시간 복잡도
시간 복잡도를 이야기할 때, 보통 O(n)이라고 하는 표기를 사용한다. 학술적인 내용은 굉장히 복잡하지만, 간단히 설명하면 루프, 재귀 등 반복이 있고, 그 반복이 n의 크기에 비례하여 커지면 복잡도가 증가한다.
- O(n) – 선형 시간복잡도 : 데이터 개수가 늘어감에 따라 선형적으로 시간이 걸린다. 10배 많은 데이터를 넣으면 10배 더 걸린다.
- O(n^2) – 지수 시간복잡도: 10배 많은 데이터를 넣으면 100배 더 걸린다.
- O(log n) – 로그 시간복잡도: 10배 많은 데이터를 넣어도 오히려 증가폭이 확 줄어든다. 거의 신이 내린 알고리즘이다 (Binary Search)
- O(n log n) – 선형로그 시간복잡도: 일반적으로 빠르다라고 여겨지는 정렬 알고리즘은 해당 시간 복잡도를 가진다(병합, 퀵 정렬)
왜 이런 이야기를 하냐면, 데이터 크기가 큰 문제를 풀 때, for문을 몇 번 중첩할 지를 정하는 것이 매우 중요하기 때문이다.
- 데이터 크기가 500이면 O(N^3)도 괜찮다.
- 크기가 2000이면 O(N^2)여야 한다.
- 크기가 100,000 (십만) 이면 O(N log n)으로 설계해야한다.
- 크기가 10,000,000 (억) 이면 O(N)으로 설계해야한다.
공간 복잡도
일반적으로 제한은 덜하지만, 파이썬에서 대략적으로 100만개까지는 괜찮지만, 1000만개 이상을 리스트에 담으면 제한을 넘어간다. 알고리즘 설계를 제대로 한 것인지 확인하는 자세가 필요하다.