1.10.2 비재귀 알고리즘 분석

우선 비재귀 알고리즘은 말 그대로 재귀적이지 않은 알고리즘이다. 재귀 알고리즘은 해를 당연하게 알 수 있는 자명한 인스턴스가 나올 때까지 같은 문제의 더 작은 인스턴스에 대해 알고리즘 자체를 반복해 적용하는 방식으로 돌아간다. 비재귀 알고리즘 분석은 기본 단계가 실행되는 횟수의 총합을 구하는 데서 시작된다. 이 합을 간략히 정리해 실행 횟수를 정확히 나타내는 공식이나 증가율을 보여줄 수 있는 근사 공식을 만들어낸다. 다음과 같은 퍼즐 문제를 예로 생각해보자.[Gar99, p.88]

정사각형 덧붙이기 이 알고리즘은 정사각형 한 개에서 시작한다. 다음 단계에서는 바깥쪽 모든 변에 새로운 정사각형을 하나씩 덧붙인다. 이 알고리즘을 n번 반복하면 단위 정사각형은 총 몇 개가 될까? 초기 몇 단계의 결과는 그림 1-12와 같다.

▲ 그림 1-12 정사각형 덧붙이기 알고리즘의 첫 세 단계