시간 복잡도(Time Complexity)

시간 복잡도(Time Complexity)

· 알고리즘을 수행하는데 사용되는 연산들의 횟수에 대한 것을 상대적 지표로 나타낸 것

(절대적 시간 X)

· 효율적인 알고리즘 구현

→ 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성

(시간 복잡도는 알고리즘 효율성을 판단하기 위한 지표)

 

시간 복잡도 표기법(점근적 표기법)

· Big-O(빅-오) 표기법 : 최악의 경우를 고려(상한 점근)

→ O(n) : 최악의 경우 n번까지 수행되면 프로그램이 종료

* 최악의 시간까지 고려해야 그에 맞는 대응이 가능

 

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)

 

· O(1) : 상수 시간 알고리즘(constant time algorithm)

- 입력값이 증가하더라도 시간은 일정

→ 입력값의 크기에 상관없이 출력값을 얻어낼 수 있다.

ex) 배열에 있는 항목을 인덱스를 사용하여 접근, 집합 내 요소로의 접근 등

data = [1, 2, 3, 4]

print(data[2])

 

· O(log n) : 로그 시간 알고리즘(logarithmic time algorithm)

- Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가짐

- BST(Binary Search Tree)의 값 탐색 또한 O(log n)의 시간 복잡도를 가진 알고리즘

↳ 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬

ex) 이진 검색 등

data = [1, 2, 3, 5, 8, 22, 34, 55]

for index in range(0, len(data), 3):
    print(data[index])

 

· O(n) : 선형 시간 알고리즘(linear time algorithm)

- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미

- 입력값이 커지면 커질수록 계수의 의미가 점점 없어지기 때문에, 같은 비율로 증가하고 있다면 계수 상관 없이 O(n)으로 표기

ex) 중첩되지 않은 통상의 반복문, 선형 검색, 자연수의 거듭제곱 등

data = [1, 2, 3, 4, 5]

for n in data:
    print(n)

 

· O(nlog n) : n 로그 시간 알고리즘(n logarithmic time algorithm)

ex) 퀵 정렬(Quick Sort) 등

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

 

· O(n^2) : 평방 시간(2차 시간) 알고리즘(quadratic time algorithm)

- 문제 해결 단계의 수가 입력값 n의 제곱으로 증가

- n이 적을 경우에만 사용해야 하는 비효율적인 알고리즘

ex) 이중 반복문, 버블정렬, 삽입정렬, 선택정렬 등

def bubble_sort(l):
    swap = True
    while swap:
        swap = False
        for i in range(len(l) - 1):
            if l[i] > l[i + 1]:
                l[i], l[i + 1] = l[i + 1], l[i]
                swap = True


data = [41, 452, 223, 1, 23, 55, 666]
bubble_sort(data)
print(data)

 

· O(2^n) : 지수 시간 알고리즘(exponential time algorithm)

- n이 하나 증가할 때 마다, 걸리는 시간이 그전보다 2배로 걸리는 알고리즘

ex) 재귀로 구현하는 피보나치 수열

def recursive_fibonacchi(n):
    if n <= 1:
        return n
    else:
        return (recursive_fibonacchi(n - 1) + recursive_fibonacchi(n - 2))
    

steps = 10

# 양수만
if steps <= 0:
    print("음수 X")
else:
    print("직전 숫자와 그 전 숫자의 합이 현재 숫자 : ")
    for i in range(steps):
        print(recursive_fibonacchi(i))

 

· O(n!) : 팩토리얼 시간 알고리즘(factorial time alogrithm)

- 초 지수 시간(super-exponential)

- 시간 복잡도가 가장 큰 알고리즘

from math import factorial

print(factorial(1))
print(factorial(3))
print(factorial(5))
print(factorial(7))

 

- 리스트 자료형과 메서드의 시간 복잡도

 

- 집합(set) 자료형과 메소드의 시간 복잡도

 

- 딕셔너리(Dictionary) 자료형과 메소드의 시간 복잡도