Zavřeno . Tato otázka vyžaduje podrobnosti nebo jasnost . Momentálně nepřijímá odpovědi.
Komentáře
- Vaše otázka již obsahuje úplnou odpověď na původní problém, ale žádná otázka o této odpovědi. Mohou tedy zůstat pouze " ano / ne " odpovědi, které nepomohou vám ani budoucím návštěvníkům. Přečtěte si související meta diskuze zde a zde a podle toho upravte svoji otázku, např. formulací konkrétní otázky o jediném prvku vaší odpovědi si nejste jisti. Pokud chcete pouze obecnou zpětnou vazbu, můžete nás navštívit v Computer Science Chat .
- @DavidRicherby No, zkuste se nepodívat na můj odpovězte a odpovězte, pokud můžete. Miloval jsem tento web, dokud všichni nezjistili chyby na položených otázkách, místo aby mi pomohli s otázkou.
- Z toho, co si myslím, že se snažíte zeptat, ano $ T (n) $ bude v $ O (2 ^ n) $, ale ' byste měli těsnější horní hranici s $ T (n) \ v O (\ phi ^ n) $, kde $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Samotné používání obrázků zde také není dobrý styl. Přepište prosím textové prvky – všimněte si, že LaTeX můžete použít zde (přes MathJax).
- Váš dotaz není ani špatný. " časová složitost Fibonacciho posloupnosti " není věc. Zde je třeba se zeptat na dvě smysluplné věci: 1) Jaký je asymptotický růst Fibonacciho sekvence (v $ \ Theta $)? 2) Jaký je asymptotický běh tohoto algoritmu počítajícího Fibonacciho čísla? – Myslím, že jsi myslel 2). K tomu máme několik referenčních otázek a také k řešení opakování .
Odpověď
Analýza není přesná, i když je výsledek správný. Dalo by se to napsat přesněji nahrazením $ = $ za $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $, protože ne všechny úrovně mají stejný počet dětí, zvažte cestu nejvíce pro praváky, n se každým krokem snižuje o $ 2 $).
Pečlivější analýza vám může přinést pevnější vazbu uvedeno v komentáři. Myšlenka je, že čas $ T (n) $ se počítá s $ T (n-1) + T (n-2) $ stejným způsobem jako skutečný fibonacci $ F (n) $ a od $ F (n ) = O (\ phi ^ n) $ za $ \ phi = (1+ \ sqrt {5}) / 2 $ jako uzavřený formulář.
Tedy $ T (n) = O (\ phi ^ n) $, které je o něco menší než $ 2 ^ n $
Komentáře
- U druhé části je třeba mít na paměti dodatečný mýtný výraz $ c $ při opakování $ T $. Opakování pro $ F $ počítá pouze listy, ale jeden z $ T $ počítá všechny uzly. Ne vždy platí, že počet listů dominuje asymptoticky, srov. metoda rekurzivního stromu.