Data Structure & Algorithm _#2 시간복잡도

수행시간

• 최악의 경우의 입력에 대한 기본 연산 횟수

시간 복잡도(time complexity)

• 측정방법:

  • 모든 입력에 대해 기본연산횟수 더한 후 평균 ->불가능에 가까움..

  • 가장 안 좋은 입력(worst case input)에 대한 기본 연산 횟수를 측정

    

Big-O

-> 최고차항으로만 간단하게 증가율 표기

-방법

​ 1) 함수의 최고차항만 남긴다

​ 2) 최고차항 계수(상수) 생략

​ 3) Big-O(최고차항) 형태로

Ex) Algorithm1: T1(n)=2n-1 Algortihm2: T2(n)=4n+1 Algorithm3: T3(n)=3/2n^2-3/2n+1

• Big-O표시

  -> T1(n)=O(n) T2(n)=O(n) T3(n)=O(n^2)

Q.

​ 1) Algorithm2가 Algorithm1보다 2배 느리다 : O (계수로 확인 가능)

​ 2) Algorithm3는 n<5/3면 Algorithm2보다 빠르다 : O

​ 모든 n에 대해 Algorithm 1보다 느리다 : O

​ 3) Algorithm3는 n>5/3면 항상 Algorithm2보다 느리다 : O

-집합으로 이해해보기

-연습문제

​

​ A. T(n): 3n/2

​ Big-O: O(n)

​ A. T(n): 1 + n^2(4log n)

​ Big-O: O(n^2log n)

​ A. T(n): 2 + 4n^0.5

​ Big-O: O(n^(0.5)) = O(sqrt(n))

​ A. T(n): 2 + 4log n

​ Big-O: O(log n)