시간 복잡도 / Big-O 표기법
시간 복잡도
알고리즘을 만들고 그 알고리즘이 현실에서 사용가능한지 알아보기 위해 시간복잡도를 계산한다.
시간 복잡도(Time Complexity)는 입력의 개수가 n개일 때 알고리즘의 실행 시간을 n에 대한 함수로 표현한다. 최악의 경우 시간 복잡도는 입력의 개수가 n인 모든 가능한 입력에 대한 최대 실행 시간을 말한다. 보통 시간복잡도를 말할 때는 최악의 경우 시간복잡도를 의미한다.
알고리즘은 아주 n의 개수가 아주 많다고 가정하기 때문에 상수는 없는 것으로 취급하고 계수가 가장 큰 함수로 구한다.
Big-O 표기법
상수 c와 n0가 존재하며, n≥n0 인 모든 n에 대하여 T(n) ≤ c · f(n)을 만족하면 T(n) = O(f(n))이라고 한다.
T(n)=3n^2 + 100n 일 때, f(n)이 n^2이면 n≥n0인 모든 n에 대하여 3n^2+100n ≤ c · n^2 을 만족하는 c가 존재한다.
따라서 3n^2 + 100n의 시간복잡도는 O(n^2)이다.
간단하게 하자면 T(n)이 주어졌을 때 n의 계수가 그 알고리즘의 시간 복잡도이다.
3n^2-100n+6 을 Big-O 표기법으로 표기하면 계수가 가장 큰 3n^2을 남기고 상수까지 제외해서 O(n^2)이 되는 것이다.
상수를 포함하여 쓰지 않는 이유는 n이 커질 수록 상수가 큰 의미를 가지지 않게 되기 때문이다. 물론 상수가 너무 크면 시간에 영향을 주기도 하지만 시간복잡도 표기법 상에서는 그렇게 한다.
시간복잡도의 예제
알고리즘 a와 b가 있다고 하자.
a는 n개의 입력에 소요되는 시간이 Ta(n) = 3n^2이고, b는 Tb(n) = 100n 이다.
이 둘을 Big-O 표기법으로 시간복잡도를 구하면 Ta(n) = O(n^2), Tb(n) = O(n)이다.
아래는 n의 개수에 따른 소요시간의 차이를 나타낸 표이다.
| n의 개수 | 1 | 10 | 100 | 1000 | 10000 | 100000 | 1000000 |
| Ta(n) | 9 | 900 | 90,000 | 9,000,000 | 900,000,000 | 90,000,000,000 | 9,000,000,000,000 |
| Tb(n) | 100 | 1,000 | 10,000 | 100,000 | 1,000,000 | 10,000,000 | 100,000,000 |
| 더 빠른 것 | a | a | b | b | b | b | b |
n의 개수가 적은 초반에는 알고리즘a가 더 빠른 것 같아 보이지만 n이 커질 수록 a의 소요시간이 매우 빠르게 늘어난다는 것을 확인할 수 있다.
시간 복잡도의 분류
시간복잡도는 다항 시간(polynomial time)과 지수 시간(exponential time)이 있다. 지수시간의 경우 n이 증가함에 따라 매우 큰 값을 가지게 되기 때문에 실제로 사용할 수 있는 가능성은 없다고 본다.
다항시간은 시간 복잡도가 작은 순서대로
O(1), O(log n), O(√n), O(n), O(n log n), O(n^2), O(n^3) ..... 이 있다.
현업에서 사용 가능한 수준은 O(n log n)정도 까지라고 한다.