직접 구현하지 않고도 알고리즘의 효율성을 따져볼 수 있는 "알고리즘 복잡도 분석" 방법에는 2가지의 측면을 고려할 수 있습니다. 바로 "알고리즘의 수행시간"과 "알고리즘이 필요로 하는 기억공간의 양"입니다. 알고리즘의 수행시간을 고려하는 분석을 "시간 복잡도"라고 하며, 기억공간의 양을 고려하는 분석은 "공간 복잡도"라고 합니다.
이번 포스팅에서는 알고리즘의 수행시간을 다루는 "시간 복잡도"에 대해서 포스팅해보도록 하겠습니다.
시간 복잡도(Time Complexity)
시간 복잡도는 알고리즘을 이루는 연산들이 몇 번이나 수행되는지를 숫자로 표시합니다. 즉, 시간 복잡도는 "연산의 횟수"에 관심을 가지는 것이며 절대적인 알고리즘 수행 시간을 나타내는 것이 아닙니다.
Q: 만약에 시간 복잡도가 알고리즘의 절대적인 수행 시간을 측정하는 것이면 어떻게 되나요?
A: 하드웨어마다 수행 속도가 다르기에 정확한 속도를 측정할 수 없을 것입니다. 또한 절대적인 수행 시간을 측정하기 위해서는 완성된 프로그램이 필요하기에 속도를 측정하기에 불편함이 있을 것입니다. (직접 구현하지 않고 알고리즘을 측정하고자 하는 "알고리즘 복잡도 분석" 방식에 어긋납니다.)
최선, 최악, 평균의 경우
알고리즘의 효율성을 평가할 때는 3가지의 경우로 나누어서 평가합니다.
최선의 경우(Best Case), 최악의 경우(Worst Case), 평균적인 경우(Average Case)
- 최선의 경우(Best Case): 알고리즘의 수행시간이 가장 적게 걸리는 경우를 의미합니다.
- 최악의 경우(Worst Case): 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 의미합니다.
- 평균적인 경우(Average Case): 알고리즘의 모든 입력을 고려한 후, 입력이 발생하는 확률을 고려해 평균 수행시간을 구합니다,.
시간 복잡도 표기법 (빅오, 빅오메가, 빅세타)
시간 복잡도를 표기하는 방법으로는 "빅오 표기법(Big-O)", "빅오메가 표기법(Big-Omega)", "빅세타 표기법(Big-Theta)"이 있습니다.
- Big-O(빅오 표기법): 시간의 상한을 표기한 방법으로, 특정 알고리즘의 최악의 경우 시간 복잡도를 나타냅니다.
- Big-Ω(빅오메가 표기법): 시간의 하한을 표기한 방법으로, 특정 알고리즘의 최선의 경우 시간 복잡도를 나타냅니다.
- Big-
3개의 표기법 중에서 가장 정밀한 것은 당연히 "빅세타 표기법"입니다. "빅오 표기법"과 "빅세타 표기법"을 주로 사용합니다. 그 중에서도 통상적으로는 "빅오 표기법"을 주로 사용합니다. 그 이유는 알고리즘을 분석할 때 최악의 경우를 주로 고려하기 때문입니다.
빅오 표기법(Big-O Notation)
시간의 상한을 표기하는 빅오 표기법은 어떤 식으로 시간 복잡도를 나타내는지 알아봅시다.
빅오 표기법의 수학적 정의
두 개의 함수 \(f(n)\)와 \(g(n)\)이 주어졌을 때 모든 \(n > n_0\)에 대하여 \( |f(n)| \leqq c|g(n)| \)을 만족하는 2개의 상수 \(c\)와 \(n_0\)가 존재하면 \(f(n) = O(g(n))\)이다.
입력의 개수 n과 n에 관한 시간 복잡도 함수의 관계는 상당히 복잡할 수 있습니다.
에를 들어 시간 복잡도 함수 \(T(n) = n^2 +3n + 2\) 라 가정해보면 \(n\)이 커질수록 최고차항을 제외한 나머지 항들의 숫자 기여도는 생각보다 크지 않습니다. 즉, \(n\)의 숫자가 커질수록 최고차항에 비해 다른 항들의 크기는 미비하다는 뜻입니다.
"빅오 표기법"은 이와 같이 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘을 쉽게 할 목적으로 시간 복잡도를 표기하는 방법입니다. 빅오 표기법은 최고차항 이외의 항들과 최고차항의 계수까지도 무시하여 오직 "최고차항의 차수"만을 주목하는 방식입니다.
빅오 표기법에 의한 알고리즘 수행 시간 비교
빅오 표기법은 "입력의 개수"에 따른 연산의 수행 횟수를 대략적으로 나타낸 것이기에 이를 통해 알고리즘의 수행시간을 추정할 수 있습니다. 빅오 표기법에 의한 알고리즘의 수행시간은 다음과 같습니다. (오른쪽으로 갈수록 수행시간이 길어진다는 뜻이며, 비효율적이라는 뜻입니다.)
$$ O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) $$
