[알고리즘] 알고리즘 분석의 기초

  알고리즘은 어떤 문제를 해결하는 메커니즘을 의미한다. 알고리즘의 효율성을 따질 때 자원을 얼마나 최소한으로 사용하느냐가 중요하게 고려된다. 특히 알고리즘 분석이라고 하면 대부분 "시간"을 중요시하며, 알고리즘의 효율성을 판단하는 잣대가 "시간복잡도"라는 개념이다. 이는 "입력"에 대해 얼마만큼의 "시간"이 걸리는지 그 비율을 의미한다. "입력"과 "시간"은 문제상황에 따라 다르게 정의될 수 있지만 대부분의 경우 자명하다. 또한 우리가 관심을 가지는 상황은 "입력"이 꽤 큰 경우이다. 꽤 크다는 것은 애매한 표현이라고 생각될 수 있지만 수학적으로는 특정 상수 이상의 입력에 대해 공통적으로 적용되는 상황 또는 입력이 무한을 커질 때 적용되는 상황이라고 이해할 수 있겠다.
 
  필자는 수학적인 알고리즘 시간복잡도 계산에 흥미가 있기 때문에 알고리즘을 공부하면서 시간복잡도를 수학적으로 증명하는 과정도 공부하면서 기록할 것이지만 처음에는 가볍게 알고리즘의 작동 원리만 이해하는 것도 충분히 공부가 될 것 같다. 이 게시글에는 시간복잡도 표기법에 대해 알아보겠다.
 

         알고리즘의 시간복잡도 표기법  

1. O - 표기법

  필자가 알고리즘의 ㅇ도 모를 때 처음 접한 시간복잡도 표기법이다. 이는 알고리즘 시간복잡도의 상한을 나타내는 표기법이다. O(f(n))이라 함은 이 알고리즘은 아무리 오래 걸려도 f(n) 시간만큼 걸린다는 뜻이다. 수학적인 정의는 다음과 같다.

 좀 거칠게 말로 풀어보자면 어떤 상수(n0) 이상의 모든 입력 크기에 대해 g(n)의 상수배보다 작거나 같은 함수의 집합이라고 할 수 있다. 직관적으로 느껴보자면 꽤 큰 입력크기에 대해서 상수배로는 g(n)을 뛰어넘을 수 없는 모든 함수의 집합을 O(n)이라고 한다. 이를 Big-O 표기법이라 한다. 예를 들어 3n^2은 O(n^2)에 속한다. 이를 직관적으로 판별하는 방법은 "차수가 작거나 같다" 또는 "3n^2에 아무리 큰 상수를 곱해도 n^2을 뛰어넘을 수 없다" 와 같이 생각하는 것이다. 엄밀한 정의대로 따져보자면 c=4, n0=1로 잡으면 n0 이상의 모든 n에 대해 3n^2<=4n^2이므로 3n^2 = O(n^2) 이라 할 수 있다. 참고로 여기서 사용된 등호는 양 변의 값이 동등하다는 의미가 아니라 좌변이 우변(집합)에 속한다는 의미이고, 관행에 따라 굳어진 표현이라고 한다.

 
2. Ω - 표기법

  Big-Omega 표기법은 Big-O와는 반대 상황을 나타낸다. 알고리즘 시간복잡도의 하한을 나타내는 기호이다. 즉, Ω(f(n))은 시간복잡도가 적어도 f(n) 만큼 걸린다는 의미이다. 예를 들어 4n은 Ω(n)에 속한다. 마찬가지로 직관적으로 따지면 4n의 차수가 n보다 크거나 같고, n에 아무리 큰 상수를 곱해도 4n을 뛰어넘을 수 없기 때문이다. 엄밀히 따지면 c=3, n0=1로 잡으면 n0보다 크거나 같은 모든 n에 대해 4n>=3n이기 때문이다.

3. Θ - 표기법

  Theta-표기법은 위 두 상황의 교집합을 의미한다. Θ(f(n))이라 하면 시간복잡도가 f(n)과 동일하다고 볼 수 있다. 예를 들어 n+3은 Θ(n)에 속한다. n+3과 n의 차수가 동일하고, 서로 아무리 큰 상수를 곱해도 서로를 넘어설 수 없기 때문이다. 엄밀히 따지자면 Big-O의 조건과 Big-Omega의 조건을 동시에 만족한다는 것을 증명하면 된다. c1=1, c2=2, n0=3로 잡으면 n0 이상의 모든 n에 대해  n<=n+3<=2n 부등식이 성립하기 때문에 n+3 = Θ(n)이다. 이번에 알고리즘을 공부하면서 Theta-표기법을 자주 사용할 건데, 그 이유는 알고리즘의 정확한 시간복잡도를 계산하는 훈련을 하기 위해서이다. Big-O 표기법도 자주 사용되지만 널널하게 잡은 상한 (예를 들면 n=O(n^2))이 되면 아무래도 알고리즘을 정확히 분석했다고 말하기 어렵기 때문에 Theta-표기가 중요하다.

 

이 3가지 외에도 little-o / little-omega 표기법도 있는데, 이는 각각 Big-O / Big-Omega에서 등호 조건이 빠진, 널널한 상한/하한을 의미한다. 거의 쓸일이 없어 간단하게 넘어가겠다.