시간복잡도 요약

시간복잡도란 ?

한마디로 알고리즘의 성능이다. 정확히 몇초라는 시간을 의미하는 것이 아니고, 이정도의 입력값과 이런 코드라면 이정도의 시간이 걸릴 것이라는 일종의 예측지표이다. 시간복잡도는 최상, 평균, 최악 3가지 지표가 있지만 보통 코드를 짤 땐 항상 최악의 경우를 상정하고 짜는 것이 일반적이므로 최악의 경우인 Big O notation을 사용한다.

왜 시간복잡도를 사용하는가 ?

한마디로, 환경에 따라 실행 시간은 다를 수 있기 때문이다. 컴퓨터 HW, 와이파이, 틀어놓은 탭 수 ... 등등 어떤 알고리즘이 실행될 때 사람마다 환경이 모두 다르다. 따라서 이 알고리즘이 나에게는 효과적인데 팀원에게는 안좋을 수 있다. 따라서 더 일반적인 설명을 위해서 시간복잡도를 사용할 수 있고, 이는 환경에 상관없이 알고리즘의 성능을 설명할 수 있다.

시간복잡도 빠른 순서

O(1) → O(logN) → O(N) → O(NlogN) → O(N^2) → O(N^3) → O(2^N) → O(N!)

이 순서인데, 사실상 N^2을 넘어가는 코드는 짜면 안된다. N^2도 코테에서는 간당간당해서(웬만하면 X) 항상 우리는 자기의 코드가 NlogN 이하의 시간복잡도인지 체크해보는 것이 좋겠다. N^3부터는 아예 가망 없다고 생각하고, 그러한 코드는 아예 처음부터 짜지 말자.

 

예시를 몇개 보자.

 

O(1)

처리 시간이 한단계만에 끝나는 것을 의미한다. 예를 들어 파이썬에서 append는 단순히 맨 뒤에 원소 하나를 추가하는 것이므로 O(1)의 시간이 소요된다.

O(logN)

대표적인 O(logN)은 이진 탐색이다. 처음에 중간의 원소에 접근하고, 비교후 왼쪽반절, 오른쪽반절 중 선택해서 다시 중간에 접근... 이것을 반복하면 크기가 계속 반씩 줄어드는 것을 볼 수 있다.

O(N)

바로 위에서 이진 탐색이 logN이라고 했는데, 그럼 선형탐색은 어떨까? 맨 앞부터 끝까지 비교하며 모든 원소를 다 봐야한다. 따라서 이는 N개의 원소가 있을 때 O(N)이 걸린다고 할 수 있다.

O(N^2)

여기부터는 긴장해야한다. 시간초과가 나기 쉬운데, 괜찮은 알고리즘이라고 생각해서 접근법을 바꾸지 못하는 경우가 있을 수 있다. 대표적인 O(N^2)은 이중 for문이다. N개의 원소에 대해 이중 for문을 돌린다면 N^2번 실행되어야함을 쉽게 알 수 있다.

O(2^N)

만약 1개의 함수가 2개가 되고, 2개가 4개가 되는 함수가 있다면 어떨까? 이런 exponential한 구조는 짜면 안된다. 대표적으로 재귀로 푸는 피보나치 수열이 있다. 이는 입력값 n에 대해서 return fibo(n-1) + fibo(n-2)를 가지므로 계속 함수가 늘어나게 된다. 실제로 이렇게 풀기는 어렵고, N이 작은 경우에는 사용할 수 있어보인다.