시간 복잡도

✔오늘 배운 중요한 🔑 point

• 시간 복잡도는 알고리즘이 입력 크기에 따라 실행되는 데 필요한 시간의 증가 속도를 설명한다. 보통 알고리즘의 효율성을 나타내는 중요한 지표 중 하나이며 보통 "Big O 표기법"을 사용하여 표현한다. 쉽게 말해 시간복잡도는 알고리즘의 성능이 좋은지 나쁜지 보여주는 것이다.

🎯 오늘 배운 내용

 

시간 복잡도

시간 복잡도는 알고리즘이 입력 크기에 따라 실행되는 데 필요한 시간의 증가 속도를 설명하며 알고리즘의 효율성을 나타내는 중요한 지표 중 하나이다

 

 

 

Big-O 표기법

Big O 표기법은 알고리즘의 성능을 입력 크기에 대한 상한을 나타낸다.

 

 

O(1): 입력 크기와 상관없이 항상 일정한 실행 시간을 가짐  EXCELLENT

O(log n)은 입력 크기의 로그에 비례하는 실행 시간을 가짐 EXCELLENT

O(n)은 입력 크기에 선형으로 비례하는 실행 시간을 가짐   GOOD

O(n log n)은 입력 크기의 로그에 선형으로 비례하는 실행 시간을 가짐  FAIR

O(n^2)는 입력 크기의 제곱에 비례하는 실행 시간을 가짐.   BAD

O(2^n): 입력 크기의 2의 지수로 비례하는 실행 시간을 가짐  HORRIBLE

O(n!): 입력 크기의 n의 팩토리얼에 비례하는 실행 시간을 가짐  HORRIBLE

 

O(1)

fun getFirstElement(arr: List<Int>): Int? {
    return if (arr.isEmpty()) {
        null
    } else {
        arr[0]
    }
}

fun main() {
    val myArray = listOf(1, 2, 3, 4, 5)
    
    // 시간 복잡도를 가진 함수
    val firstElement = getFirstElement(myArray)
    println("첫 번째 요소: $firstElement")
}

매개변수로 어떤 리스트를 받는지 상관없이 항상 일정한 시간이 소요되는 상수 시간 복잡도

 

 

O(log n) 

fun binarySearch(arr: List<Int>, target: Int): Int {
    var left = 0
    var right = arr.size - 1

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

        if (arr[mid] == target) {
            return mid
        }

        if (arr[mid] < target) {
            left = mid + 1
        } else { 
            right = mid - 1
        }
    }

    return -1
}

fun main() {
    val arr = listOf(1, 3, 5, 7, 9, 11, 13, 15, 17)
    val target = 11
    val index = binarySearch(arr, target)
    if (index != -1) {
        println("${target}은 배열의 ${index} 번째 인덱스에 있음")
    } else {
        println("${target}을 찾을 수 없음")
    }
}

이진 탐색은 입력 크기 n에 대해 O(log n)의 시간 복잡도를 가지며, 각 단계에서 배열을 절반으로 나누므로 로그 시간 안에 대상을 찾을 수 있다.

 

 

O(n)

fun findMax(arr: IntArray): Int {
    var max = Int.MIN_VALUE

    for (num in arr) {
        if (num > max) {
            max = num
        }
    }
    return max
}

fun main() {
    val arr = intArrayOf(3, 7, 2, 10, 5)
    val maxNumber = findMax(arr)
    println("배열의 요소 중 가장 큰 값: $maxNumber")
}

배열의 크기에 관계없이 배열을 한 번씩 순회하므로, 실행 시간은 배열의 크기에 선형적으로 비례한다.
따라서 시간복잡도는 O(n)

 

 

O(n log n)

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

    val middle = arr.size / 2
    val left = arr.copyOfRange(0, middle)
    val right = arr.copyOfRange(middle, arr.size)

    mergeSort(left)
    mergeSort(right)

    merge(left, right, arr)
}

fun merge(left: IntArray, right: IntArray, result: IntArray) {
    var i = 0
    var j = 0
    var k = 0

    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++]
        } else {
            result[k++] = right[j++]
        }
    }

    while (i < left.size) {
        result[k++] = left[i++]
    }

    while (j < right.size) {
        result[k++] = right[j++]
    }
}

fun main() {
    val arr = intArrayOf(38, 27, 43, 3, 9, 82, 10)
    println("정렬 전: ${arr.joinToString()}")

    mergeSort(arr)
    println("정렬 후: ${arr.joinToString()}")
}

배열을 반으로 나누는 데는 재귀 호출이 사용되므로 재귀 호출의 시간복잡도는  O(log n)
병합하는 데는 반복문이 사용되므로 n만큼 반복하니 시간복잡도는 0(n)
따라서 시간복잡도는 둘을 곱한 0(n) * 0(log n) ->  0(n log n)

 

 

O(n^2)

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전: ${arr.joinToString()}")

    bubbleSort(arr)
    println("정렬 후: ${arr.joinToString()}")
}

O(n^2) 시간 복잡도를 가지는 코드 중 하나인 버블 정렬(Bubble Sort) 알고리즘

두 개의 반복문을 사용하여 배열을 순회하고, 인접한 요소를 비교하여 정렬하는 과정을 배열의 크기인 n에 대해 반복한다

외부 루프는 배열의 크기 n에 대해 n-1번 반복 -> n* (n-1)
내부 루프는 최대 n-1번까지 반복 -> n*(n-1)

따라서 시간 복잡도는  n * (n-1) = -> O(n^2).

 

O(2^n)

fun generateSubsets(set: List<Int>): List<List<Int>> {
    val subsets = mutableListOf<List<Int>>()
    val n = set.size

    for (i in 0 until (1 shl n)) {
        val subset = mutableListOf<Int>()

        for (j in 0 until n) {
            if (i and (1 shl j) != 0) {
                subset.add(set[j])
            }
        }

        subsets.add(subset)
    }

    return subsets
}

fun main() {
    val set = listOf(1, 2, 3)
    val subsets = generateSubsets(set)
    
    println("주어진 집합: $set")
    println("생성된 부분집합:")
    for (subset in subsets) {
        println(subset.joinToString())
    }
}

주어진 집합의 원소가 n개일 때, 모든 부분집합의 수는 2^n이므로
이러한 모든 부분집합을 생성하는 과정의 시간 복잡도는  O(2^n)

<출력된 화면에서는 7개만 나온것처럼 보이지만 공집합을 포함해서 8개이다>

 

 

O(n!)

fun permute(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    backtrack(nums, mutableListOf(), BooleanArray(nums.size), result)
    return result
}

fun backtrack(nums: IntArray, currentList: MutableList<Int>, used: BooleanArray, result: MutableList<List<Int>>) {
    if (currentList.size == nums.size) {
        result.add(ArrayList(currentList))
        return
    }

    for (i in nums.indices) {
        if (!used[i]) {
            currentList.add(nums[i])
            used[i] = true
            backtrack(nums, currentList, used, result)
            used[i] = false
            currentList.removeAt(currentList.size - 1)
        }
    }
}

fun main() {
    val nums = intArrayOf(1, 2, 3)
    val permutations = permute(nums)
    
    println("주어진 배열: ${nums.joinToString()}")
    println("생성된 순열:")
    for (permutation in permutations) {
        println(permutation.joinToString())
    }
}

첫번째로 올수 있는 경우의 수는 n , 두번째로 올수 있는 경우의 수는 n-1, 3번째로 올수 있는 경우의 수는 n-3,...... 이런식으로 각 단계에서 가능한 선택지가 n-i이다
 n * (n-1) * (n-2) * ... * 1 = n! 번의 호출이 이루어지므로 시간 복잡도는 O(n!)

 

 

 

🤔 어떻게 활용할까?

시간 복잡도를 활용하는 것은 알고리즘의 성능을 평가하고 선택하는 데 도움이 되기 때문에 시간 복잡도를 고려하여 알고리즘을 선택하여 실행 시간을 최소화시키는 방향으로 코드를 작성해야겠다.

📓 오늘의 한줄

The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle. As with all matters of the heart, you'll know when you find it.

- Steven Paul Jobs -