시간, 공간복잡도

시간 복잡도: 입력에 대해 알고리즘이 얼마나 오래 걸리는지, 필요한 연산의 횟수

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

 

효율적인 알고리즘을 사용하면 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립한다. 메모리를 많이 사용하는 대신 반복 연산을 생략하면서 계산 복잡도를 줄일 수 있다.

 

-시간복잡도

만약 연산 횟수가 3N^3 + 5N^2 + 1,000,000이면 상수를 무시할 수 없다. 일반적 코딩 테스트에선 상수를 고려해야 하는 경우는 적지만 빅오 표기법이 항상 절대적인 것은 아니다.

 

일반적으로 코딩테스트에서 O(N^3)을 넘어가면 문제 풀이에 사용하기 어렵다. 그렇기에 알고리즘 문제 풀이 전에 조건을 먼저 확인하고 얼마나 효율적으로 풀어야하는지 알아야한다.

 

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

N 범위 500: O(N^3)이면 풀 수 있다.

N 범위 2,000: O(N^2)이면 풀 수 있다.

N 범위 100,000: O(NlogN)이면 풀 수 있다.

N 범위 10,000,000: O(N)이면 풀 수 있다.

 

-공간 복잡도

공간 복잡도도 빅오 표기법을 사용한다. 메모리에도 절대적 제한이 있는데 MB 단위로 제시된다.

코딩 테스트 대부분은 리스트(배열)을 사용해서 풀어야 한다. 보통 메모리 사용량을 128~512MB로 제한한다. 즉 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다.