시간 복잡도 측정하기(빅오 표기법, 시간 메모리 측정 방법)

빅오 표기법

빅오 표기법	명칭
O(1)	상수시간(Constant time)
O(logN)	로그시간(Log time)
O(N)	선형시간
O(NlongN)	로그선형시간
O(N^2)	이차 시간
O(N^3)	삼차시간
O(2^n)	지수 시간

*시간 복잡도가 낮은 순서로 작성

 

일반적인 시간 제한이 1초인 문제에 대한 예시

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

 

시간과 메모리 측정

공부하는 과정에서 실질적인 소요 시간을 확인하여 알고리즘을 점검해보는 것이 좋다.

 

import time
start_time = time.time() # 측정 시작(소스코드 제일 앞부분)

##### 프로그램 소스코드 #####

end_time = time.time() # 측정 종료(소스코드 제일 끝부분)
print("time :", end_time - start_time) # 수행 시간 출력