[알고리즘] 빅오 표기법 (Big O Notation)

 

[알고리즘] 빅오 표기법 (Big O Notation)

빅오는 대략적으로 숫자를 세는 것에 붙인 공식적인 표현입니다.

입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변화하는지 설명하는 공식적인 방법입니다.

빅오는 어떤 함수의 입력값이 늘어나는 것과 함수 실행 시간이 변하는 관계를 의미합니다.

입력의 크기와 실행시간의 관계를 말합니다.

 

 

빅오 표기법(Big O Notation)은 알고리즘의 효율성을 나타내기 위한 수학적 표기법입니다.

주로 알고리즘의 시간 복잡도와 공간 복잡도를 분석할 때 사용됩니다.

빅오 표기법을 이해하면 알고리즘이 얼마나 빠르게 실행되는지, 얼마나 많은 메모리를 사용하는지를 파악할 수 있습니다.

 

 

빅오 표기법의 개요

빅오 표기법은 알고리즘의 성능을 입력 크기 nnn에 따라 나타냅니다.

여기서 중요한 것은 "가장 큰 입력 크기"에 대해 알고리즘이 어떻게 동작하는지입니다.

빅오는 상수나 작은 항목을 무시하고, 가장 빠르게 증가하는 항만 고려합니다.

 

 

 

주요 빅오 표기법과 예시

 

1. 시간 복잡도 (Time Complexity)

시간 복잡도는 알고리즘이 입력 크기(Input Size) n에 대해 실행하는 데 걸리는 시간을 나타냅니다. 빅오 표기법을 사용하여 알고리즘의 최악의 실행 시간을 표현합니다.

 

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

• 입력 크기에 상관없이 항상 일정한 시간이 걸리는 알고리즘.
• 예시: 배열의 첫 번째 요소 접근

 

function getFirstElement(arr) {
    return arr[0];
}

 

 

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

• 입력 크기가 커질수록 시간이 천천히 증가하는 알고리즘.
• 예시: 이진 탐색

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

 

 

3. O(n) - 선형 시간 복잡도

• 입력 크기에 비례하여 시간이 증가하는 알고리즘.
• 예시: 배열 요소의 합 계산

function sumArray(arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

 

 

4. O(n log n) - 선형 로그 시간 복잡도

 

• 병합 정렬이나 퀵 정렬 같은 효율적인 정렬 알고리즘의 시간 복잡도.
• 예시: 병합 정렬

 

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

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

 

 

5. O(n^2) - 이차 시간 복잡도

• 입력 크기의 제곱에 비례하여 시간이 증가하는 알고리즘.
• 예시: 버블 정렬

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

 

 

6. O(2^n) - 지수 시간 복잡도

• 입력 크기가 증가할수록 실행 시간이 급격히 증가하는 알고리즘.
• 예시: 피보나치 수열(재귀적 구현)

 

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

 

 

7. O(n!) - 팩토리얼 시간 복잡도

• 매우 비효율적인 알고리즘으로, 입력 크기가 커질수록 실행 시간이 폭발적으로 증가.
• 예시: 순열 생성

 

function generatePermutations(arr) {
    if (arr.length === 0) return [[]];
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        const rest = generatePermutations(arr.slice(0, i).concat(arr.slice(i + 1)));
        for (let j = 0; j < rest.length; j++) {
            result.push([arr[i]].concat(rest[j]));
        }
    }
    return result;
}

 

 

 

 

2. 공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 입력 크기 n에 대해 사용하는 메모리의 양을 나타냅니다.

빅오 표기법을 사용하여 알고리즘이 최악의 경우에 얼마나 많은 메모리를 사용하는지 표현합니다.

 

O(1) - 상수 공간 복잡도

입력 크기와 무관하게 일정한 메모리 공간을 사용하는 알고리즘입니다.

function constantSpace(arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

 

 

 

O(n) - 선형 공간 복잡도

입력 크기에 비례하여 메모리 공간을 사용하는 알고리즘입니다.

function linearSpace(n) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(i);
    }
    return arr;
}

 

 

 

요약

빅오 표기법은 알고리즘의 효율성을 분석할 때 사용되는 중요한 도구입니다.

다양한 시간 복잡도를 이해하고 알고리즘을 선택할 때 이 지식을 활용하면 더 효율적인 코드 작성을 할 수 있습니다.

각 시간 복잡도의 대표적인 예시를 통해 개념을 이해하고 실제로 어떻게 적용되는지를 살펴보세요.

 

 

• 시간 복잡도(Time Complexity): 알고리즘이 입력 크기 n에 따라 실행하는 데 걸리는 시간.
  • 예: O(1), O(n), O(n^2), O(log n) 등.
• 공간 복잡도(Space Complexity): 알고리즘이 입력 크기 n에 따라 사용하는 메모리 공간.
  • 예: O(1), O(n) 등.

 

빅오 표기법을 사용하면 알고리즘의 효율성을 쉽게 비교할 수 있습니다.

시간 복잡도와 공간 복잡도를 고려하여 최적의 알고리즘을 선택하는 것이 중요합니다.