자료구조와 알고리즘 복잡도 분석

고성욱·2023년 3월 31일

개발 CS

목록 보기

8/8

시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘 실행 속도의 측정치입니다. 보통 연산 횟수를 계산합니다. 이 연산 횟수는 입력의 크기에 따라 달라지기 때문에 입력 크기(n)를 기준으로 표기합니다.

Big O 표기법

Big O 표기법은 알고리즘의 수행 시간을 나타내는 표기법 중 하나입니다. 알고리즘의 최악 시간 복잡도를 나타냅니다. 여기서 최악 시간 복잡도란, 입력값 n에 대해 알고리즘이 가장 오래 걸리는 경우의 연산 횟수를 의미합니다. Big O 표기법은 입력값 n이 무한대로 커질 때, 알고리즘의 실행 시간이 어떤 함수 f(n)보다 빠르게 증가하지 않는다는 것을 나타냅니다.

자료구조와 알고리즘 복잡도 예시

배열(Array)

접근 시간: O(1)
검색 시간: O(n)
삽입 시간: O(n)
삭제 시간: O(n)

연결 리스트(Linked List)

접근 시간: O(n)
검색 시간: O(n)
삽입 시간: O(1)
삭제 시간: O(1)

이진 탐색 트리(Binary Search Tree)

접근 시간: O(log n)
검색 시간: O(log n)
삽입 시간: O(log n)
삭제 시간: O(log n).

해시 테이블(Hash Table)

접근 시간: O(1)
검색 시간: O(1)
삽입 시간: O(1)
삭제 시간: O(1)

정렬 알고리즘(Sorting Algorithm)

// 샘플 코드: 정렬 알고리즘 시간 복잡도 측정하기
fun main() {
    val n = 1000000
    val lst = (0 until n).toList()

    val startTime = System.currentTimeMillis()

    // 접근 연산
    val x = lst[0]

    // 검색 연산
    val y = n - 1 in lst

    // 삽입 연산
    val newList = lst.toMutableList()
    newList.add(n)

    // 삭제 연산
    newList.removeAt(newList.lastIndex)

    // 선택 정렬
    selectionSort(lst)

    // 삽입 정렬
    insertionSort(lst)

    // 버블 정렬
    bubbleSort(lst)

    // 합병 정렬
    mergeSort(lst)

    // 퀵 정렬
    quickSort(lst)

    // 힙 정렬
    heapSort(lst)

    val endTime = System.currentTimeMillis()

    println("모든 연산에 걸린 시간: ${endTime - startTime} ms")
}

// 선택 정렬
fun selectionSort(lst: List<Int>): List<Int> {
    val result = lst.toMutableList()
    for (i in result.indices) {
        var minIndex = i
        for (j in i + 1 until result.size) {
            if (result[j] < result[minIndex]) {
                minIndex = j
            }
        }
        val temp = result[i]
        result[i] = result[minIndex]
        result[minIndex] = temp
    }
    return result
}

// 삽입 정렬
fun insertionSort(lst: List<Int>): List<Int> {
    val result = lst.toMutableList()
    for (i in 1 until result.size) {
        val key = result[i]
        var j = i - 1
        while (j >= 0 && result[j] > key) {
            result[j + 1] = result[j]
            j -= 1
        }
        result[j + 1] = key
    }
    return result
}

// 버블 정렬
fun bubbleSort(lst: List<Int>): List<Int> {
    val result = lst.toMutableList()
    for (i in 0 until result.size - 1) {
        for (j in 0 until result.size - i - 1) {
            if (result[j] > result[j + 1]) {
                val temp = result[j]
                result[j] = result[j + 1]
                result[j + 1] = temp
            }
        }
    }
    return result
}

// 합병 정렬
fun mergeSort(lst: List<Int>): List<Int> {
    if (lst.size <= 1) {
        return lst
    }
    val middle = lst.size / 2
    val left = lst.subList(0, middle)
    val right = lst.subList(middle, lst.size)
    return merge(mergeSort(left), mergeSort(right))
}

fun merge(left: List<Int>, right: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < left.size && j < right.size) {
        if (left[i] < right[j]) {
            result.add(left[i])
            i++
        } else {
            result.add(right[j])
            j++
        }
    }
    result.addAll(left.subList(i, left.size))
    result.addAll(right.subList(j, right.size))
    return result
}

// 퀵 정렬
fun quickSort(lst: List<Int>): List<Int> {
    if (lst.size <= 1) {
        return lst
    }
    val pivot = lst[lst.size / 2]
    val equal = lst.filter { it == pivot }
    val less = lst.filter { it < pivot }
    val greater = lst.filter { it > pivot }
    return quickSort(less) + equal + quickSort(greater)
}

// 힙 정렬
fun heapSort(lst: List<Int>): List<Int> {
    val result = lst.toMutableList()
    for (i in result.size / 2 - 1 downTo 0) {
        heapify(result, result.size, i)
    }
    for (i in result.size - 1 downTo 1) {
        val temp = result[0]
        result[0] = result[i]
        result[i] = temp
        heapify(result, i, 0)
    }
    return result
}

fun heapify(lst: MutableList<Int>, n: Int, i: Int) {
    var largest = i
    val l = 2 * i + 1
    val r = 2 * i + 2
    if (l < n && lst[l] > lst[largest]) {
        largest = l
    }
    if (r < n && lst[r] > lst[largest]) {
        largest = r
    }
    if (largest != i) {
        val swap = lst[i]
        lst[i] = lst[largest]
        lst[largest] = swap
        heapify(lst, n, largest)
    }
}

위 코드는 Kotlin을 사용하여 서로 다른 정렬 알고리즘의 시간 복잡도를 측정하는 예시입니다. 코드는 리스트의 접근, 검색, 삽입, 삭제 연산의 시간, 그리고 선택 정렬, 삽입 정렬, 버블 정렬, 합병 정렬, 퀵 정렬, 힙 정렬의 시간 복잡도를 측정합니다.

각 정렬 알고리즘의 시간 복잡도는 다음과 같습니다:

선택 정렬: O(n^2)
삽입 정렬: O(n^2)
버블 정렬: O(n^2)
합병 정렬: O(n log n)
퀵 정렬: O(n log n)
힙 정렬: O(n log n)

같은 문제에 대해 적절한 알고리즘을 사용하면 더 나은 성능과 효율성을 얻을 수 있습니다. 따라서 알고리즘을 설계할 때 시간 복잡도 분석을 고려하는 것이 중요합니다.

아래는 파이썬의 리스트를 예시로, 리스트의 길이에 따른 연산 시간을 측정하는 코드입니다.

import time

n = 1000000
lst = [i for i in range(n)]

start = time.time()

# Access operation
x = lst[0]

# Search operation
y = n - 1 in lst

# Insert operation
lst.append(n)

# Delete operation
del lst[-1]

end = time.time()

print("Elapsed time for list operations: ", end - start)

이 코드는 리스트를 사용하는 연산 중 접근, 검색, 삽입, 삭제 연산의 시간을 측정합니다. 리스트의 길이(n)를 바꿔가며 시간을 측정하여, 각각의 연산이 얼마나 오래 걸리는지를 확인할 수 있습니다.