복잡도

복잡도

알고리즘의 성능을 나타내는 지표

'시간 복잡도' 와 '공간 복잡도' 로 나눌 수 있음

• 시간 복잡도
  • 알고리즘이 얼마나 오래 걸리는지
• 공간 복잡도
  • 알고리즘이 얼마나 많은 메모리를 사용하는지

대개, 시간 복잡도와 공간 복잡도는 Trade-Off 관계를 가지고 있음

시간 복잡도

시간 복잡도에 대해 표기할 때에는 대개, Big-O 표기법을 사용함.
전체 알고리즘에서 가장 오래 걸리는 부분(상한선)만을 표기

$O(N)$

 

이중 for문의 경우, 대부분 O(N^2)의 시간 복잡도를 갖지만, 그 내부에 들어있는 함수에 따라 반드시 그렇게 되는 것은 아니다.
ex) 퀵 정렬

 

알고리즘의 시간 복잡도를 하나의 식으로 세워 생각하고, 그에 맞춰 가장 보수적으로 접근하여 최악의 경우의 수를 생각할 필요가 있다.

$3N^3+5N^2+1000000$의 시간 복잡도를 갖는 알고리즘에서,
상수 복잡도가 무시될 만큼의 충분히 큰수를 N이 갖게 된다면 상수 복잡도에 대해서 크게 고려할 필요가 없겠지만,
그렇지 않은 경우에는 상수 복잡도가 해당 알고리즘의 복잡도를 결정할 가장 큰 요인이 될 수 있다.

 

보통 시간 복잡도가 1억이 되면, 1초의 시간이 걸린다고 생각하고 문제를 접근하면 좋다.

공간 복잡도

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB로 제한하는데, 그렇기 떄문에 일반적으로 데이터의 개수가 1000만 단위를 넘지 않도록 알고리즘을 설계할 필요가 있다.

TIP

• 코딩 테스트 문제를 풀때, 항상 시간+공간 복잡도에 대해 계산해보는 습관을 기르자
• 기본 built-in 라이브러리를 사용할 떄에, low-level로 구현한 알고리즘과의 성능 차이가 애매하다면, 직접 걸리는 시간을 구해서 비교해보자