복잡도

복잡도는 두 가지로 나눌 수 있다.

• 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양

시간 복잡도

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 빅오는 가장 차수가 큰 항만 남기는 방법으로 예를 들어 연산 횟수가

3N^3 + 5N^2 + 1,000,000

인 알고리즘이 있다고 사정할 때, O(N^3)로 표기된다. 하지만 N이 10처럼 작은 수일 경우 상수인 1,000,000의 영향력이 클 수 밖에 없는데, 이러한 문제때문에 연산 횟수가 N의 크기에 따라 대략적으로 어떻게 되는지 알아보자.

문제의 조건을 확인하고 데이터의 개수 N이 1,000만개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것이다. 혹은 100억이나 1,000억개를 넘어가는 경우 O(logN)의 복잡도를 갖는 알고리즘을 작성해야 할 것이다.

시간 제한이 1초인 문제를 풀때의 예시다.

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

공간 복잡도

공간 복잡도를 표현할 때도 빅오(Big-O) 표기법을 사용한다. 일반적으로 메모리 사용량 기준은 MB단위로 제시된다. int형을 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자.

• int a[1000]: 4KB
• int a[1000000]: 4MB
• int a[2000][2000]: 16MB

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한하는데, 이건 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미이다. 만약 리스트의 크기가 1,000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것이 아닌지 고민해봐야 한다.

시간과 메모리 측정

수행 시간 측정 소스코드

import time

start_time = time.time()
end_time = time.time()

print("time: ", end_time - start_time)

ref
이것이 취업을 위한 코딩 테스트다 with 파이썬