알고리즘 성능분석을 위한 복잡도 활용법

Computer Science

알고리즘

알고리즘이란, 어떤 목적이나 결과물(프로그램)을 만들어내기 위해 거쳐야 하는 일련의 과정들을 말한다. 어떤 프로그램을 만드는 데 있어서 방법은 여러가지가 있을 수 있다. 예를 들어, 어떤 케익 1개를 100가지 방법으로 자를 수 있는 것처럼, 하나의 문제를 여러가지의 알고리즘으로 풀 수 있다. 그렇기 때문에, 여러 알고리즘 중 최선의 알고리즘으로 하는 것이 좋다.

어떤 프로그램 개발을 위해 코딩을 할 때, 여러가지의 알고리즘으로 풀 수 있지만, 최선의 알고리즘으로 푸는 것이 (웹페이지 등의) 성능을 위해서 좋다. 이때, 이 성능 분석을 위해 필요한 것이 복잡도이다.


복잡도

복잡도에는 크게 2가지가 있다.

  • 시간 복잡도: 알고리즘이 문제를 해결하기 위한 연산의 횟수(얼마나 많은 연산이 수행되는지)
  • 공간 복잡도: 메모리 사용량(얼마나 많은 양의 메모리를 차지하는지)

이런 복잡도를 가지고 작성한 코드 알고리즘의 성능을 분석해서, 어떻게 하면 더 적은 연산으로(시간 복잡도), 더 적은 메모리를 차지하여(공간 복잡도) (웹페이지 등의) 성능을 좋게 할 수 있다.

알고리즘의 성능을 평가하기 위해서는 작성된 코드의 시간복잡도 및 공간복잡도를 계산하고, 이를 점근적 표기법으로 나타내어 평가한다. 이때 점근적 표기법이란, 각 알고리즘이 주어진 데이터의 크기를 기준으로 코드에서의 연산의 횟수 또는 메모리 사용량이 얼마나 되는지를 비교할 수 있는 방법이다. 이 방법에는 Big-O, 오메가, 세타 등이 있다.

이 방법중에서 Big-O 표기법에 대해 알아보자.


Big-O 표기법

Big-O 표기법이란, 계산된 복잡도를 O(n) 이런식으로 표기하는 방식인데, 이때, n은 최고차항의 차수가 된다. 예를 들어, T(n) = n^2+ 2n + 1 으로 시간복잡도가 계산되었다면, O(n^2)으로 표기하는 것이 Big-O 표기법이다.

대표적인 복잡도를 Big-O 표기법으로 작성한 것은 다음과 같다.

  • O(1): 상수 시간
    • 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는 데 오직 한 단계만 거친다.
  • O(logn): 로그 시간
    • 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
  • O(n): 직선적 시간
    • 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.
  • O(n^2): 2차 시간
    • 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.
  • O(c^n): 지수 시간
    • 문제를 해결하기 위한 단계의 수는 주어진 상수값 c의 n 제곱이다.

복잡도의 크기는 다음과 같다.

1
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

보통 O(n^2) 이상의 복잡도를 가지는 알고리즘은 좋지 않다.


복잡도 계산하기

O(1): 상수 시간(constant time)

알고리즘이 문제를 해결하는 데 오직 한 단계만 거친다.

O(1)은 여러가지 경우가 있겠지만, 예를 들면 다음과 같은 코드들이 있다.

1. 전달되는 인자를 반환하는 경우

1
2
3
4
5
function addTwoNumbers(num1, num2) {
  return num1 + num2; // 1번 실행
}

console.log(addTwoNumbers(1, 3)); // 4

시간복잡도를 T(n)이라고 하는데, 위 코드의 시간복잡도를 계산하면 T(n) = 1 이다. 이것을 Big-O 표기법으로 나타내면 O(1)이다. 1인 이유는 Big-O 표기법에서 O(n)의 n은 최고차항의 차수를 나타내는데, 위의 경우 n^0이므로, 1이된다.


2. 정렬되어 있는 배열에서 최소값과 최대값을 구하는 경우

1
2
3
4
5
6
7
8
const numbers = [1, 2, 3, 4, 5, 10]; // 배열의 요소들이 순서대로 정렬되어 있다.
function FindLargestNumber(items) {
  let smallest = items[0]; // 1번 실행
  let largest = items[items.length - 1]; // 1번 실행
  return (largest - smallest); // 1번 실행
}

console.log(FindLargestNumber(numbers)); // 9

위 코드의 시간복잡도를 계산하면 T(n) = 3 이다. 이것을 Big-O 표기법으로 나타내면 O(1)이다.


3. 값을 검색할 때, 객체에서 키를 알거나, 배열에서 인덱스를 알고 있으면 언제나 한 단계만 걸린다.

1
2
3
4
5
6
7
8
9
10
11
function isCryptoCurrency(name) {
  return cryptoCurrency[name]; // 1번 실행
}

var cryptoCurrency = {
  'bitcoin': true,
  'ripple': true,
  'bitcoinCash': true
}

console.log(isCryptoCurrency('bitcoin')); // true

위 코드의 시간복잡도를 계산하면 T(n) = 1 이다. 이것을 Big-O 표기법으로 나타내면 O(1)이다.


O(logN): 로그 시간(log time)

문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면, 검색하는 시간이 줄어든다. 대표적인 것이 이진 검색 알고리즘이다.(binary search)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function findAge(num, array) {
  var midPoint = Math.floor(array.length/2);
  if(array[midPoint] === num) {
    return true; // 1번 실행
  }
  if(array[midPoint] < num) {
    for (let i = midPoint + 1; i < array.length) {
      if(array[i] === num) {
        return true;
      }
    } n/2번 실행
  } else {
    for (let i = 0; i < midPoint) {
      if(array[i] === num) {
        return true;
      }
    } n/2번 실행
  }
}

console.log(findAge(27, sortedAges))
sortedAges = [21, 23, 25, 27, 29];

위 코드의 시간복잡도를 계산하면 T(n) = 1 + n/2 이다. 이것을 Big-O 표기법으로 나타내면 O(logn)이다.


O(n): 직선적 시간(linear time)

문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.

for문을 1번 사용하는 경우

예를 들어, 배열이 정렬되어 있지 않을 경우, 최소 및 최대값을 찾기 위해 배열의 모든 숫자를 탐색하여, 비교를 수행한다. 이 경우, 수행시간은 배열의 크기에 따라 늘어난다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const numbers = [1, 9, 3, 10, 16];
function FindLargestGap(items) {
  let smallest = items[0]; // 1번 실행
  let largest = items[0]; // 1번 실행
  for (let i = 1; i < items.length; i++) {
    if (items[i] < smallest) {
      smallest = items[i];
    } else if (items[i] > largest) {
      largest = items[i];
    }
  } // n번 실행
  return (largest - smallest); // 1번 실행
}

console.log(FindLargestGap(numbers));

위 코드의 시간복잡도를 계산하면 T(n) = 3 + n 이다. 이것을 Big-O 표기법으로 나타내면 O(n)이다.


O(n^2): 2차 시간(quadratic time)

문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.

중첩 for 문을 사용할 경우, 첫번째 for 문의 각 요소(n) x 두번째(안에있는) for 문의 각 요소(n) = n x n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const number = [2, 10, 1, 4, 3, 10, 5];
function FindLargestGap(items) {
  let gap; // 1번 실행
  let maxGap = 0; // 1번 실행
  for (let i = 0; i < items.length; i++) {
    for(let j = 0; j < items.length; j++) {
      gap = items[i] - items[j];
      if (gap < 0) {
        gap = gap * -1;
      }
      if (gap > maxGap) {
        maxGap = gap;
      }
    }
  } // n^2번 실행
  return maxGap; // 1번 실행
}

console.log(FindLargestGap(numbers)); // 9

위 코드의 시간복잡도를 계산하면 T(n) = 3 + n^2 이다. 이것을 Big-O 표기법으로 나타내면 O(n^2)이다.


O(c^n): 지수 시간(exponential time)

문제를 해결하기 위한 단계의 수는 주어진 상수값 c의 n 제곱이다.

지수 시간은 문제를 풀기 위해, 모든 조합과 방법을 시도할 때 사용된다.

예를 들어, 2^n이 걸리는 피보나치 수열이 있다.

1
2
3
4
5
6
7
8
9
function fibonacci(num) {
  if(num === 0) {
    return 0;
  } else if(num === 1) {
    return 1;
  }

  return fibonacci(num - 1) + fibonacci(num - 2);
}

위 코드는 함수가 호출될 때마다, 앞의 두 수에 대한 함수를 호출하기 때문에, 두번씩 호출하게 된다.(구조는 트리로 되어 있다.) 위 코드의 시간복잡도를 계산하면 T(n) = 2^n 이다. 이것을 Big-O 표기법으로 나타내면 O(2^n)이다.


Worst Case, Best Case, and Average Case

시간 복잡도 계산을 위한 연산 횟수를 카운팅할때, 3가지의 시나리오가 있다.

  • Worst Case: 입력값 n의 규모가 동일할 때, 가장 많은 횟수의 연산으로 처리되는 경우
  • Best Case: 입력값 n의 규모가 동일할 때, 가장 적은 횟수의 연산으로 처리되는 경우
  • Average Case: 입력값 n의 규모가 동일할 때, 평균적인 횟수의 연산으로 처리되는 경우

예를 들면 다음과 같은 코드가 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
function getNumber7(items) {
  for (let i = 0; i < items.length; i++) {
    if (i === 7) {
      return i
    }
  }
}

getNumber7(numbers)

// numbers = [7, 5, 3, 1]인 경우, 1번만 실행(Best Case)
// numbers = [5, 7, 3, 1]인 경우, 2번만 실행
// numbers = [1, 3, 5, 7]인 경우, 4번 모두 실행(Worst Case)