[개념] 복잡도

이것이 취업을 위한 코딩테스트다를 읽고 정리한 문서입니다.

1. 복잡도

1) 의미

알고리즘의 성능을 나타내는 척도

2) 종류

1. 시간복잡도: 특정 크기의 입력에 대한 알고리즘의 수행 시간

2. 공간 복잡도: 특정 크기의 입력에 대한 알고리즘의 메모리 사용량

   일반적으로 거래 관계가 성립
   ex) memoization - 메모리를 더 많이 사용해 시간을 비약적으로 줄이는 방법

3) 시간복잡도

1. Big O 표기법
   알고리즘의 최악의 경우를 상정한 계산법
   ⇒ 가장 빠르게 증가하는 항만을 고려 (간단한 정의)

   ex)
   n에 비례하는 연산을 수행하는 반복문의 경우 O(N)
   단순 연산: O(1)
   이중 for 문: O($n^{2}$) (예외 존재)

2. 비교
   O(1) < O($logN$) < O(N) < O($NlogN$) < O($N^{2}$) < O($N^{3}$) < O($2^{n}$)

3. 주의할 점

• 실제 코딩테스트에선 차수가 작은 항을 완전히 무시했을 때 문제가 생길 수 있음
  ex) 상수값이 미치는 영향력이 큰 경우
• O($N^{3}$)을 넘기면 문제 풀이에서 사용이 어려움
  통상적으로는 다항 시간 알고리즘에 해당해 풀만 한 알고리즘으로 분류되긴 하지만 테스트 상에선 연산량이 기하급수적으로 늘어날 수 있기 때문에 그렇지 않다.

4. 알고리즘의 조건 예시
   ex) N이 1000만 개 이상, 시간 제한 1초 = O(N)을 최악의 경우로 두고 동작하는 알고리즘
   N이 100억 or 1000억을 넘김 = 이진탐색 (O(logN))의 시간 복잡도를 갖는 알고리즘 작성

제한시간 1초인 경우

N	시간복잡도
500	O($N^{3}$)
2000	O($N^{2}$)
100,000	O($NlogN$)
10,000,000	O(N)

3) 공간복잡도

• 빅오 표기법 사용
• 사용 기준: MB
• 일반적인 경우 데이터의 수는 1000만 단위를 넘어가지 않음

4) 시간 측정 방법

import time
start_time = time.time()

#프로그램 소스 코드
end_time = time.time()
print("time: end_time-start_time")

파이썬 기본 정렬 라이브러리는 O(NlogN)의 성능을 보장한다.