Algorithm_2. 복잡도

알고리즘 성능평가와 복잡도

복잡도란 '계산 복잡도 이론'에서 나온 것으로, 특정 알고리즘의 성능을 나타내는 척도이다. 복잡도는 다음과 같이 두 개념으로 나누어진다.

• 시간 복잡도: 알고리즘 수행에 걸리는 시간 분석
• 공간 복잡도: 알고리즘의 메모리 사용량 분석

특정 알고리즘의 복잡도는 동일 기능을 수행하는 다른 알고리즘에 비해 낮을수록 일반적으로 좋다고 볼 수 있다. 이러한 복잡도는 코드의 길이나 가독성과는 관련이 없으며, 실제 성능적인 측면만 고려하는 개념이다.

시간 복잡도와 빅오 표기법

빅오 표기법(Big-O Notation)은 시간 복잡도를 표현하는 방법으로, 가장 빠르게 증가하는 항만을 고려하는 방법이다. 빅오 표기법에 따라 빠른 방식에서부터 느린 방식까지를 정리하면 다음과 같다.

순위	명칭
O(1)	상수시간(Constant time)
O(logN)	로그시간(Log time)
O(N)	선형시간
O(NlogN)	로그 선형 시간
O(1)	상수시간(Constant time)
O(N²)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

간단한 코드를 통해 살펴보자.

let arr = [1, 2, 3, 4, 5];

let result = arr.map((el) => {
  return el * 1;
});

map은 arr의 수 만큼 연산을 반복하므로, O(N)의 시간복잡도를 가진다.

let arr = [1, 2, 3, 4, 5];

for (let el of arr) {
  for (let el2 of arr) {
    return el * el2;
  }
}

위와 같은 이중반복문은 arr의 수를 제곱한 만큼의 경우의 수가 생기므로, O(N²)의 시간복잡도를 가진다.

일반적인 코딩테스트의 시간제한은 1~5초 정도로 이러한 시간복잡도를 고려하여 최대한 낮은 복잡도를 가지도록 코드를 설계하는 것이 중요하다.

참고
위키백과 - 시간 복잡도
이것이 취업을 위한 코딩 테스트다 with 파이썬