컴퓨터 알고리즘 Ch03, Ch04

▶ Growth of Function

알고리즘의 효율성을 판단하는 것은 매우 어려운 일이다. 하드웨어 기기나 소프트웨어 환경 등 여러 변수들의 영향을 하나하나 고려하기는 것은 사실 불가능한 일이기 때문이다. 따라서 알고리즘을 분석할 때에는 이를 실행시켜 정확한 실행시간을 측정하는 것이 아니라 점근적 분석(asymtotic analysis)을 통해 입력값이 무한대로 갈 때 시간복잡도 함수의 증가율을 분석한다.

▶ Recurrence

분할 정복 기법(divide-and-conquer) 기반의 알고리즘의 시간복잡도 함수는 점화식(recurrence)의 형태로 나타나곤 한다. 이러한 점화식의 해를 찾을 수 있는 방법에는 대표적으로 세 가지가 있다.

1. Substitution method
2. Recursion-tree method
3. Master method