시간 복잡도란?
알고리즘의 효율성은 알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 나타낼 수 있습니다. 이들을 각각 시간복잡도, 공간복잡도로 나타낼 수 있습니다.
시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 비례한 함수로 표현합니다.
예를 들어, 숫자 카드가 10장이 있고 이 중에서 최대 숫자를 찾는데, 순차 탐색으로 찾는 경우에 숫자 비교가 기본적인 연산이고, 숫자 비교가 9번입니다.
숫자 카드가 만약에 n장이 있다면, 숫자 비교는 n -1 번을 하므로 n -1이 시간복잡도가 됩니다.
▶ 복잡도를 표현하는 방법
- 최악 경우 분석
'어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'라는 상한(Upper Bound)의 의미
보통 최악의 경우로 시간복잡도를 나타냅니다.
- 평균 경우 분석
입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등 분포(Uniform Distribution)를 가정
- 최선 경우 분석
가장 빠른 수행 시간을 분석하며, 최적(Optimal) 알고리즘을 찾는데 활용
- 상각 분석
일련의 연산을 수행하여 총 수행 시간을 합하고 이를 연산 횟수로 나누어 수행 시간을 분석
[조건]: 알고리즘에서 적어도 두 종류의 연산이 수행되고, 그 중 하나는 수행 시간이 길고, 다른 하나는 짧으며, 수행 시간이 짧은 연산은 많이 수행되고, 수행 시간이 긴 연산은 적게 수행되어야 상각 분석이 의미를 갖는다.
※ 복잡도를 표현하는 방법은 시간복잡도 표기와는 상관이 없습니다.
(최악의 경우라고 해서 무조건 O-표기를 사용하거나, 그런 경우는 없다는 겁니다.)
▶ 시간복잡도의 점근적 표기
입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
1) O(Big-Oh) 표기
점근적 상한을 나타내는 표기입니다.
복잡도가 위와 같다면, f(n)의 O-표기는 O(n^2)입니다.
단순화된 함수 n^2에 임의의 상수 c를 곱한 cn^2이 n이 증가함에 따라 f(n)의 상한이 됩니다. (단, c >0)
위 그림에서 c = 3이라면, 교차점 n = n0일 때 이후부터는 f(n)은 cn^2보다 절대로 커질 수가 없습니다. c값이 정해진 값이 아니더라도 교차점 이후 상한 관계를 만족하는 c가 존재한다면, f(n) = O(n^2)으로 표기할 수 있습니다.
(따라서 O-표기에는 c가 숨겨져있다고 생각하면 쉬울 겁니다.)
상한 관계를 가지고 있어야 f(n)의 O-표기로 채택될 수 있습니다.
f(n) ≠ O(nlogn), O(logn), O(n) 입니다.
상한 관계를 따져보면 cnlogn의 그래프, clogn의 그래프, cn의 그래프는 f(n)보다 큰 그래프가 아닙니다.
하지만 f(n) = O(2^n), O(n^3) 입니다.
위처럼 상한관계를 따져 봤을 때, f(n)의 그래프보다 위에 있기 때문입니다.
2) Ω(Big-Omega) 표기
Ω-표기는 O-표기와 반대로 점근적 하한 표기입니다.
f(n) = 2n^2 8n + 3 의 시간복잡도 표기는 Ω-표기로 Ω(n^2)입니다. 점근적 하한인데 왜 O-표기와 같은 거지? 하실 수 있는데
'n이 증가함에 따라 f(n)이 cn^2보다 작을 수 없다' 라는 의미로 점근적 하한인 것입니다.
이때 상수 c = 1로 놓으면 됩니다.
위에서 O-표기에서는 f(n) ≠ O(nlogn), O(logn), O(n) 였지만,
Ω-표기에서는 f(n) = Ω(nlogn), Ω(logn), Ω(n) 이 성립합니다. (어떤 c를 선택하면, f(n)보다 작게 만들 수 있기 때문입니다.)
하지만 점근적 하한 의미에 따라 f(n)은 Ω(2^n), Ω(n^3) 으로 표기할 수 없습니다. (어떤 c를 선택해도 f(n)보다 작게 만들 수 없기 때문입니다.)
위 그래프와 같이 그려진다면, f(n)을 Ω(g(n)) 으로 표기할 수 있습니다.
3) θ (Theta) 표기
θ-표기는 O-표기와 Ω-표기가 같은 경우에 사용합니다. 따라서 아까 위에서 구했을 때 O-표기와 Ω-표기가 n^2으로 같았죠? 이렇게 같을 경우, f(n) = θ(n^2) 으로 나타낼 수 있습니다.
즉, 'f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다' 라는 의미입니다.
O-표기와 Ω-표기가 달랐던 n, nlogn, n^3, 2^n은 θ-표기로 나타낼 수 없습니다.
그림으로 나타내면 위와 같습니다.
g(n) n0보다 큰 모든 n에 대해서 c = c1일 때는f(n)보다 작지만, c = c2일 때는 f(n)보다 큽니다.
---연습문제---
<각각 O-표기로 나타내기>
1) 10000
2) 4logn - 9
3) 2nlogn+3n+logn-7
4) 3n^3 + 5n - 7n + 16
1) O(1)
2) O(logn)
3) O(nlogn)
4) O(n^3)
▶ 복잡도는 주로 O-표기로
시간복잡도는 알고리즘에서 보통 일반적으로 O-표기를 사용합니다.
실제로는 주로 θ-표기로 나타낼 수 있는 표기를 O-표기로 나타낸다고 생각하면 됩니다.
(즉, f(n)을 O-표기와 Ω-표기로 나타냈을 때 같은 표기를 그냥 O-표기로 나타냅니다.)
다음은 컴퓨터 분야에서 시간복잡도를 위해 자주 사용하는 O-표기들입니다.
▢ O(1) - 상수 시간
▢ O(logn) - 로그(대수) 시간
▢ O(n) - 선형 시간
▢ O(nlogn) - 로그 선형 시간
▢ O(n^2) - 이차 시간
▢ O(n^3) - 3차 시간
▢ O(2^n) - 지수 시간
상수 시간 O(1)은 입력 크기 n에 대하여 변하지 않고 일정한 시간이 걸립니다. 즉, 아무리 자료 크기가 크더라도 일정한 시간이 걸린다는 겁니다.
+ 함수의 증가율 비교
오류나 오타 지적 언제든 환영입니다. :)