[Algorithm] 시간 복잡도와 점근적 표기법

알고리즘의 성능과 효율성을 판단할 때 주로 시간 복잡도를 가장 중요하게 생각합니다. 이번 글에서는 시간 복잡도가 무엇인지와 시간 복잡도를 단순화하여 표현하는 점근적 표기법(빅 오, 리틀 오, 빅 세타, 빅 오메가, 리틀 오메가)에 대해 알아보겠습니다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

시간 복잡도(Time Complexity)

알고리즘의 복잡성(효율성 혹은 성능)은 알고리즘 수행에 소모되는 자원의 양으로 판단됩니다. 여기서 자원은 소요 시간, 메모리, 통신대역 등이 될 수 있지만 가장 중요하게 생각되는 판단 기준은 소요 시간입니다. 메모리는 돈으로 어느 정도 해결 할 수 있지만 시간은 돈으로 살 수 없으니까요.

알고리즘의 시간 복잡도(소요 시간)는 입력 크기에 대한 함수로 표현할 수 있습니다. 아래 코드는 입력 n이 주어졌을 때 1부터 n까지 모든 자연수를 더하는 두개의 알고리즘을 파이썬으로 구현한 예시입니다. 두 개의 알고리즘을 살펴보고 각각의 시간 복잡도를 n에 대한 함수로 표현해 봅시다.

# 알고리즘 1
sum = 0
for i in range(1, n+1):
    sum += i

# 알고리즘 2
sum = n * (n+1) / 2

알고리즘이 어느 정도의 시간 복잡도를 갖는지 어떻게 계산할 수 있을까요? 알고리즘은 많은 연산들의 조합으로 이루어지고 연산이 수행될 때 시간이 소모됩니다. 즉, 입력 n에 따른 연산의 횟수로 알고리즘의 시간 복잡도를 표현할 수 있습니다. 모든 연산을 세면 더 정확하겠지만 입력이 충분히 크다면 지배적인 연산의 횟수가 다른 연산의 횟수를 압도합니다. 여기서 지배적인 연산이란 전체 연산에서 가장 많은 비율을 차지하는 연산을 의미합니다. 위 예시에서는 덧셈 연산이 지배적인 연산이 되겠네요. 두 알고리즘의 지배적인 연산(덧셈 연산)의 횟수를 입력 n에 대한 함수로 나타내 보면 아래와 같습니다.

$$\begin{align*}f_1(n)&=n+1\\f_2(n)&=1\end{align*}$$

알고리즘 1은 n+1번 덧셈 연산을 수행하고 알고리즘 2는 입력과 관계없이 항상 1번의 덧셈 연산을 수행합니다. 두 알고리즘의 입력의 크기에 따른 시간 복잡도를 비교해 봅시다.

입력 (n)	알고리즘 1 ($f_1$)	알고리즘 2 ($f_2$)
1	2	1
$10^8$	100,000,001	1
$10^{10}$	10,000,000,001	1

입력이 1이라면 덧셈 연산이 각각 2번, 1번 수행되므로 눈 깜짝할 사이 끝나버려 알고리즘의 성능을 비교하는데 큰 의미가 없을 것입니다. 1억 번의 덧셈연산을 수행하는데 1초가 걸린다고 가정한다면 입력이 1억이라면 알고리즘 2는 여전히 찰나의 시간에 결과를 내지만 알고리즘 1은 1초가 걸릴 것입니다. 입력이 100억이라면 두 알고리즘의 차이가 확연하게 드러나겠죠. 이렇듯 알고리즘의 복잡도는 입력의 크기가 커질수록 중요해집니다. 따라서 알고리즘의 시간 복잡도를 비교할 때는 충분히 큰 입력에 대해서 비교하는 것이 의미 있습니다. 여기서 '충분히 큰'이란 '차이가 의미를 가질 만큼 큰'입니다. 입력 n이 충분히 크다고 가정하는 것은 고등학교 교육과정에서 배운 함수의 극한과 비슷합니다. 

$$\lim_{n\to\infin}f_2(n)\space<\space\lim_{n\to\infin}f_1(n)$$

충분히 큰 n에 대해 알고리즘 2의 시간 복잡도가 알고리즘 1의 시간 복잡도보다 작으므로 알고리즘 2가 더 효율적이라고 할 수 있습니다.

 

점근적 표기법

알고리즘의 시간 복잡도는 입력에 대한 함수로 계산될 수 있고 이렇게 계산된 함수는 충분히 큰 입력에서 의미를 갖는다고 했습니다. 함수의 극한을 생각해 보면 인자(argument)가 충분히 커진다면 최고차항을 제외한 항들은 최고차항의 증가 속도에 압도되어 무시할 수 있게 됩니다.(함수의 모든 항을 최고차항으로 나누면 최고차항을 제외한 나머지 항은 0으로 수렴합니다.) 따라서 충분히 큰 입력에서 시간 복잡도는 최고차항으로만 표기해도 비교에 무리가 없습니다. 시간 복잡도는 입력이 충분히 큰 경우에서 비교하는데 입력이 충분히 크다면 최고차항만 비교해도 비교 결과는 같을 테니까요.

이렇게 시간 복잡도의 최고차항만 표기하는 방법을 `점근적 표기법`이라 합니다. 점근적 표기법은 입력이 충분히 크다는 전제하에 입력의 증가에 따른 복잡도의 증가율을 나타내는 것이기 때문에 최고차항의 계수도 무시합니다. 입력에 따른 복잡도의 증가율을 의미하는 계수가 1인 최고차항은 `점근적 증가율`이라 합니다.

 

Big $\Theta$ notation

$\Theta(f(n))$은 점근적 증가율이 $f(n)$인 모든 함수의 집합입니다.

$$\begin{align*}\Theta(g(n))=\lbrace f(n)\space|&\space충분히\space큰\space모든\space n에\space대하여\\&\space c_1g(n)\le f(n)\le c_2g(n)을\space만족하는\\&\space양의\space상수\space c_1, c_2가\space존재한다.\rbrace\end{align*}$$

 

시간 복잡도가 $f(n)$인 알고리즘의 점근적 증가율이 $g(n)$이라면 $f(n)\in\Theta(g(n))$입니다.

$$\text{if} \lim_{n\to\infin}f(n)\approx g(n),\space\text{then}\space f(n)\in\Theta(g(n))$$

 

예를 들어 $n^2, 7n^2, 3n^2+7n, 8n^2+\log n$과 같이 점근적 증가율이 $n^2$인 함수들은 $\Theta(n^2)$의 원소입니다.

$$\Theta(n^2)=\lbrace n^2, 7n^2, 3n^2+7n, 8n^2+\log n, ...\rbrace$$

 

점근적 표기법에서 사용되는 빅세타, 빅오, 빅오메가 등은 집합이기 때문에 집합기호로 써야 하지만 편의상 등호를 사용합니다. 하지만 여전히 집합이기에 교환법칙은 성립하지 않습니다.

$$\begin{align*}5n^2&\in\Theta(n^2)\\5n^2&=\Theta(n^2)\\\Theta(n^2)&\ne5n^2\end{align*}$$

 

Big $\Omicron$ notation

점근적 표기법에는 많은 표기법이 있으나 가장 많이 사용되는 표기법은 빅오 표기법입니다.

$\Omicron(f(n))$은 점근적 증가율이 $f(n)$보다 크지 않은 모든 함수의 집합입니다.

$$\begin{align*}\Omicron(g(n))=\lbrace f(n)\space|&\space충분히\space큰\space모든\space n에\space대하여\\&\space f(n)\le cg(n)을\space만족하는\\&\space양의\space상수\space c가\space존재한다.\rbrace\end{align*}$$

 

예를 들어 $n,7n^2,3n^3-7n^2,8n^2+\log n$과 같이 점근적 증가율이 $n^3$을 넘지 않는 함수들은 $\Omicron(n^3)$의 원소입니다.

$$\Omicron(n^3)=\lbrace n,7n^2,3n^3-7n^2,8n^2+\log n,...\rbrace$$

빅오는 점근적 증가율의 상한을 의미합니다. 상한을 아주 넉넉하게 잡을 수도 딱 맞게 잡을 수도 있겠죠.

 

Little $\omicron$ notation

$\omicron(f(n))$은 점근적 증가율이 $f(n)$보다 작은 모든 함수의 집합입니다.

넉넉하게 잡은 상한은 리틀오($\omicron(f(n))$)로 표기합니다. 빅오에서 등호가 빠진 거죠.

$$\begin{align*}\Omicron(g(n))=\lbrace f(n)\space|&\space충분히\space큰\space모든\space n에\space대하여\\&\space f(n) < cg(n)을\space만족하는\\&\space양의\space상수\space c가\space존재한다.\rbrace\end{align*}$$

 

Big $\Omega$ notation

$\Omega(f(n))$은 점근적 증가율이 $f(n)$보다 작지 않은 모든 함수의 집합입니다.

$$\begin{align*}\Omega(g(n))=\lbrace f(n)\space|&\space충분히\space큰\space모든\space n에\space대하여\\&\space f(n)\ge cg(n)을\space만족하는\\&\space양의\space상수\space c가\space존재한다.\rbrace\end{align*}$$

예를 들어 $n, 7n^2, 3n^3-7n^2, 8n^2+\log n$과 같이 점근적 증가율이 $n$보다 크거나 같은 함수들은 $\Omicron(n)$의 원소입니다.
$$\Omega(n)=\lbrace n, 7n^2, 3n^3-7n^2, 8n^2+\log n, ...\rbrace$$

빅오메가는 점근적 증가율의 하한을 의미합니다. 하한을 아주 넉넉하게 잡을 수도 딱 맞게 잡을 수도 있겠죠. 

 

Little $\omega$ notation

$\omega(f(n))$은 점근적 증가율이 $f(n)$보다 큰 모든 함수의 집합입니다.

넉넉하게 잡은 하한 리틀오메가($\omicron(f(n))$)로 표기합니다. 빅오메가에서 등호가 빠진 거죠.

$$\begin{align*}\Omega(g(n))=\lbrace f(n)\space|&\space충분히\space큰\space모든\space n에\space대하여\\&\space f(n) < cg(n)을\space만족하는\\&\space양의\space상수\space c가\space존재한다.\rbrace\end{align*}$$

 

정리

알고리즘의 효율성을 평가하는 가장 중요한 지표는 알고리즘이 수행되는데 소요되는 시간인 `시간 복잡도`입니다. 시간 복잡도는 알고리즘에서 지배적인 연산의 횟수를 입력에 대한 함수로 나타내어 표현합니다. 이때 입력의 크기가 충분히 크다면 함수의 최고차항이 증가율에 미치는 영향은 최고차항을 제외한 나머지 항과 최고차항의 계수를 무시할 정도로 큽니다. 따라서 계수가 1인 최고차항으로 시간 복잡도를 표현해도 의미가 같고 이렇게 표현하는 방법을 `점근적 표현법`, 표현된 식(계수가 1인 최고차항)을 `점근적 증가율`이라 합니다.

점근적 표기법에는 빅세타, 빅 오, 리틀 오, 빅 오메가, 리틀 오메가 등이 있으며 정의는 다음과 같습니다.

표기법	충분히 큰 모든 n에 대하여 다음을 만족하는 $c_i$가 존재
$\Theta(g(n))$	$c_1g(n)\le f(n)\le c_2g(n)$
$\Omicron(g(n))$	$f(n)\le c_0g(n)$
$\omicron(g(n))$	$f(n)<c_0g(n)$
$\Omega(g(n))$	$f(n)\ge c_0g(n)$
$\omega(g(n))$	$f(n)>c_0g(n)$