알고리즘 빅오 표기법(Big-O notation) 이해하기

빅오 표기법(Big-O Notaion)에 대해 공부한 내용을 파이썬 코드 예제를 통해 정리해보았습니다.

빅오표기법(Big-O Notaion) 이란?

빅오는 알고리즘의 효율성을 평가하기 위해 사용하는 표기법으로, 입력 크기(n)에 대한 실행 시간을 나타내는 시간 복잡도 와 메모리 사용량의 증가를 나타내는 공간 복잡도로 나눌 수 있다.

빅오표기법에서 오는 영어 O ? 숫자 0?

빅오 표기법의 "O"는 영어 알파벳 대문자 “O”를 의미합니다. "Order"의 첫 글자를 딴 것으로, 알고리즘의 시간 복잡도나 공간 복잡도가 입력 크기 n에 대해 어떤 "순서(Order)”로 증가하는지를 나타낸다.

1. O(1): 상수 시간 복잡도

입력 크기에 상관없이(리스트의 길이와 상관없이) 항상 일정한 시간이 걸리는 알고리즘

Copy

L = ['mon','tue','wed','thu','fri']

# 끝에 원소 붙이기 .append(값)
L.append('sat')
L
# 끝에서 삭제하기 .pop()
L.pop()
L 

# 리스트의 길이와 무관하게 할 수 있음 -> 상수시간 O(1)

리스트의 마지막 요소에 원소를 붙이거나, 마지막 원소를 삭제하는 경우는 리스트의 길이와 무관하게 항상 일정한 시간만 소요한다.

2. O(n): 선형 시간 복잡도

입력 크기에 비례하여 실행 시간이 증가하는 경우, 선형 탐색(linear search, 순차탐색 sequential search) 이라고 함.

Copy

L = [20, 37, 58, 72, 91]

# 중간에 원소 삽입 .insert(인덱스위치, 값)
L.insert(4, 24)
L

# 중간에 원소 삭제 del(L[2]) 
del(L[4])
L

# 리스트의 길이에 비례 -> 선형시간 O(n)

특정 요소를 찾는 경우는 최악의 경우 리스트의 모든 요소를 탐색해야 해서 O(n) 의 시간이 소요된다.

3. O(n^2): 이차 시간 복잡도

이중 반복문과 같이 모든 요소를 중첩해서 탐색하는 경우에 발생

Copy

def pairs(L):
    for i in L:
        for j in L:
            print(i, j) # O(n^2)

4. O(log n): 로그 시간 복잡도

이진 탐색(Binary Search)처럼 한 번 비교가 일어날 때마다(입력크기가 커질수록) 리스트 절반으로 줄어드는 경우 (Divide & Conquer)를 의미한다

Copy

def binary_search(L, x):
    idx = -1 
    upper = len(L) -1
    lower = 0

    while lower <= upper: 
        middle = (lower+upper) // 2
        if L[middle] == x: 
            idx = middle   
            return idx
        elif L[middle] < x: 
            lower = middle + 1 
        else:
            upper = middle - 1 
    return -1

5. O(n log n): 선형 로그 시간 복잡도

입력을 나누고 정렬하면서 병합하는 과정이 필요한 병합 정렬(Merge Sort) 알고리즘에서 나타난다.

정렬된 데이터를 합치는 과정에서 O(n), 분할 과정에서 O(log n)의 시간 복잡도를 갖는다.

Copy

# merge 함수는 정의되어있다고 가정

def merge_sort(L):
    if len(L) <= 1:
        return L
    mid = len(L) // 2
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    return merge(legt, right) 

6. O(2^n): 지수 시간 복잡도

입력 크기가 증가할 때, 처리해야 하는 경우의 수가 지수적으로 증가할 경우 발생.

피보나치 수를 재귀적으로 계산할 때 입력 크기 n에 대해 지수적으로 시간이 증가하므로 시간복잡도는 O(2^n) 이다.

Copy

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

7. O(n!): 계승 시간 복잡도

모든 가능한 순열 계산시 발생

시간 복잡도 계산 방법

import time

ts = time.time() # 현재시간을 타임스탬프로 표현
maximum = max(haystack) # 시간 복잡도 구하고자 하는 함수
elapsed = time.time() - ts # 함수 구현 시간 구하기

print("Maximum element = %d, Elapsed time = %.2f" % (maximum, elapsed))