[Python] 시간복잡도, 공간복잡도 제한

해당 글은 아래의 2가지를 다룬다.
📌 시간 복잡도
📌 공간 복잡도

📌 시간 복잡도

- 입력의 크기에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.

- 시간 복잡도를 표현할 때는 Big-O(빅오) 표기법을 사용한다.

- 빅오 표기법에서는 상수와 작은 차수의 항을 제거하고, 차수가 가장 큰 항만 표기한다.

- 시간 복잡도 표

빅오 표기법	명칭
O(1)	상수 시간(Constant Time)
O(logN)	로그 시간(Logarithmic Time)
O(N)	선형 시간(Linear Time)
O(NlogN)	선형 로그 시간(Log-linear Time)
O(\(N^2\))	이차 시간(Quadratic Time)
O(\(N^3\))	삼차 시간(Cubic Time)
O(\(2^N\))	지수 시간(Exponential Time)

Q. 그럼 시간 복잡도가 작은 알고리즘은 항상 빨리 실행이 종료되나요?

그렇지 않다! 빅오 표기법에서는 차수가 가장 큰 항만 남게 되지만, 입력의 크기가 작을 때는 상수 값이 미치는 영향력이 크다.

예를 들어, 연산 횟수가 \(5N+100000000\)인 알고리즘이 있을 때, 빅오 표기법은 O(N)이지만 N의 크기가 작아도 상수 값이 크므로 시간 복잡도가 큰 알고리즘이 더 빨리 종료될 수도 있다.

 

- 코딩테스트 Tip!

시간 제한이 1초일 때 N의 범위 별로 아래의 시간 복잡도인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위	시간 복잡도
500	O(\(N^3\))
2,000	O(\(N^2\))
100,000	O(NlogN)
10,000,000	O(N)

 

📌 공간 복잡도

- 입력의 크기에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

- 공간 복잡도를 표현할 때도 Big-O(빅오) 표기법을 사용한다.

- 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.

- int의 메모리 사용량

데이터의 개수 (리스트의 길이)	메모리 사용량
1,000	4 KB
1,000,000	4 MB
10,000,000	40 MB

 

* 코딩테스트 시,

시간 제한과 메모리 제한을 참고하여 어떤 알고리즘을 사용해야 하는지,

어느 정도의 메모리를 사용해야하는지 유추하여 빠르게 풀 수 있다.

 

 

[참고자료] : 이것이 취업을 위한 코딩테스트다 with 파이썬 책