[알고리즘 이론] 6. 시간복잡도

1. 알고리즘 수행 시간의 척도

알고리즘 수행 시간을 지배하는 것은 반복문입니다.

입력의 크기가 커질수록 반복문이 수행되는 횟수가 알고리즘 수행 시간을 지배하게 되고, 따라서 반복문이 수행되는 횟수로 알고리즘의 수행 시간을 측정합니다.

따라서 이번 시간에는 다양한 알고리즘과, 그 알고리즘의 시간복잡도에 대해서 다루겠습니다.

2. 선형 시간 알고리즘(linear time)

var count = 1
for (i in 1 until N) {
		count *= i
}
for (j in 1 until 50) {
		count += j
}

N의 값이 커짐에 따라 아래의 반복문에서 50만큼 반복하는 것은 크게 고려하지 않아도 됩니다.

따라서 이때 알고리즘의 수행 시간은 N에 정비례합니다.

이렇게 입력값에 정비례하여 수행 시간이 늘어나는 알고리즘을 선형 시간 알고리즘이라고 합니다.

3. 선형 이하 시간 알고리즘(sublinear time)

이진 탐색(binary search)이 대표적입니다. 이진 탐색은 원하는 요소를 탐색할 때 매번 탐색해야 할 분량을 절반으로 나눕니다. 따라서 이 경우 수행 시간은 logN이 됩니다.(이때 밑은 2입니다.)

다만 이미 탐색되어야 하는 배열 혹은 자료가 정렬되어 있어야 합니다.

fun binarySearch(target: Int, arr: IntArray): Int {
    var left = 0
    var right = arr.size-1
    var idx = 0
    while (left <= right) {
        idx = (left+right)/2
        if (arr[idx] == target) {
            return idx
        }
        else if (arr[idx] < target) {
            left = idx + 1
        }
        else {
            right = idx - 1
        }
    }
    return -1
}

이것이 이진 탐색의 메커니즘입니다. 물론 더 짧게 사용할 수도 있습니다.

fun binarySearch(target: Int, arr: IntArray): Int {
    var left = 0
    var right = arr.size-1
    var idx = 0
    while (left <= right) {
        idx = (left+right)/2
        when {
            arr[idx] == target -> return idx
            arr[idx] < target -> left = idx + 1
            else -> right = idx - 1
        }
    }
    return -1
}

4. 다항 시간 알고리즘

반복문의 수행 횟수를 N^2, N^10 등처럼 입력 크기의 다항식으로 표현할 수 있는 알고리즘은 다항 시간 알고리즘이라고 합니다.

5. 지수 시간 알고리즘

입력값 N이 증가할 때마다 수행 시간이 배로 증가하는 알고리즘을 지수 시간 알고리즘이라고 합니다.

예를 들어 옷을 입는다고 가정하겠습니다. 현재는 티셔츠와 바지만 선택하면 되며, 가짓수는 각각 두 개라고 하겠습니다.

그러면 티셔츠 중 A를 입을지 B를 입을지 골라야 하고, 바지 중 A를 입을지 B를 입을지 골라야 합니다. 총 가짓수는 2x2 = 4가 됩니다.

근데 이때 자켓도 두 가지 중에서 골라야 한다고 해봅시다. 그러면 가짓수는 2x2x2가 됩니다.

이때 수행 시간은 2^N이 되며, 지수 시간만큼 수행시간이 걸립니다.

입력값이 증가함에 따라 수행 시간이 압도적으로 커지기 때문에 주의해서 사용해야 합니다.