Time Complexity

시간복잡도는 알고리즘의 실행 시간을 표현하는 방법이다. Big O 표기법을 사용해 입력 크기 n에 따른 연산 횟수의 증가율을 나타낸다. 시간 대비 속도로 표현하지 않는 이유는, 같은 작업이어도 컴퓨터의 하드웨어에 따라 속도가 달라지기 때문이다. 따라서 알고리즘의 스피드는 완료까지 걸리는 절차의 수로 결정한다.

O(1)

배열에 index로 접근할 경우 (어떤 크기의 배열이든)1번 만에 접근하므로 시간복잡도를 O(1)로 표현한다.

func printElement(array: [Int]) {
    print(array[0])
}

이 때 시간복잡도를 상수 시간(constant time)으로도 표현한다. n의 크기와 관계 없이 작업을 끝내는데 동일한 횟수의 절차가 걸리기 때문이다.

func printElement(array: [Int]) {
    print(array[0])
    print(array[1])
}

또한, 위와 같은 경우 O(1)의 작업이 2개 들어있다고 해서 O(2)가 되진 않는다. 시간복잡도가 상수 시간이라는 사실에 집중한다.

O(n)

선형 탐색(Linear Search 또는 순차 탐색(Sequential Search))의 경우, 배열에서 특정 요소를 찾기 위해 자리를 하나씩 총 n번 방문한다. 따라서, 크기가 n인 배열에서 선형 탐색의 시간복잡도를 O(n)으로 표현하고, 선형 시간(Linear Time)이라고도 부른다.

func linearSearch<T: Equatable>(array: [T], target: T) -> Int? {
    for (index, element) in array.enumerated() {
        if element == target { return index }
    }
    return nil
}

O(1)이 O(2)가 되지 않는 것처럼, 반복문이 2번 연속으로 있다고 해서 O(2n)이 되지 않는다. 시간복잡도는 작업 자체에 집중한다.

O(n²)

2차 시간(Quadratic Time) 또는 제곱 시간이라고도 하며, 중첩 반복이 있을 때 발생한다. 배열의 각 요소에 대해 n번의 반복을 또 돌기 때문에 n × n번의 절차가 필요한 것이다.

func bubbleSort<T: Comparable>(_ array: inout [T]) {
    for i in 0..<array.count {
        for j in 0..<(array.count-1) {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
}

예시는 버블 정렬이다.

O(log n)

로그 시간(Logarithmic time)이라고도 한다. 대표적으로 이진 탐색(Binary Search)을 가리킬 때 사용한다. 이진 탐색은 크기가 n인 배열에 대해 탐색 시 각 프로세스에서 input을 절반으로 나누기 때문에 배열이 2배로 커지더라도 절차의 횟수는 단 1번만 늘어난다. 따라서 제곱의 반대 개념인 로그로 시간복잡도를 표현한다.

func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        if array[mid] == target { return mid }
        else if array[mid] < target { left = mid + 1 }
        else { right = mid - 1 }
    }
    return nil
}

O(n log n)

로그 선형 시간(Linearithmic)이라고 부르며, 퀵정렬과 병합정렬 설명 시 사용한다. Swift의 sort() 메소드의 시간복잡도도 여기에 해당한다고 한다.

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
   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<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
   var leftIndex = 0
   var rightIndex = 0
   var result: [T] = []
   
   while leftIndex < left.count && rightIndex < right.count {
       if left[leftIndex] <= right[rightIndex] {
           result.append(left[leftIndex])
           leftIndex += 1
       } else {
           result.append(right[rightIndex])
           rightIndex += 1
       }
   }
   
   result.append(contentsOf: left[leftIndex...])
   result.append(contentsOf: right[rightIndex...])
   
   return result
}

예시는 병합정렬이다. 배열을 반으로 나누고(log n) 각 부분을 정렬하면서 병합(n)하기 때문에 n log n으로 표현된다.

사실 이건 병합정렬 자체를 모르기도 하고 무슨 말인지 이해하고 쓴 건 아니고 갖다 붙였다. 나중에 병합정렬을 따로 공부하도록 하겠다.

O(2ⁿ)

지수 시간(Exponential)이다. 재귀 피보나치가 여기에 해당한다.

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

각 단계마다 2개의 재귀 호출이 발생하고, n이 1 증가할 때마다 호출 횟수가 2배씩 증가하기 때문에 2ⁿ으로 표현한다.