결과는 정확하지만 분석은 정확하지 않습니다. $ = $를 $ \ le $로 바꾸면 더 정확하게 작성할 수 있습니다.
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ 모든 레벨에 동일한 수의 자식이있는 것은 아니므로 가장 오른 손잡이 경로를 고려하십시오. n은 매 단계마다 $ 2 $ 씩 감소합니다.
실제로보다 신중한 분석은 다음과 같이 더 엄격한 경계를 얻을 수 있습니다. 댓글에 언급되었습니다. 아이디어는 $ T (n) $ 시간이 $ T (n-1) + T (n-2) $로 실제 피보나치 $ F (n) $와 같은 방식으로 계산되고 $ F (n ) = O (\ phi ^ n) $ for $ \ phi = (1+ \ sqrt {5}) / 2 $.
따라서 $ T (n) = O (\ phi ^ n) $는 $ 2 ^ n $보다 약간 작습니다.
댓글