[Kotlin] 시간 복잡도(Time Complexity)

Data Structures & Algorithms in Kotlin 예제 코드를 이용하여 시간 복잡도를 알아보자 !

 

 

 

 

 

 

 

 

 

* 시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. *

 

시간 복잡도는 주로 빅-오(Big-O) 표기법을 사용하며 나타낸다.

 

 

 

 

 

 

 

 

빅 오 표기법의 종류

• O(1)
• O(n)
• O(log n)
• O(n2)
• O(2n)

 

 

 

 

• O(1) : 일정한 복잡도로, 입력값이 증가하더라도 시간이 늘어나지 않는다.
• O(n) : 선형 복잡도로, 입력값이 증가함에 따라 시간도 같은 비율로 증가한다.
• O(log n) : 로그 복잡도로, O(1) 다음으로 빠른 시간 복잡도를 가진다.
• O(n2) : 2차 복잡도로, 입력값이 증가함에 따라 시간이 n 제곱수 만큼 증가한다.
• O(2n) : 기하급수적 복잡도로, 빅오 표기법 중 가장 느린 시간 복잡도이다.

 

 

 

 

 

 

 

 

 

1. 상수 시간(Constant Time)

 

- 하나의 연산이 어떤 배열에서 요소 위치를 알아내는 것을 수행하고자 할 때, 이 요소에 접근하는 것은 상수 시간이 걸린다. 

- O(1) 시간이 소요

 

fun checkFirst(names: List<String>) {
    if (names.firstOrNull() != null) {
        println(names.first())
    } else {
        println("no names")
    }
}

 

 

 

 

 

 

 

 

 

 

2. 선형 시간(Linear Time)

- 리스트의 모든 요소를 더하는 프로시저는 리스트의 길이에 비례하는 시간을 요구한다.

- O(n)시간이 소요

 

fun printNames(names: List<String>) {
    for (name in names) {
        println(name)
    }
}

 

 

 

 

 

 

 

 

 

3. 2차 시간(Quadratic Time)

- O(n2) 시간이 소요

 

fun multiplicationBoard(size: Int) {
    for (number in 1..size) {
        print("|")
        for (otherNumber in 1..size) {
            print("$number x $otherNumber = ${number*otherNumber} |")
        }
        println()
    }
}

 

 

 

 

 

 

 

 

 

 

4. 로그 시간(Logarithmic Time)

- 이진트리, 이진 탐색에서 찾아볼 수 있다.

- O(log n) 시간이 소요

 

 

val numbers = listOf(1, 3, 56, 66, 68, 80, 99, 105, 450)

fun linearContains(value: Int, numbers: List<Int>): Boolean {
    for (element in numbers){
        if (element == value) {
            return true
        }
    }
    return false
}

 

 

 

 

 

5. 유사 선형 시간(Quasilinear Time)

- O(n log n) 시간이 소요