1-(3) Growth of Function

이 단원에서는 알고리즘의 수행시간을 분석하는 방법에 대해 다룬다. 나는 그냥 대충 다루겠다.

알고리즘의 수행 시간은 CPU의 속도, 컴파일러의 성능 등 여러가지에 의해 결정되는 면이 있지만, 그것에 가장 지배적인 영향을 미치는 요인은 알고리즘의 특성이다. 즉, n개의 데이터가 주어지는 문제에서 해당 알고리즘은 몇 번 데이터를 봐야하는가? 가 그 수행시간을 지배적으로 결정한다고 보는 것이다. 

n개의 데이터가 주어졌을 때 수행시간인 T(n)은 다음과 같은 세 개의 notation에 의해 표현된다.

1. Θ-notation: T(n)의 tight한 수행시간

2. O-notation: T(n)의 upper bound가 될 수 있는 terms

3. Ω-notation: T(n)의 lower bound가 될 수 있는 terms

사실 그 정의가 수학적으로 엄격하게 쓰여있지만 어차피 어떻게 적용하는지만 알면 된다.

예를 들어 T(n)=3n³+5000n²+100인 알고리즘이 있다고 해보자. 그러면 upper bound는 n³이상의 차수를 가진 term들이 될 수 있고(ex:n⁴....) lower bound는 n³이하의 차수를 가진 term들이 될 수 있다. (term의 계수는 무시해도 된다.)

따라서 O-notation으로는 n의 3승으로 쓰나 11승으로 쓰나 맞다. 오메가 노테이션도 1승 2승 상관 없다.

그러면 Θ-notation은 그 교집합이다. 즉, 이 경우는 n의 3승이 된다. 

근데 뭐하러 이렇게 어렵게 생각하는가

그냥 T(n)에서 n이 커질 때 leading term을 보면 된다. 예를 들어 위의 T(n)=3n³+5000n²+100에서는 n이 커지면 3n³이 이 함수의 값을 지배적으로 결정할 것이다. 그러니까 그냥 이 term이 Θ-notation이 된다.

그냥 어떤 알고리즘의 속도를 얘기할 때는 어떤 케이스에 대한 leading term을 얘기하면 된다... 너무 이런 방법론에 신경쓸 필요는 없는 것 같고 귀찮아서 줄여 썼다.

핵심: 일반적으로 T(n)의 leading term이 그 알고리즘의 수행시간을 결정한다.

(물론 계수 때문에 그렇지 않은 경우도 있을 것이다.)