프로그램 코드의 시간 복잡도(Time Complexity)

프로그램의 수행 시간 체크를 위해서 일반적으로 사용하는 시간 복잡도(time complexity)를 다룬다.
비교를 위해서 가장 일반적인 Big O 표기법을 사용한다.

먼저 프로그램 시간 복잡도를 Big O 표기법으로 구해보자.

def is_unique (alist : [int]) -> bool:
    copy = list(alist)       O(N)
    copy.sort()       O(N Log N) - for Python sorting
    for i in range(len(alist)-1):       O(N) - really N-1, but that is O(N)
        if copy[i] == copy[i+1]:      O(1): 2 [i] (each O(1)) and == ints O(1)
            return False       O(1) - never executed in worst case
    return True         O(1)

O(N) + O(N Log N) + O(N)*O(1) + O(1)
= O(N + N Log N + O(N*1) + 1)
= O(N + N Log N + N + 1)
= O(N Log N + 2N + 1)
= O(N Log N)

* 몇 가지 연산 성질들이 있으며, 직관하는 바와 유사할 것이다.

자주 사용되는 시간 복잡도와 알고리즘 예제들이다.

이름	Big O 표기	알고리즘 예제
constant time	O(1)
logarithmic time	O(log n)	이진 검색
linear time	O(n)	정렬되지 않은 배열에서 최대/최소값 찾기
linearithmic time	O(n log n)	머지 소트
quadratic time	O(n²)	버블 소트
cubic time	O(n³)	NxN 행렬의 곱
exponential time	O(cⁿ) c > 1	연쇄 행렬 곱셈 문제
factorial time	O(n!)	외판원 문제

각 요소별 n의 크기 증가에 따른 복잡성의 증감을 시각화 해 보자.

from math import log2, factorial

import pandas as pd

n = 20

X = range(1,n + 1)

tc = pd.DataFrame({'1.log(n)' : [ log2(x) for x in X ]

,'2.n' : X

,'3.nlog(n)' : [ n*log2(x) for x in X ]

,'4.n**2' : [ x**2 for x in X ]

,'5.n**3' : [ x**3 for x in X ]

,'6.2**n' : [ 2**x for x in X ]

,'7.n!' : [ factorial(x) for x in X ]

})

tc.index = X

tc.plot(lw=4,ylim=(0,300))

legend(loc=(.7,.37))

전체 동향 확인을 위해서 y축에 로그를 반영해 보았다.

tc.plot(lw=4,logy=True)

* 참고로 log₂ n 는 2를 몇 번 곱해야 n이 되는가를 뜻한다.