[알고리즘] 시간 복잡도

시간 복잡도는 알고리즘의 성능을 나타내는 지표다.

해당 알고리즘을 실행시켰을 때, 연산 횟수에 대한 worst case적인 한계를 의미한다.

 

시간 복잡도는 낮으면 낮을 수록 좋다.

빅 O 표기법을 통해 알 수 있으며, 현대 컴퓨터에서 대략적으로 1초 연산이 최대 1억번의 연산 횟수를 가진다는 걸 머릿속에 넣어 놓으면 좋다.

 

이를 통해 우리는 조건이 1초, 1만개가 들어가는 테스트 케이스 범위가 주어졌을 때, O(n^2)은 쓰지 못한다는 걸 직감적으로 알 수 있게 된다. 

 

시간을 측정하려면 절대 시간을 측정하는 방법도 있으나, 그런 방법은 코딩 테스트에서는 잘 활용되지 않는다.

 

빅오 표기법

1차원 배열에서 가장 값을 늦게 찾는 경우는 리스트의 끝까지 검색했을 때 혹은 값을 못찾았을 때.

즉, O(n)이다. 이때가 worst case이고, 빅오 표기법의 시간복잡도는 이런 worst case의 집합이다.

 

연산 횟수가 f(x)라는 함수일 떄, 수식에서 최고차항의 함수만 가져와서 계수를 1로 만들면 된다.

 

최고차항만 남기는 이유는 로그함수와 지수함수와의 차이를 쉽게 구분하고 직관적으로 받아들이기 위함이다.

 

코딩 테스트의 문제는 출제자가 의도를 충분히 구현했다면 풀 수 있도록 되어 있으므로, 1억번이 아닌 1000만~3000만 정도로 고려한다.

 

즉, n의 범위 5000 정도가 O(n^2)를 사용했을 때의 한계치.

 

따라서, 각 시간복잡도의 최대 연산 횟수는

 

시간 복잡도

O(n!) = 10번

O(2^n) = 20~25번

O(n^3) = 200~300번

O(n^2) = 3000~5000번

O(nlogn) = 100만

O(n) = 1000만~3000만

O(logn) = 10억

 

 

별 찍기 문제의 시간 복잡도는?

for i in range(n):
	print('*'*i)

*를 1,2,3....n번 찍는다 -> 1,2,3,...n번의 연산

그걸 n번 반복한다 -> n번의 반복

 

따라서 수열이므로 n(n+1)/2, 즉, O(n^2)의 시간복잡도를 가진다.

 

이번엔 2배씩 줄어드는 반감기가 있다면?

n, n/2, n/4....

마지막에는 n/ (2^k)<=1이라고 생각하면, 양변에 로그를 취했을 때,

 

log2 (n) = k

 

따라서 k 번 반복한다는 뜻이므로 시간복잡도는 O(logN)이다.

 

반으로 줄어드는 동작이면 O(logN)이다.