[CS] 시간복잡도와 공간복잡도

coderH·2022년 10월 22일

시간복잡도와 공간복잡도

오늘 다뤄볼 시간복잡도와 공간복잡도는 알고리즘을 평가할 때 사용됩니다.

알고리즘이란 어떤 문제를 해결하기 위한 절차나 방법을 말하며
보통 문제를 풀기 위해 적용할 수 있는 알고리즘은 여러개인 경우가 많기 때문에 실행시간은 짧고, 공간은 적게 차지하는 더 효율적인 알고리즘이 어떤것인지를 판단해야 합니다.

프로그램의 실행은 다양한 요소의 영향을 받기 때문에 절대적인 수치만을 비교하기에는 무리가 있습니다.

따라서 불필요한 요소들은 제외하고 필요한 요소에만 집중하는 점근적 분석(Asymptotic Analysis)을 통해 알고리즘의 성능을 평가합니다.

그럼 점근적 표기법에는 어떠한 종류가 있는지 알아보겠습니다.

점근적 표기법(Asymptotic Notation)의 종류

점근적 표기법에는 대표적으로 빅 오메가, 빅 오, 빅 세타 3가지가 있습니다.

이해를 돕기 위해 위 사진처럼 인풋은 5개의 요소를 가진 배열이며 특정 요소를 찾기 위해 순환한다고 가정해보겠습니다.

빅 오메가 (Big-Ω, Best Case)
빅 오메가는 최선의 경우를 말하며 사진에서는 요소 1을 찾는다고 가정 했을 때의 복잡도를 말합니다.
요소가 첫 번째에 위치해 연산은 한번만 필요하므로 Ω(1)로 표기하게 됩니다.
빅 오 (Big-O, Worst Case)
빅 오는 최악의 경우를 말하는것으로 사진에서 요소 5를 찾는다고 가정한 복잡도를 말합니다.
모든 요소를 순환해야 하므로 인풋 n의 크기와 같다는 의미로 O(n)으로 표기합니다.

대부분의 경우 시간복잡도와 공간복잡도를 표현할 때 빅 오를 사용합니다.
빅 세타 (Big-θ , Average Case)
빅 세타는 빅 오메가와 빅 오의 중간 값으로 평균 값인 요소 3을 찾는다고 가정했을 때의 복잡도를 나타냅니다.
이 경우 θ(log n)과 같은 형식으로 표기하게 됩니다.

그렇다면 이 셋 중 빅 오를 사용하는 이유는 뭘까요?
알고리즘의 연산수는 정확하지 않기 때문에 예측 가능한 범위 내에서
제 시간안에 끝나는것을 보장할 수 있도록 최악의 경우를 고려하기 때문입니다.

시간 복잡도 (Time Complexity)

시간 복잡도는 함수의 실행부터 결과를 반환할 때까지 소요되는 실행시간을 말하며
이는 위에서 말했듯이 다양한 요소의 영향을 받기 때문에 불필요한 요소를 제외하여 판단합니다.
시간 복잡도에서 말하는 불필요한 요소들은 다음과 같습니다.

코드의 라인 수

사용하는 언어의 특성(컴파일언어 or 인터프리터언어)과 컴파일러의 성능

컴퓨터의 하드웨어 성능

대표적인 복잡도

출처: https://www.bigocheatsheet.com/

O(1) - Constant Time
인풋의 크기와 상관없이 바로 결과를 반환할 수 있는 경우이며
객체의 키를 통해 요소를 찾거나 배열의 인덱스로 요소를 찾는 경우가 대표적이고
반복문이 없는 단순연산인 경우를 포함합니다.

O(log n) - Logarithmic Time
인풋크기가 커질수록 복잡도가 증가하지만 그 증가폭이 정비례하지 않는 경우로
이진 탐색 알고리즘이 대표적입니다.
binary search algorithm animation

출처: https://en.wikipedia.org/wiki/Binary_search_algorithm

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;

  while(left <= right) {
    const medium = Math.floor((left + right) / 2);
    if(arr[medium] === target) return medium;

    if(arr[medium] < target) {
        left = medium + 1;
    } else {
        right = medium - 1;
    }
  }
}

O(n) - Linear Time
인풋의 크기에 따라 복잡도 또한 정비례하여 증가하는것으로
배열, 문자열, 또는 1부터 특정 숫자까지 전부 순환하는 경우입니다.
```
// O(n)

const search = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }
    return -1;
};
```
O(n2) - Quadratic time
인풋크기의 제곱만큼 복잡도가 상승하며 2중 for문을 사용하는 경우가 대표적입니다.
또한 퀵 정렬, 버블 정렬, 삽입 정렬 등 정렬관련 알고리즘에서 많이 볼 수 있는 복잡도입니다.
```
function test(n) {
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      // ...some code
    }
  }
}
```
O(2n) - Exponential Time
O(2^n)으로도 표기하며 인풋 크기가 증가하면 복잡도 또한 급격히 증가하기 시작합니다.
재귀함수를 이용한 피보나치의 수를 구할 때가 대표적인 경우입니다.
```
function fibonacci(n) {
    if (n === 0 || n === 1) return n;

    return fibonacci(n-1) + fibonacci(n-2);
};
```
O(n!) - Factorial Time
가장 나쁜 성능을 보여주며 순열을 구하는 알고리즘의 대표적인 시간복잡도입니다.

인풋 사이즈에 따른 연산 횟수 변화

Complexity / Input size 1 10 100
O(1) 1 1 1
O(log n) 0 2 5
O(n) 1 10 100
O(n2) 1 100 10000
O(2n) 1 1024 1.2676506002282294e+30
O(n!) 1 3628800 ❌ Maximum Callstack!

Complexity / Input size	1	10	100
O(1)	1	1	1
O(log n)	0	2	5
O(n)	1	10	100
O(n2)	1	100	10000
O(2n)	1	1024	1.2676506002282294e+30
O(n!)	1	3628800	❌ Maximum Callstack!

공간 복잡도 (Space Complexity)

함수의 실행을 위해 요구되는 공간은 크게 고정 공간과 가변 공간으로 나눌 수 있습니다.

고정 공간은 입력과 출력의 횟수 또는 크기와 관계가 없는 공간을 말하고
가변 공간은 위와 반대로 문제 해결 과정에서 의존해야하는 동적인 공간을 말합니다.

예를 들어, 함수 내부에서 기존 변수에 값을 계속 재할당하는 경우라면 공간 복잡도는 O(1)이며 재귀함수라면 O(n)이 됩니다.

// 공간복잡도가 O(1)인 경우
function foo(n) {
  let result = 0;
  for(let i = 0; i < n; i++) {
    result += i
  }
}

// 공간복잡도가 O(n)인 경우, 재귀함수
function factorial(n) {
  if(n === 1) {
    return 1;
  }

  return n * factorial(n - 1);
}

다만, 현대에는 대용량 시스템이 보편화되어 있어 공간 복잡도보다 시간 복잡도를 중심으로 계산하며 시간 복잡도와 공간 복잡도는 보통의 경우 반비례하는 성격을 가집니다.

아래의 링크는 자료구조와 정렬 알고리즘에 따른 시간 복잡도와 공간 복잡도가 표기되어 있으니 참고하시면 좋을 것 같습니다.

bigocheatsheet