Big O 표기법

Big O 표기법이란?

알고리즘의 시간 복잡도(Time Complexity) 와 공간 복잡도(Space Complexity) 를 분석하는 방법이야. 즉, 입력 크기(n)가 커질 때, 알고리즘의 실행 시간(또는 메모리 사용량)이 어떻게 증가하는지 표현하는 방법이야!

Big O 표기법을 배워야 되는 이유

버블 정렬 (Bubble Sort) → O(n²) (느림)
퀵 정렬 (Quick Sort) → O(n log n) (빠름)

같은 정렬 알고리즘이라도 정렬 속도에 차이가 생김. 따라서 어떤 알고리즘을 사용해야 될 지 알 수 있음.

O(n) → 1,000,000번 연산
O(n²) → 1,000,000,000,000번 연산 (매우 느림!)

입력 값이 커짐에 따라 연산 속도에 차이가 생김. 값이 커질 수록 속도가 얼마나 느려질 지 예측 가능.

시간 복잡도

입력 크기(n)와 관계없이 항상 일정한 시간이 걸리는 경우

int arr[] = {1, 2, 3, 4, 5};
int x = arr[0];  // O(1)

탐색 범위가 매번 절반으로 줄어들기 때문에 O(log n)

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

최악의 경우 모든 요소를 검사해야 하므로 O(n)

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

재귀적으로 분할하면서 정렬하기 때문에 O(n log n)

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

이중 반복문이 있으므로 O(n²)

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

재귀적으로 모든 경우를 탐색하기 때문에 O(2ⁿ)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

시간 복잡도 비교

O(1)      → 초고속 (항상 일정한 시간)
O(log n)  → 매우 빠름 (이진 탐색)
O(n)      → 보통 (배열 순회)
O(n log n)→ 효율적 정렬 (퀵 정렬, 병합 정렬)
O(n²)     → 느림 (버블 정렬)
O(2ⁿ)     → 매우 느림 (재귀적 피보나치)
O(n!)     → 극도로 느림 (순열)

Big O 계산법

반복문이 있으면 O(n)

for (int i = 0; i < n; i++) { ... }  // O(n)

중첩 반복문이 있으면 O(n²)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) { ... }  // O(n²)
}

이진 탐색처럼 절반씩 줄어들면 O(log n)

while (low <= high) {
    mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}  // O(log n)