시간복잡도

코데 준비를 시작했다.

파이썬으로 문제를 풀 때 가장 많이 걸렸던 것이 '시간초과' 이다.

 

데이터의 개수 N의 범위와 제한시간에 따라 어느 정도의 시간 복잡도를 예상하고 알고리즘을 설계할 수 있다.

 

먼저 빅오 표기법에 따른 식과 명칭을 순서대로 정리해보자.

빅오 표기법	명칭
\(O(1)\)	상수 시간 (Constant time)
\(O(logN)\)	로그 시간 (Log time)
\(O(N)\)	선형 시간
\(O(NlogN)\)	로그 선형 시간
\(O(N^2)\)	이차 시간
\(O(N^3)\)	삼차 시간
\(O(2^N)\)	지수 시간
\(O(N^k)\)	다항 시간에 동작하는 알고리즘

 

일반적으로 코딩 테스트 환경에서는 삼차 시간 을 넘어가면 문제 풀이에서 적용하기 힘들다고 한다.

CPU 기반 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면, C언어 기준으로 통상 1초 이상의 시간이 소요된다.

 

아래는 각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라 어떻게 분포되는지를 나타낸 표이다.

시간 복잡도	N이 1,000일 때의 연산 횟수	Python 기준 예상 소요 시간
\(O(N)\)	1,000
\(O(NlogN)\)	10,000
\(O(N^2)\)	1,000,000 (100만)	약 0.002초
\(O(N^3)\)	1,000,000,000 (10억)	약 2초

 

 

 

---

위 개념을 활용하는 방법

ex) 데이터의 개수 N이 1,000만개를 넘어가며 시간 제한이 1초: 최악의 경우 O(N) 의 시간 복잡도

ex) 데이터의 크기나 탐색 범위가 100억, 1,000억을 넘어간다: O(logN) 의 시간복잡도를 갖는 알고리즘 작성

 

일반적 예시

• N의 범위가 500인 경우: 시간 복잡도가 \(O(N^3)\) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우: 시간 복잡도가 \(O(N^2)\)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000인 경우: 시간 복잡도가 \(O(NlogN)\)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000인 경우: 시간 복잡도가 \(O(N)\)인 알고리즘을 설계하면 문제를 풀 수 있다.