[Algorithm] Big-O Notation

알고리즘의 중요한 개념인 Big-O 표기법에 대해 정리하였습니다.

---

< Big-O Notation >

Big-O 표기법(Big-O Notation)은 알고리즘의 효율성을 표현하는 방법으로, 주로 입력 크기(n)에 따른 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 데 사용됩니다. 이를 통해 알고리즘이 실행될 때 얼마나 많은 리소스를 사용하는지 대략적으로 평가할 수 있습니다.

Big-O Notation에서 상수는 항상 무시합니다.

 

 

---

< 시간 복잡도(Time Complexity) >

시간 복잡도(Time Complexity)는 알고리즘이 완료되는 데 걸리는 시간을 나타내는 지표로, 주어진 입력 크기(n)에 대한 연산의 수를 평가합니다.

 

 

---

[ O(1) : 상수 시간 복잡도]

: 입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우입니다.

 

Ex)

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

: 위 함수는 배열의 첫 번째 요소를 반환합니다. 배열의 크기와 무관하게 항상 일정한 시간이 걸리므로 O(1) 시간 복잡도를 가집니다.

 

 

---

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

: 입력 크기가 커질수록 시간 증가가 로그 함수와 같은 경우입니다

 

Ex)

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

: 이진 탐색은 정렬된 배열에서 값을 찾기 위해 중간 요소와 비교하여 범위를 절반씩 줄여 나갑니다. 따라서 O(log n) 시간 복잡도를 가집니다.

 

 

---

[ O(n): 선형 시간 복잡도 ]

: 입력 크기에 비례하여 시간이 증가하는 경우입니다.

 

Ex)

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

: 위 함수는 배열에서 특정 값을 찾기 위해 모든 요소를 검사합니다. 배열의 크기가 커질수록 반복 횟수가 증가하므로 O(n) 시간 복잡도를 가집니다.

 

 

---

[ O(n log n): 로그 선형 시간 복잡도 ]

: 입력 크기 n과 로그 n의 곱에 비례하는 시간 증가입니다.

 

Ex)

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

: 병합 정렬은 배열을 반으로 나누어 각각 정렬한 후 병합합니다. 이 과정은 O(n log n) 시간 복잡도를 가집니다.

 

 

---

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

: 중첩된 반복문으로 인해 입력 크기의 제곱에 비례하여 시간이 증가하는 경우입니다.

 

Ex)

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]) {
                // Swap
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

: 버블 정렬은 배열을 정렬하기 위해 중첩된 반복문을 사용하므로 O(n^2) 시간 복잡도를 가집니다.

 

 

---

[ O(2ⁿ): 지수 시간 복잡도 ]

: 입력 크기 n에 대해 지수적으로 시간이 증가하는 경우입니다.

 

Ex)

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

: 피보나치 수열을 재귀적으로 계산할 때, 동일한 부분 문제를 여러 번 계산하므로 O(2^n) 시간 복잡도를 가집니다.

 

 

---

[ O(n!): 팩토리얼 시간 복잡도 ]

: 입력 크기 n의 팩토리얼에 비례하여 시간이 증가하는 경우입니다.

 

Ex)

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 perm of rest) {
            result.push([arr[i]].concat(perm));
        }
    }
    return result;
}

: 주어진 배열의 모든 가능한 순열을 생성하기 위해 각 요소에 대해 재귀적으로 순열을 계산하므로 O(n!) 시간 복잡도를 가집니다.

 

 

---

< 시간 복잡도(Time Complexity) >

공간 복잡도는 알고리즘이 완료되는 데 필요한 메모리 공간을 나타냅니다. 시간 복잡도와 마찬가지로 입력 크기 n에 대한 함수로 표현됩니다. 예를 들어, 배열을 사용하는 경우 O(n)의 공간 복잡도를 가질 수 있습니다.

 

 

---

Ex1 : 선형 검색(Linear Search)

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

Ex2 : 병합 정렬(Merge Sort)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

• 시간 복잡도: O(n log n)
• 공간 복잡도: O(n)