빅 오(big-O)

해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.

빅오(big-O)

점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 표기법 중 하나이다. 점근적 실행시간을 달리 말하면 시간 복잡도(Time Complexity)라고 부를 수 있으며, 사전적 정의는 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도(computational Complexity)를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 Big-O이다.

빅오로 시간복잡도를 표한혈 때 최고차항만 표기하며, 계수는 무시한다.

종류	의미
$O(1)$	입력값이 아무리 커도 실행시간은 일정하다. 최고의 알고리즘이 될 수 있지만 그만큼 신중해야 한다.
$O(log_n)$	매우 큰 입력값에도 크게 영향을 받지 않는다.
$O(n)$	선형 시간(Linear-Time) 알고리즘. 입력값만큼 실행 시간에 영향을 받음
$O(nlog_n)$	병렬 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다.
$O(n^2)$	버블 정렬같은 비효율적인 정렬 알고리즘
$O(2^n)$	피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당. $O(n^2)$보다 훨씬 더 크다.
$O(n!)$	각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(TSP)를 브루트 포스로 풀이할 떄 이에 해당. 가장 느린 알고리즘으로 입력값이 조금만 커져도 웬만한 다항시간 내에 계산이 어렵다.

다음은 $n^2$와 $2^n$의 차이를 보여주는 코드이다.

for n in range(1, 15+1):
    print(n, n**2, 2**n)

out:
1 1 2
2 4 4
3 9 8
4 16 16
5 25 32
6 36 64
7 49 128
8 64 256
9 81 512
10 100 1024
11 121 2048
12 144 4096
13 169 8192
14 196 16384
15 225 32768

빅오는 시간 복잡도 이외에도 공간 복잡도를 표현하는데 널리 쓰인다. 알고리즘은 ‘시간과 공간이 트레이드 오프(Space-Time Tradeoff)’ 관계다. 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다는 이야기이다.

상한과 최악

• 빅오(O)는 상한(Upper Bound), 빅오메가(Ω)는 하한(Lowder Bound), 평균을 의미하는 빅세타(Θ)
• 복잡한 함수가 있을 때, 이 함수가 가장 빨리 실행될 때가 하한(Ω), 가장 늦게 실행될 때가 상한(O)
• 학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐 단순화하려는 경향
• 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행시간의 상한을 나타낸다.

분할 상환 분석(Amortized Analysis)

알고리즘의 복잡도를 계산할 떄, 최악의 경우만 살펴보는 것은 지나치게 비관적인 이유로 등장하게 되었다. 최악의 경우를 여러번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다.

병렬화

일부 알고리즘들은 병렬화로 실행 속도를 높혀줄 수 있다. 딥러닝의 인기와 GPU의 발전에 따라 병렬 연산 알고리즘이 최근 큰 주목을 받고 있다.