[이것이 취업을 위한 코딩 테스트다] 시간 복잡도

시간 복잡도

알고리즘을 위해 필요한 연산의 횟수
코딩 테스트에서 작성한 프로그램이 모든 입력을 받아 처리하고 실행한 결과를 출력하는데까지 걸리는 시간
특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는 가?

• 문제에서 가장 먼저 확인해야할 내용
• ‘복잡도’라고 하면 보통 ‘시간 복잡도’를 의미함
• 시간 제한을 넘기면 ‘시간 초과(Time Limit Exceeded)’ 메시지 발생 후 오답 처리됨
• 연산 횟수가 5억을 넘어가는 경우 파이썬은 5 ~ 15초 가량의 시간 소요
• 보통 코딩 테스트의 시간 제한 : 1 ~ 5초(2000만번의 연산 ~ 1억번의 연산)

• 시간 제한이 1초인 문제의 예

  N의 범위	시간 복잡도 기준
  500	O(N^3)
  2,000	O(N^2)
  100,000	O(NlogN)
  10,000,000	O(N)

빅오(Big O) 표기법 : 시간 복잡도를 표현하는 방법

• 차수가 가장 큰 항만 남기지만, N이 작을 때 상수의 영향이 클 수 있으므로 빅오 표기법이 항상 절대적인 것은 아님(3N^3 + 5N^2 + 1,000,000)
• 일반적으로, 시간복잡도가 O(N^3)을 넘어가면 문제풀이에서 사용하기 어려움

시간 복잡도	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

공간 복잡도

알고리즘을 위해 필요한 메모리의 양

• 대부분 리스트를 사용해서 풀어야 함
• 보통 128MB ~ 512MB의 공간 복잡도 제한이 있음
  • 데이터의 개수가 1000만 단위가 넘어가지 않도록 설계 필요
  • 파이썬에서도 100만개 이상 크기의 리스트를 선언하는 경우는 거의 없음

시간과 메모리 측정

import time
start_time = time.time()

end_time = time.time()
print("time: ", end_time - start_time)