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;
    }

    여기서는 nm에 따라 독립적인 두 개의 루프가 실행되므로 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) (상수 시간)이다.

    반응형

    댓글