[자료구조/알고리즘] 시간복잡도

 

복잡도(complexity) : 알고리즘의 성능을 객관적으로 평가하는 기준

시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것으로, Big-O 표기법을 이용

* 공간 복잡도 고려는 최근들어 중요성이 줄어듦

 

Big-O 표기법

: 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가를 고려함

1) Big-O : 최악의 경우를 고려 >> 항상 최악의 경우를 대비

2) Big-Ω : 최선의 경우를 고려

3) Big-θ : 중간의 경우를 고려 

 

1. O(1) (constant complexity)

: 입력값이 증가하더라도 시간이 늘어나지 않음

: 가장 빠른 시간 복잡도

Ex. 배열 중 인덱스 하나 리턴 (배열이 증가하더라도 리턴값이 1개이기에 복잡도가 늘어나지 않음)

 

2. O(n) (linear complexity)

: 입력값이 증가함에 따라 같은 비율로 시간도 증가

Ex. 반복문 n번 반복 (5배, 10배가 되어도 동일하게 n)

 

3. O(log n) (logarithmic complexity)

: O(1) 다음으로 빠른 표기법

Ex. 진행할 때마다 절반으로 실행이 줄어듦

 

4. O(n^2) (quadratic complexity)

: 입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가하는 것

Ex. 이중 반복문, 삼중 반복문 등

 

5. O(2^n) (exponential complexity)

: 가장 느린 시간 복잡도

Ex. 파보나치 수열(재귀)

 

[기타]

제한된 시간 내에 정확한 값을 반환하기 위해 시간 복잡도 예측이 필요

 

데이터 크기에 따른 시간 복잡도

- n<=1,000,000  >> O(n), O(log n)

- n<=10,000 >> O(n2)

- n<=500 >> O(n3)