SICP 연습문제 1.21 친절한 풀이

문제

smallest-divisor 프로시저로 199,1999,19999의 가장 작은 약수를 찾아라.

문제로 부터 얻은 것

앞 절의 내용이 이해가 되셨다면, 굳이 구현할 필요는 없다고 생각합니다.

문제풀이

혹시나 시간복잡도가 $Θ(\sqrt{n})$이 되는 것을 이해하지 못하신 분들을 위해서 성명드리자면,

find-divisor 프로시저는 n의 약수를 찾을때
1~n까지의 수를 검사하는 것이 아니라, 1~$\sqrt{n}$의 수를 검사합니다.
n이 4배로 커진다면, 확인해야 할 테스트케이스의 수는 2배로 커지므로, $Θ(\sqrt{n})$의 시간 복잡도를 가집니다.

읽어주셔서 감사합니다.