알고리즘의 성능을 평가하는 복잡도

알고리즘 성능 평가 척도 📐

알고리즘 성능을 나타내는 척도는 일반적으로 복잡도(Complexity)라는 것을 사용합니다. 복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있으며, 각각 프로그램 실행 시간이 얼마나 걸리는지와 메모리 공간을 얼마나 사용하는지에 연관이 있습니다. 동일한 기능을 수행하는 알고리즘은 복잡도가 낮은 것이 더 좋습니다만, 일반적으로 시간 복잡도와 공간 복잡도는 서로 트레이드오프(Trade-off) 관계를 가집니다. 그래서 코딩 테스트와 같은 환경에서는 메모리를 좀 더 사용하면서 수행 시간을 줄이는 식으로 문제를 해결하곤 합니다.

시간 복잡도

문제를 해결할 때 복잡도가 몇인지 물어보면 대개 시간 복잡도를 의미합니다. 시간 복잡도는 알고리즘이 수행되는데 걸리는 시간을 의미하며, 표현할 때는 일반적으로 빅오 표기법(Big-O Notation)을 사용합니다. 빅오 표기법은 프로그램의 연산 횟수에서 최고 차항만을 남겨 표기하는 방식인데, 다음의 코드를 보면서 알아보겠습니다.

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

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

위 코드는 배열의 크기만큼 반복해 출력하는 간단한 프로그램이며, 배열이 담고 있는 요소 개수에 따라 실행 시간이 달라집니다. 여기서 요소의 개수를 N이라 하면, 반복문은 N만큼 반복하게 됩니다. 따라서 전체적인 연산 횟수는 N이 되며, 빅오 표기법에 의해 시간 복잡도는 O(N)이라 할 수 있습니다.

추가로 아래 코드도 한 번 보도록 합시다.

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

// 1번의 연산
console.log('간단한 출력');

// N번의 연산
for (let i = 0; i < arr.length; i++) {
  // N번의 연산
  for (let j = 0; j < arr.length; j++) {}
}

위 코드에서 console.log 메소드는 한 번만 실행되고, 반복문은 이중으로 NxN만큼 실행되기 때문에 총 연산 횟수는 N² + 1입니다. 하지만 빅오 표기법은 항상 최고차항만을 표기하기 때문에, 위 코드의 시간 복잡도는 O(N²)이라 할 수 있습니다.

최고차항별 빅오 표기법을 모아 그래프를 그리면 다음과 같습니다.

• O(1): 상수 시간 [해시 테이블]
• O(log n): 로그 시간 [이진 검색]
• O(n): 선형 시간 [순차 탐색]
• O(n log n): 로그 선형 시간 [병합 정렬, 퀵 정렬]
• O(n²): 이차 시간 [버블 정렬, 삽입 정렬]
• O(N³): 삼차 시간 [행렬 곱셈]
• O(2ᴺ): 지수 시간
• O(n!): 팩토리얼 시간

이처럼 빅오 표기법은 최고차항만을 남기고 나머지는 적지 않습니다. 하지만 빅오는 항상 절대적인 것이 아니며, 상수의 값이 엄청 큰 경우 자체적으로 영향력이 커져, 결과간 대소 관계(실행 시간)가 달라질 수 있습니다. 따라서 알고리즘을 선택할 때, 평균 복잡도가 빠르다 하더라도 이런 케이스들이 있기 때문에 잘 고려해야 합니다.

Big-Ｏ는 여러 경우에 대한 성능의 상한을 표기한 것이며, 하한을 표기하는 Big-Ω 표기법도 있습니다 👏

공간 복잡도

공간 복잡도란 프로그램이 메모리를 얼마나 사용하는지를 의미하며, 공간 복잡도에도 동일하게 빅오 표기법을 이용할 수 있습니다. 코딩 테스트와 같은 문제 풀이 환경에서는 메모리 제한이 함께 주어지는데, 이 부분이 공간 복잡도를 의미합니다. 

자바스크립트 시간 측정 ⏰

시간을 측정하는 것은 알고리즘의 효율을 측정하는 가장 기본적인 방법입니다. 자바스크립트에서도 가볍게 프로그램의 수행 시간을 측정할 수 있는데, 바로 Web API로 제공되는 console.time을 사용하는 방법입니다.

console.time('수행시간');

for (let i = 0; i < 1000; i++) {
  for (let j = 0; j < 1000; j++) {}
}

// 수행시간: 3.144ms
console.timeEnd('수행시간');

함수의 인자로 타이머에 이름을 붙여줄 수 있으며, 종료할 때는 console.timeEnd를 사용하면 됩니다. 간단한 로직인 경우에 한해서만 복잡도를 계산하기 편하기에, 자신이 작성한 코드의 수행 시간이 궁금할 때는 이 방법을 사용해서 시간을 측정하면 됩니다.