3. 시간 복잡도 (Time Complexity) Codility Lesson 한국어 정리본 (JavaScript ver.)

시간 복잡도란?

시간 복잡도(Time Complexity)를 사용하면 프로그램의 실행 시간을 대략적으로 추정할 수 있다. 정확한 실행 시간을 계산하는 것은 컴파일러, 컴퓨터의 종류, 프로세서 속도 등 여러 요인에 의해 영향을 받기 때문에 매우 복잡하다. 따라서, 우리는 실행 시간의 대략적인 크기(order of magnitude) 를 측정하는 것이 목표이다.

복잡도는 프로그램이 실행할 수 있는 기본 연산(primitive operation) 의 최대 개수로 볼 수 있다. 여기서 기본 연산이란 덧셈, 곱셈, 대입 연산 등을 의미한다. 하지만 모든 연산을 다 고려하는 대신, 프로그램에서 가장 많이 실행되는 지배적인 연산(dominant operation) 에 초점을 맞춘다.

프로그램의 시간 복잡도는 입력 데이터에 따라 달라지며, 보통 입력 데이터의 크기에 의해 결정된다. 예를 들어, 입력이 𝑁 개의 요소를 가진 배열이라면, 프로그램의 실행 시간은 𝑁에 의해 좌우될 것이다.

---

1. 지배적인 연산과 시간 복잡도

다음 예제를 살펴보자.

예제: O(n) (선형 시간 복잡도)

function dominant(n) {
    let result = 0;
    for (let i = 0; i < n; i++) {
        result += 1;
    }
    return result;
}

위 코드에서 result += 1; 연산이 n 번 실행된다. 따라서 이 함수의 시간 복잡도는 O(n) (선형 시간)이다.

시간 복잡도를 나타내는 Big-O 표기법에서 상수 계수(constant factor) 는 무시된다. 즉, 루프가 20 * n 번 실행되든, n / 5 번 실행되든, 시간 복잡도는 여전히 O(n)으로 본다.

---

2. 다양한 시간 복잡도 비교

O(1) (상수 시간 복잡도)

function constant(n) {
    return n * n;
}

이 함수는 항상 일정한 수의 연산을 수행하므로 O(1) (상수 시간)이다.

O(log n) (로그 시간 복잡도)

function logarithmic(n) {
    let result = 0;
    while (n > 1) {
        n = Math.floor(n / 2);
        result += 1;
    }
    return result;
}

이 함수는 n을 반복적으로 2로 나누므로 O(log n) (로그 시간)이다.

O(n) (선형 시간 복잡도)

function linear(n, A) {
    for (let i = 0; i < n; i++) {
        if (A[i] === 0) return 0;
    }
    return 1;
}

최악의 경우 n 번 루프를 실행하므로 O(n) (선형 시간)이다.

O(n²) (이차 시간 복잡도)

function quadratic(n) {
    let result = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            result += 1;
        }
    }
    return result;
}

이중 루프를 사용하여 O(n²) (이차 시간) 복잡도를 갖는다.

O(n + m) (다중 선형 시간 복잡도)

function linear2(n, m) {
    let result = 0;
    for (let i = 0; i < n; i++) {
        result += i;
    }
    for (let j = 0; j < m; j++) {
        result += j;
    }
    return result;
}

여기서는 n과 m에 따라 독립적인 두 개의 루프가 실행되므로 O(n + m) 이다.

O(2ⁿ) (지수 시간 복잡도) 및 O(n!) (팩토리얼 시간 복잡도)

지수 시간과 팩토리얼 시간 복잡도를 가지는 알고리즘은 입력 크기가 조금만 커져도 실행 시간이 급격히 증가하므로, 일반적으로 사용되지 않는다.

---

3. 시간 제한과 예상 복잡도

일반적으로 평균적인 컴퓨터는 1초 안에 약 10⁸ 개의 연산을 수행할 수 있다. 따라서 입력 크기(𝑛)에 따른 예상 복잡도를 다음과 같이 유추할 수 있다.

• 𝑛 ≈ 1,000,000 → O(n) 또는 O(n log n)
• 𝑛 ≈ 10,000 → O(n²)
• 𝑛 ≈ 500 → O(n³)

이는 대략적인 기준이며, 특정 문제에 따라 다를 수 있다.

---

4. 공간 복잡도 (Space Complexity)

공간 복잡도는 프로그램이 실행될 때 필요한 메모리 크기를 의미한다.

• O(1) (상수 공간): 고정된 개수의 변수만 사용할 때
• O(n) (선형 공간): 입력 크기 𝑛 에 비례하는 배열을 사용할 때
• O(n²) (이차 공간): 𝑛×𝑛 크기의 2차원 배열을 사용할 때

특히 재귀(Recursion) 를 사용할 경우, 스택 메모리가 추가적으로 필요하기 때문에 공간 복잡도를 신중히 고려해야 한다.

---

5. 시간 복잡도 계산 예제

문제: 1부터 𝑛까지의 합 계산하기

O(n²) (비효율적인 방법)

function slowSum(n) {
    let result = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= i; j++) {
            result += 1;
        }
    }
    return result;
}

O(n) (선형 시간)

function fastSum(n) {
    let result = 0;
    for (let i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}

O(1) (상수 시간, 최적화된 방법)

function optimizedSum(n) {
    return (n * (n + 1)) / 2;
}

이 방법은 단 하나의 연산만 필요하므로 O(1) (상수 시간)이다.