Swift 시간복잡도 빅오(Big-O) 주요 예제

시간복잡도는 알고리즘이 특정 작업을 수행하는 데 필요한 연산 횟수를 입력 크기에 따라 표현한 것입니다. 입력 크기가 증가하면 알고리즘이 얼마나 더 느려지는지 평가하는 데 사용됩니다. 이를 통해 효율적인 알고리즘을 설계하거나 선택할 수 있습니다.

 

 

---

1. 시간복잡도 표기법: 빅오(Big-O) 표기법

시간복잡도는 **입력 크기(n)**에 따라 알고리즘의 성능을 표현합니다.
**빅오 표기법(Big-O Notation)**은 입력 크기가 커질수록 가장 중요한(가장 빠르게 증가하는) 항만 남기는 방식입니다.

주요 빅오 표기법

1. O(1) - 상수 시간

• 입력 크기와 관계없이 항상 일정한 시간.
• 예시: 배열에서 인덱스를 이용해 값을 바로 찾기.
   

let value = array[3] // O(1)

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

• 입력 크기가 증가해도 처리 시간이 느리게 증가.
• 예시: 이진 탐색.
   

func binarySearch(array: [Int], key: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == key {
            return mid
        } else if array[mid] < key {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

 

3. O(n) - 선형 시간

• 입력 크기에 비례해 처리 시간이 증가.
• 예시: 배열에서 특정 값 찾기(Linear Search).

func linearSearch(array: [Int], key: Int) -> Int? {
    for (index, value) in array.enumerated() {
        if value == key {
            return index
        }
    }
    return nil
}

4. O(n²) - 이차 시간

• 입력 크기가 증가하면 시간이 제곱으로 증가.
• 예시: 이중 반복문을 사용하는 버블 정렬.

func bubbleSort(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)
            }
        }
    }
}

5. O(2ⁿ) - 지수 시간

• 입력 크기가 증가할 때 처리 시간이 기하급수적으로 증가.
• 예시: 재귀 호출을 사용하는 피보나치 수열 계산.
   

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fibonacci(n - 1) + fibonacci(n - 2) // O(2ⁿ)
}

---

2. 시간복잡도 분석 방법

알고리즘의 시간복잡도를 분석하려면 다음 단계를 따릅니다.

1) 기본 연산을 찾기

• 알고리즘에서 가장 빈번하게 실행되는 작업을 찾습니다.
  예: 비교, 할당, 반복문 실행 등.

2) 입력 크기(n)에 따른 연산 횟수 표현

• 반복문, 재귀 호출 등의 실행 횟수를 입력 크기(n)로 나타냅니다.

3) 가장 큰 항만 남기기

• 입력 크기가 매우 커질 때 지배적인 항만 남기고, 계수(상수)는 제거합니다.

예제

func exampleFunction(array: [Int]) {
    for i in 0..<array.count { // O(n)
        for j in 0..<array.count { // O(n)
            print(array[i] + array[j]) // O(1)
        }
    }
}

1. 외부 반복문: n번 실행.
2. 내부 반복문: 외부 반복문마다 n번 실행.
3. 총 연산 횟수: n×n=n2n×n=n2.
4. 시간복잡도: O(n²).

---

3. 실생활 비유로 이해하기

• O(1): 직접 서랍에서 원하는 물건을 꺼내는 것.
• O(n): 서랍을 처음부터 끝까지 열어가며 원하는 물건을 찾는 것.
• O(n²): 각 서랍을 두 번씩 열어가며 모든 물건을 비교하는 것.
• O(log n): 정렬된 서랍에서 중간부터 시작해 물건을 찾는 것.

---

4. 효율적인 알고리즘 선택

• 문제의 입력 크기(n)가 크다면, 시간복잡도가 작은 알고리즘을 선택하세요.
• 빅오 표기법은 최악의 경우를 기준으로 하기 때문에 평균적인 실행 시간도 고려해야 합니다.
• 현실적인 상황에서는 시간복잡도뿐만 아니라 코드의 가독성과 구현 용이성도 중요합니다.