시간 복잡도
- 파이썬은 1초에 2천만번 정도의 연산을 한다고 생각하면 됨.
- N의 범위가 1,000,000인 경우 : O(logN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- in 시간복잡도는 자료형에 따라 다름!
- list, tuple : O(n) - 하나하나 순회함
- set, dictionary : O(1) ~ O(n) - hash를 통해 저장하므로 접근시간은 O(1). (단, 해쉬의 충돌이 많아 성능이 떨어지는 경우 O(n)이 걸릴 수도 있음.)
- 결론은 리스트말고 dictionary 쓰면 더 짧으니 추천!
공간 복잡도
- 보통 코딩테스트에서 128~512MB로 제한.
- int의 경우 약 리스트 길이가 100만개일때, 4MB
- 즉, 128MB일때 3200만개, 256MB일때 6400만개, 512MB일때 1억2800만개 사용가능.
- 참고 : 나동빈, 이것이 취업을 위한 코딩테스트다 with 파이썬
'알고리즘(Python)' 카테고리의 다른 글
| [Python] 자주쓰는 라이브러리, 함수 정리 (0) | 2021.07.08 |
|---|