시간 복잡도의 개념

시간 복잡도에 대한 개념 정리

0. 시간 복잡도란?

• 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도.
• 일반적으로 점근 표기법을 사용해 표기.

1. 시간 복잡도의 종류

O(1) : 상수 시간

• 입력 데이터의 크기와 관계없이 항상 일정한 시간이 걸림.
• 해시 테이블의 조회 및 삽입.

적용 사례

• 배열 / 스택 / 큐에서의 삽입 및 삭제.

예시

function constant(data) {
	return data[0]
}

O(log n) : 로그 시간

• 데이터의 크기가 커져도, 그에 비례해서 실행 시간이 증가하지 않고 로그 함수에 따라 증가.
• 정렬되어 있지 않은 배열 같은 곳엔 사용할 수 없음.

적용 사례

• 이진 검색.
• 이진 트리의 조회 및 삽입.
• 힙의 삽입 및 삭제.

예시

let i = n;
while (i > 1) {
    i /= 2;
}

O(n) : 선형 시간

• 입력 데이터의 크기에 비례해서 알고리즘의 실행 시간이 증가.

적용 사례

• 선형 검색.
• 단일 반복문.
• 외에 대부분의 정렬이 아닌 알고리즘.

예시

for (let i = 0; i < n; i++) {
    console.log(i);
}

O(n log n) : 선형 로그 시간

• 데이터를 정렬하는데 필요한 대표적인 최선의 경우.

적용 사례

• 고급 정렬 알고리즘(병합 정렬, 힙 정렬, 퀵 정렬).
• 힙 구성.

예시

for (let j = 0; j < n; j++) {
    let i = arr[j];
    while (i > 1) {
        i /= 2;
    }
}

O(n^2) : 제곱 시간

• 입력 데이터의 제곱에 비례해서 알고리즘의 실행 시간이 증가.
• O(n^3) 등등, 이런 식으로 계속 진행.

적용 사례

• 이중 반복문.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        console.log(i, j);
    }
}

O(2^n) : 팩토리얼 시간

• 매우 큰 입력값에 대해 매우 비효율적.

적용 사례

• 피보나치 수열.
• 모든 부분 집합의 탐색.

예시

function fibonacci(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

O(n!): 지수 시간

• 모든 순열을 생성해야 하는 경우에 사용.

적용 사례

• 외판원 문제의 완전 탐색 해법.
• 순열 생성.

예시

function getPermutations(array) {
    if (array.length === 0) return [[]];
    let permutations = [];
    for (let i = 0; i < array.length; i++) {
        let rest = array.slice(0, i).concat(array.slice(i + 1));
        for (let subPermutation of getPermutations(rest))
            permutations.push([array[i]].concat(subPermutation));
    }
    return permutations;
}
console.log(getPermutations([1, 2, 3]));

2. 시간 복잡도 개선 방법

동적 프로그래밍

• 복잡한 문제를 여러 개의 문제로 나누어 푸는 방법.
• 이미 계산된 부분 문제의 해답을 저장하고 재활용함으로써
  중복 계산을 피하고, 실행 시간을 개선.

예시

// 피보나치 수열 계산 최적화
function fibonacci(n) {
    let fib = [0, 1];
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

분할 정복

• 문제를 더 작은 문제로 분활한 뒤 각각 해결하고, 이를 합쳐서 문제를 해결하는 방법.

예시

// 병합 정렬
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) {
        result.push(left.shift());
    }
    while (right.length) {
        result.push(right.shift());
    }
    return result;
}

3. 그리디 알고리즘

• 각 단계에서 최적이라고 생각되는 선택을 함으로써 전체에서의 최적해를 찾는 방법.

// 거스름돈 문제
function changeMoney(money, coins) {
    coins.sort(function(a, b) {return b - a});
    let result = 0;
    for (let i = 0; i < coins.length; i++) {
        if (money == 0) {
            break;
        }
        let count = Math.floor(money / coins[i]);
        money -= count * coins[i];
        result += count;
    }
    return result;
}

etc

• '시간 복잡도'라는 이름 때문인지 걸리는 시간에 따라 달라지는 건 줄 알았는데,
  과정에 따라 달라진다라는 걸 깨달았다.
• 추가로 '공간 복잡도'라는 것도 고려해야 한다는데 머리가 아프다.