시간 복잡도와 공간 복잡도

복잡도

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

 

시간 복잡도 : 특정한 크기의 입력에 따라서 알고리즘이 얼마나 오래 걸리는지를 의미한다.

간단하게 생각하면 시간이 얼마나 걸리냐를 나타낸다.

알고리즘을 위해 필요한 연산의 횟수를 계산할 수 있다.

 

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

알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다.

 

빅 오 표기법: 상한 만을 고려하는 방식으로, 코딩테스트의 중요한 기준으로 쓰인다.

파이썬의 경우 1억번의 연산이 보통 1초라고 볼 수 있다.

 

O(1)	스택의 push,pop
O(logN)	이진트리
O(N)	for문
O(NlogN)	퀵정렬, 병합정렬, 힙정렬
O(N^2)	이중for문, 삽입정렬,거품정렬,선택정렬
O(N^3)
O(2^N)	피보나치

N의 범위가 500 인 경우: 시간복잡도가 O(N^3)으로 설계하면 1.25억번으로 풀 수 있다.

N의 범위가 2000 인 경우: 시간복잡도가 O(N^2)으로 설계

N의 범위가 100,000 인 경우: 시간복잡도가 O(NlogN)으로 설계

N의 범위가 10,000,000 인 경우: 시간복잡도가 O(N)으로 설계

 

공간 복잡도

빅오 표기법을 사용한다.

 

코딩테스트는 대부분 배열을 사용해서 푸므로 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보면

int a[1000] :4KB

int a[1000000] :4MB

int a[2000][2000] :16MB

보통 사용량은 128~512MB정도로 제한한다.

그래서 데이터의 개수가 1000만이 넘지않도록 알고리즘 설계가 필요하다.