시간 복잡도(Time Complexity) 공부하기

알고리즘을 공부하면서 '시간 복잡도(Time Complexity)'라는 개념이 얼마나 중요한지 자주 마주하게 된다. 시간 복잡도는 알고리즘이 주어진 입력을 처리하는 데 걸리는 시간을 나타내는 개념으로, 이를 이해하면 알고리즘의 효율성을 평가하는 데 큰 도움이 된다. 이번에는 시간 복잡도가 무엇인지, 그리고 왜 중요한지에 대해 깊이 있게 공부해보자.

시간 복잡도란?

시간 복잡도는 알고리즘이 어떤 입력을 받았을 때, 그 입력을 처리하는 데 걸리는 시간을 나타낸다.

주로 입력 크기(input size)에 대한 함수로 표현되며, 입력이 커질수록 알고리즘이 얼마나 더 오래 걸리는지를 설명해준다.

시간 복잡도 표기법 - Big-O 표기법

시간 복잡도는 보통 Big-O 표기법을 사용해 표현한다. 이 표기법은 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 변하는지, 가장 빠르게 증가하는 항만을 고려해서 나타낸다. 주로 사용되는 Big-O 표기법의 예시는 다음과 같다:

• O(1): 입력 크기와 상관없이 항상 일정한 시간이 걸림 (예: 배열의 첫 번째 요소 접근)
• O(log n): 입력 크기가 커질수록 시간이 느리게 증가함 (예: 이진 탐색)
• O(n): 입력 크기에 비례해서 시간이 증가함 (예: 단순 반복문)
• O(n^2): 입력 크기의 제곱에 비례해서 시간이 증가함 (예: 중첩 반복문)

시간 복잡도의 대표적인 예시들 (출처: 위키피디아)

시간 복잡도를 이해하기 위한 예시

예를 들어, 숫자 리스트에서 가장 큰 숫자를 찾는 알고리즘을 생각해보자. 리스트가 길어질수록 비교해야 할 숫자가 많아지기 때문에, 시간 복잡도는 리스트의 길이에 비례하게 된다.

function findMax(arr: Array): Int {
    var max = arr[0]
    for (i in 1 until arr.size) {
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    return max
}
    

위 코드에서 리스트의 길이가 n이라면, 최대 n-1번 비교를 해야 가장 큰 수를 찾을 수 있다. 그래서 이 알고리즘의 시간 복잡도는 O(n)이다.

시간 복잡도 계산 예시 - Kotlin으로 작성하기

다양한 시간 복잡도를 가진 알고리즘을 Kotlin 코드로 작성해보고, 그 시간 복잡도를 분석해보자.

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

fun getFirstElement(arr: Array): Int {
    return arr[0]
}
    

이 함수는 입력 배열의 첫 번째 요소를 반환한다. 배열의 크기와 상관없이 항상 동일한 시간에 실행되므로 시간 복잡도는 O(1)이다.

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

fun printAllElements(arr: Array) {
    for (element in arr) {
        println(element)
    }
}
    

이 함수는 배열의 모든 요소를 출력한다. 배열의 크기 n에 비례하여 반복 횟수가 늘어나므로 시간 복잡도는 O(n)이다.

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

fun printPairs(arr: Array) {
    for (i in arr.indices) {
        for (j in arr.indices) {
            println("${arr[i]}, ${arr[j]}")
        }
    }
}
    

이 함수는 배열 내 모든 요소의 쌍을 출력한다. 두 개의 중첩된 반복문이 사용되었기 때문에, 시간 복잡도는 O(n^2)이다.

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

fun binarySearch(arr: Array, target: Int): Int? {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = (left + right) / 2

        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return null
}
    

이 함수는 이진 탐색 알고리즘을 구현한 것이다. 배열이 정렬되어 있다는 가정 하에, 입력 크기가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)이다.

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

fun mergeSort(arr: Array): Array {
    if (arr.size <= 1) return arr

    val mid = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until mid))
    val right = mergeSort(arr.sliceArray(mid until arr.size))

    return merge(left, right)
}

fun merge(left: Array, right: Array): Array {
    var indexLeft = 0
    var indexRight = 0
    val newArray: ArrayList = ArrayList()

    while (indexLeft < left.size && indexRight < right.size) {
        if (left[indexLeft] <= right[indexRight]) {
            newArray.add(left[indexLeft])
            indexLeft++
        } else {
            newArray.add(right[indexRight])
            indexRight++
        }
    }

    newArray.addAll(left.slice(indexLeft until left.size))
    newArray.addAll(right.slice(indexRight until right.size))

    return newArray.toTypedArray()
}
    

이 함수는 병합 정렬 알고리즘을 구현한 것이다. 병합 정렬은 입력 크기를 반으로 나누고, 각 부분을 재귀적으로 정렬하여 합치는 과정이므로 시간 복잡도는 O(n log n)이다.

 

다양한 시간 복잡도를 가진 알고리즘을 직접 구현해보면서, 각각의 시간 복잡도가 어떻게 계산되는지 이해하는 것이 중요한 것 같다.