[이코테] 1. 복잡도
! 이것이 코딩 테스트다 책을 정리하여 내가 다시 보기 위함 !
시간 복잡도(Time Complexity)
빅오(big-O) 표기법에 의해 대략적인 수행시간을 예상해볼 수 있지만, 코딩테스트에 한해서는 절대적이지 않다.
- O(N^3) 인 경우에도 N이 작고 상수항이 +1,000,000 이라면 무시할 수 없는 수준이기 때문
코딩테스트 환경에서 O(N^k)의 알고리즘은 시간초과가 발생할 확률이 높다. 시간제한은 1~5초 정도이므로 연산횟수가 10억을 넘어가도록 코드를 작성하면 오답 판정을 받게된다. 알고리즘을 구상해놓고 머리속으로 간략하게 평가해보자
N이 1000일 경우 대략적인 연산 횟수
- O(N) = 1,000
- O(NlogN) = 10,000
- O(N^2) = 1,000,000
- O(N^3) = 1,000,000,000
따라서 문제를 풀 때 조건을 먼저 보도록 하자
- 시간 제한이 1초인 경우, N의 개수가 1000만개라면 위의 대략적인 연산 횟수를 바탕으로 O(N) 안쪽으로 동작하는 알고리즘으로 구현해야 함을 알 수 있다
- 시간 제한 1초인 경우
- N 의 범위가 500 : O(N^3)
- N 의 범위가 2,000 : O(N^2)
- N 의 범위가 100,000 : O(NlogN)
- N 의 범위가 10,000,000 : O(N)
- 그 이상은 : O(logN)
시간 제한이 2초, 3초 라도 크게 달라지는 것은 없지만 N의 범위에 따라 유동적으로 사고하며 구현하자
공간복잡도(Space Complexity)
공간복잡도 또한 마찬가지로 빅오 표기법을 이용한다
코딩테스트에서는 메모리 사용기준을 MB단위로 보여준다. 보통 128MB ~ 512MB사이로 정해진다.
- int = 4byte(32bit)
- int a[1000] = 4byte * 1000 = 4KB
- int a[1000][1000] = 4byte * 1000 * 1000 = 4MB
파이썬에는 int자료형이 따로 명시되어있지는 않지만 대략 100만 단위를 넘어가면 안된다는 것을 알 수 있다. 즉, 리스트의 크기가 1000만 단위를 넘어간다면 잘못 설계했을 확률이 높다.