알고리즘이란?
알고리즘이란 문제를 풀기 위한 절차를 기술한 것입니다.
알고리즘은 하나 이상의 출력을 가져야 하고, 각 절차가 모호하지 않고 명확해야 하는 명확성, 유한한 시간 안에 결과를 생성해야 하는 유한성, 그리고 모든 컴퓨터에서 실행될 수 있어야 하는 유효성을 만족해야 합니다.
또 알고리즘이 예상대로 수행되는지에 대하여 수학적으로 증명하는 정확성 분석, 알고리즘이 문제를 얼마나 효율적으로 해결할 수 있는지 파악하는 효율성 분석을 통해 알고리즘을 평가합니다.
알고리즘의 효율성 분석에서는 알고리즘의 실행부터 완료까지 필요한 총 메모리의 양을 나타내는 공간 복잡도와, 마찬가지로 실행부터 완료까지 걸리는 시간을 나타내는 시간 복잡도를 평가합니다.
점근성능
알고리즘의 시간 복잡도는 알고리즘에 입력되는 데이터의 크기가 커질수록 증가합니다. 따라서 입력의 크기가 무한하게 커짐에 따라서 결정되는 성능을 계산하는데, 이를 점근성능(asymptotic performance)이라고 합니다.
시간 복잡도는 입력의 크기 n에 대한 함수 f(n)으로 표현됩니다.
함수 f(n)은 입력 크기 n일 때의 수행 시간을 나타냅니다.
예를 들어서, 입력이 n개 들어왔을 때 n번 계산이 수행된다면, 세 가지 표기법으로 아래처럼 표시할 수 있습니다.
| Big-O 표기: O(n) | 알고리즘의 수행 시간 f(n)은 O(n)보다 작다. 즉, 최악의 경우이다. |
| Big-Omega 표기: Ω(n) | 알고리즘의 수행 시간 f(n)은 Ω(n)보다 작다. 즉, 최적의 경우이다. |
| Big-Theta 표기: Θ(n) | 최악의 수행 시간 O(n)과 최적의 수행 시간 Ω(n)을 동시에 나타낸다. |
일반적으로 알고리즘의 시간 복잡도는 O(n)으로 나타내며, 연산 시간 순서로 나타내면 아래와 같습니다.
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)
재귀 알고리즘(순환 알고리즘)의 성능
이진 탐색 알고리즘과 같이 수행 과정에서 알고리즘 자신을 반복적으로 호출하는 재귀 알고리즘의 수행 시간을 나타내기 위해서는 점화식(漸化式)을 사용합니다. 이진 탐색 알고리즘의 점화식은
n = 1일 때 T(n) = Θ(1)
n >= 2일 때 T(n) = T(n/2) + Θ(1)
로 나타내는데, 만약 n=8이라면
T(8)
= T(4)+Θ(1)
= T(2)+2Θ(1)
= T(1)+3Θ(1)
와 같이 T(n)은 1을 향해 1/2씩 점점 작아지고, 상수항의 계수는 그에 비례해 커집니다.
결국 상수항의 계수가 k일 때 식의 모양은
T(n/2^k) + kΘ(1) = T(1) + kΘ(1)
이 됩니다. T(n/2^k)는 위 n=8 예시에서 보이듯이 T(1)과 같습니다.
계수 k를 잘 관찰하면, 입력 n과 관련된 규칙성을 찾을 수 있습니다.
k = log n입니다. (밑이 2인 로그)
n=8이라면, k = log 8 = 3이므로 정말 그렇죠?
따라서 이진 탐색 알고리즘의 점화식의 폐쇄형은
T(n) = Θ(log n)
이 됩니다. 읽어주셔서 감사합니다.