20240129 이것이 코딩 테스트다

복잡도

복잡도에는 시간 복잡도와 공간 복잡도가 있다.

시간 복잡도

작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간.
시간 복잡도를 표현할 때는 빅오 표기법을 사용함. 빅오 표기법은 간단히 정의하면 가장 빠르게 증가하는 항만을 고려하는 표기법.

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	다항 시간 - 이차 시간
O(N^3)	다항 시간 - 삼차 시간
O(2^n)	지수 시간

시간 측정 방법

import time
start_time = time.time()

# 프로그램 소스코드 #

end_time = time.time()

print("time :", end_time - start_time)

공간 복잡도

코딩 테스트에서는 보통 메모리 사용량을 128~512mMB 정도로 제한하고, 따라서 데이터의 개수(리스트의 크기)가 1000만 단위 이상이 아니도록 알고리즘 설계를 해야함.