2025.01.16 Today I Learned

시간 복잡도와 빅오표기법 (Big-O Notation)

1. 빅오 표기법

빅오 표기법은 알고리즘이 처리해야 할 입력 크기(Input Size)에 따라 실행 시간이 어떻게 변하는지 설명한다. 주로 최악의 경우를 기준으로 성능을 측정하며, 입력크기(n)가 커질 때 실행 시간이나 자원 사용량의 상한선을 나타낸다.

빅오 표기법의 기본 구조

O(f(n))

여기서 f(n)은 입력 크기 n에 따른 실행 시간 또는 작업 횟수의 함수이다.

 

2. 시간 복잡도

시간 복잡도는 알고리즘이 특정 입력 크기에 대해 얼마나 오래 실행되는지를 나타낸다. 일반적으로 아래의 단계를 따라 계산한다.

1. 기본 연산 찾기: 알고리즘의 핵심 작업(예: 비교, 할당)을 확인한다.
2. 연산 횟수 분석: 입력 크기에 따라 기본 연산이 얼마나 자주 실행되는지 분석한다.
3. 최악의 경우 고려: 최악의 입력 상황에서의 실행 시간을 기준으로 복잡도를 측정한다.
4. 최고 차항 유지: 입력 크기가 커질 때 실행 시간에 가장 큰 영향을 미치는 요소만 남긴다.

3. 주요 시간 복잡도 예제

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

입력 크기에 상관 없이 실행 시간이 일정하다.

// 예제: 첫 번째 요소 반환
let arr = [1, 2, 3, 4]
prit(arr[0]) // O(1)

 

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

입력 크기가 커질수록 실행 시간이 느리게 증가한다. 보통 이진 탐색에서 나타난다.

// 예제: 이진 탐색
func binarySearch(arr: [Int], target: Int) -> Int? {
    var low = 0
    var high = arr.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

 

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

입력 크기에 비례하여 실행 시간이 증가한다.

// 예제: 배열의 합 계산
let arr = [1, 2, 3, 4, 5]
let sum = arr.reduce(0, +)
print(sum)

 

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

데이터를 분할하고 각각을 처리할 때 발생한다. 주로 효율적인 정렬 알고리즘에서 나타난다.

// 예제: 병합 정렬
func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }

    let mid = array.count / 2
    let left = mergeSort(Array(array[..<mid]))
    let right = mergeSort(Array(array[mid...]))

    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result: [Int] = []
    var i = 0, j = 0

    while i < left.count && j < right.count {
        if left[i] < right[j] {
            result.append(left[i])
            i += 1
        } else {
            result.append(right[j])
            j += 1
        }
    }

    return result + left[i...] + right[j...]
}

 

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

중첩 루프가 있는 경우 발생하며, 입력 크기가 클수록 실행 시간이 급격히 증가한다.

// 예제: 버블 정렬
func bubblerSort(_ array: inout [Int]) {
    for i in 0..<array.count {
        for j in 0..<(array.count - i - 1) {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
}

 

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

입력 크기가 증가할수록 실행 시간이 급격히 증가한다. 보통 재귀 호출이 많은 문제에서 나타난다.

// 예제: 피보나치 수열 계산
func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

 

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

모든 가능한 경우를 탐색해야 하는 문제에서 많이 나타난다. 보통 순열 생성 문제가 이에 해당한다.

// 예제: 순열 생성
func permutations<T>(_ array: [T]) -> [[T]] {
    guard array.count > 1 else { return [array] }

    var result: [[T]] = []

    for i in 0..<array.count {
        let element = array[i]
        let remaining = Array(array[0..<i] + array[(i + 1)...])
        let subPermutations = permutations(remaining)

        result += subPermutations.map { [element] + $0 }
    }

    return result
}

 

4. 빅오 표기법 최적화

1. 데이터 구조 선택: 문제에 적합한 데이터 구조(예: 해시맵, 트리 등)를 사용한다.
2. 중복 계산 제거: 동적 프로그래밍(Dynamic Programming)을 활용하여 동일한 계산을 반복하지 않도록 한다.
3. 분할 정복: 문제를 더 작은 부분으로 나누어 처리한다.
4. 필요 없는 연산 제거: 루프 내에서 불필요한 계산을 피한다.

5. 시간복잡도 비교

빅오 표기법	이름	실행 예제(입력 크기 n = 10)
O(1)	상수 시간 복잡도	1
O(log n)	로그 시간 복잡도	3
O(n)	선형 시간 복잡도	10
O(n log n)	선형 로그 시간 복잡도	30
O(n^2)	이차 시간 복잡도	100
O(2^n)	지수 시간 복잡도	1024
O(n!)	팩토리얼 시간 복잡도	3,628,800