시간 복잡도 계산 하기

정의

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. (위키백과 출저.)

빅오(Big-O)표기법

알고리즘 실행 시간 분석에 사용되는 대표적인 표기법이다. 최악의 상황을 고려하여 계산하는 표기법이다.

빅오 표기법 종류

1. O(1) :입력 값이 증가하더라도 수행 시간이 변경없다.

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val c = sc.nextInt()
    val result = a + b + c
    println(result)
}

2. O(logN) : 로그 복잡도라 불리며 O(1) 다음으로 빠른 복잡도이다. 이진 탐색의 경우 이에 해당 한다.
3. O(N) : 선형 복잡도로 증가한 입력의 수 만큼 시간이 증가 한다. 보통 1억 6천만 입력까지 1초안에 결과가 나타난다.

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val N = sc.nextInt()

    for (index in 0..N-1) {
        println(index)
    }
}

4. O(N^2) : 2차 복잡도로 입력된 수에 따라 결과는 그 수의 제곱만큼 시간이 늘어난다. 40960의 입력까지 1초안에 수행될 수 있다.

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val N = sc.nextInt()

    for (index in 0..N-1) {
        for (_index in 0..N-1) {
            println(index + _index)
        }
    }
}

5. O(nlogn) : 약 2천만의 입력까지 1초안에 수행될 수 있다.