[알고리즘 기초] 복잡도

[1] 시간 복잡도 

일반적으로 코딩 테스트 환경에서는 O(n^3)을 넘어가면 문제풀이에서 사용하기 어려움. 

• CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요. 
• N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸리고 파이썬은 더욱 오래 걸림. 
• 보통 코테의 시간 제한은 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

• O(NlogN)인 알고리즘은 시간복잡도가 동일하더라도 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번에서 100,000번까지 실제 연산의 횟수는 차이가 클 수 있음.

 

시간 제한이 1초인 문제일 때 데이터의 개수 N의 범위에 따른 시간 복잡도 

N의 범위가 500인 경우	시간복잡도 O(N^3)인 알고리즘
N의 범위가 2,000인 경우	시간복잡도 O(N^2)인 알고리즘
N의 범위가 100,000인 경우	시간복잡도 O(NlogN)인 알고리즘
N의 범위가 10,000,000인 경우	시간복잡도 O(N)인 알고리즘

• 데이터의 개수가 1000만개를 넘어가고 시간제한이 1초라면 최악의 경우 O(n)의 시간복잡도로 동작하는 알고리즘을 작성해야 함. 
• 데이터의 크기가 100억이나 1,000억을 넘어가는 경우 O(logN)의 시간복잡도를 설계해야 함. 

 

[2] 공간 복잡도 

코딩 테스트에서는 보통 메모리 사용량을 128~512 MB로 제한함. 

일반적으로 1,000만 단위가 넘어가지 않도록 설계해야 함.

 

 

[3] 시간과 메모리 측정

수행 시간 측정 소스코드

import time
start_time = time.time() #측정 시작

#프로그램 소스코드

end_time = time.time() #측정 종료
print("time:", end_time - start.time) # 수행시간 출력