알고리즘의 복잡도

제대로 된 알고리즘을 구현하기 위해서는 복잡도를 고려해야 한다.

복잡도에 대해 알아보자.

 

복잡도

복잡도(complexity) : 알고리즘의 성능을 나타내는 척도

 

- 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 -> 필요한 연산의 횟수

- 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 ->   필요한 메모리의 양

 

=> 동일한 기능을 수행한다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘

 

시간 복잡도

- 시간제한 내에 구현하여야 함 (보통 1~5초 제한)

- Big-O 표기법 사용 (가장 빠르게 증가하는 항만을 고려하는 표기)

- 최악인 경우의 시간복잡도를 우선 고려하여야 함

- 보통의 경우 상수항을 무시하지만, 항상 절대적인 것은 아님 !

 

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

 

시간 복잡도가 O(N^K)일 때, 이를 다항 시간에 동작하는 알고리즘 이라고 한다.

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

연산 횟수가 10억을 넘어가면 C언어를 기준으로 약 1초 이상의 시간이 소요된다. 만약 N의 크기가 5000을 넘는다면, 10초 이상의 시간이 걸릴 수 있다. 특히 파이썬이 더욱 오래 걸린다.

 

- Big-O 표기법으로는 시간 복잡도가 같더라도, 실제 연산 횟수는 다를 수 있다.

- 문제의 조건을 먼저 확인하고, 사용가능한 알고리즘을 좁혀 나가는 전략 필요

 

 

공간 복잡도

- 메모리 사용량 제한 내로 구현하여야 함 (보통 128~512MB 제한)

- Big-O 표기법 사용

- 메모리양 체감하기

 

int a[1000]	4KB
int a[1000000]	4MB
int a[2000][2000]	16MB

 

- 일반적으로 데이터 개수 1000만 단위가 넘지 않도록 설계해야 함

 

 

시간과 메모리 측정

'이것이 코딩테스트다'에서 제공한 수행 시간 측정 코드이다.

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

# ... 프로그램 #

end_time = time.time() #측정 종료 시작
Print("time :", end_time = start_time) # 수행 시간 출력

=> 알고리즘의 성능을 확인하기 위해 실제 수행 시간을 측정해볼 수 있다. 이러한 습관을 기르는 것이 좋다.