⏱️ 시간 복잡도 (Time Complexity)
단순하게 생각해서 '특정한 크기의 입력에 대한 알고리즘의 대략적인 수행 시간'
-
보통 코딩테스트 문제의 시간제한은
1초 ~ 5초로 제한 -
Python 의 경우, 초당 약 20,000,000(2천만)번의 연산이 가능하다고 알아두자.
-
Python 의
in시간 복잡도는 자료형에 따라 다르다.- List, Tuple : O(N) - 하나 하나 탐색!
- Set, Dictionary : O(1) ~ O(N) - Hash를 통해 저장하므로 접근 시간은 상수 시간!
(단, Hash 의 충돌이 많아 성능이 떨어지는 경우 선형시간이 걸릴 수 있음.)
-
알고리즘의 따른 Big-O notation 은 다음과 같다.
⏳ 연산 횟수에 따른 시간 복잡도
만약에 총 연산 횟수 = 500,000,000(5억) 이라면?
- C, C++ : 1 ~ 3초
- Python : 5 ~ 15초
- PyPy : 때때로 C 보다도 빠른 퍼포먼스를 보임.
⌛️ 시간 제한에 따른 알고리즘 설계
ex) 시간제한 : 1초
| range of N | Big-O notation |
|---|---|
| 500 (5백) | O(N^3) |
| 2,000 (2천) | O(N^2) |
| 100,000 (10만) | O(N * log N) |
| 1,000,000 (100만) | O(log N) |
| 10,000,000 (1000만) | O(N) |
문제에서 주어진 N의 범위에 따라 다음과 같은 시간복잡도를 가지는 알고리즘을 설계하면 된다.
⏱️ 공간 복잡도 (Space Complexity)
단순하게 생각해서 '특정한 크기의 입력에 대한 알고리즘의 대략적인 메모리 사용량'
-
보통 코딩테스트 문제의 메모리 제한은
128 MB ~ 512 MB로 제한 -
int 자료형의 경우, 리스트의 길이가 100만 일 때,
4 MB! -
대략적으로
128 MB = 3200만, 256 MB = 6400만, 512 MB = 1억 2800만개의 데이터를 사용가능.
| Data의 개수 | 메모리 사용량 |
|---|---|
| 1,000 (1천) | 약 4 KB |
| 1,000,000 (100만) | 약 4 MB |
| 10,000,000 (1000만) | 약 40 MB |
| 100,000,000 (1억) | 약 400 MB |
달려