Analiza nie jest dokładna, chociaż wynik jest prawidłowy. Możesz napisać to dokładniej, zamieniając $ = $ na $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ ponieważ nie wszystkie poziomy mają taką samą liczbę dzieci, rozważ ścieżkę najbardziej praworęczną, n zmniejsza się o 2 $ na każdym kroku).
Rzeczywiście, dokładniejsza analiza może dać ci ściślejsze ograniczenie, ponieważ wspomniany w komentarzu. Chodzi o to, że czas $ T (n) $ jest obliczany za pomocą $ T (n-1) + T (n-2) $ w taki sam sposób, jak rzeczywisty fibonacci $ F (n) $, a ponieważ $ F (n ) = O (\ phi ^ n) $ for $ \ phi = (1+ \ sqrt {5}) / 2 $ jako forma zamknięta.
Zatem $ T (n) = O (\ phi ^ n) $, które jest nieco mniejsze niż $ 2 ^ n $
Komentarze