Gesloten . Deze vraag heeft details of duidelijkheid nodig. Het accepteert momenteel geen antwoorden.
Opmerkingen
- Uw vraag bevat al een volledig antwoord op het oorspronkelijke probleem, maar geen vraag over dit antwoord. Dus alleen " ja / nee " antwoorden kunnen overblijven, die jou noch toekomstige bezoekers helpen. Lees gerelateerde metadiscussies hier en hier en pas uw vraag dienovereenkomstig aan, bijvoorbeeld door een specifieke vraag te formuleren over een enkel element van uw antwoord waarover u twijfelt. Als u alleen algemene feedback wilt, kunt u ons bezoeken in Computerwetenschappelijke chat .
- @DavidRicherby Nou, kijk dan niet naar mijn beantwoord en beantwoord het, als je kunt. Ik hield van deze site totdat iedereen fouten van de gestelde vragen begon te vinden in plaats van degene met de vraag te helpen.
- Van wat ik denk dat je probeert te vragen, ja, $ T (n) $ zou in $ O (2 ^ n) $ maar jij ' d hebt een strakkere bovengrens met $ T (n) \ in O (\ phi ^ n) $ waar $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Bovendien is het gebruik van alleen afbeeldingen hier geen goede stijl. Transcripeer de tekstelementen – merk op dat u LaTeX hier kunt gebruiken (via MathJax).
- Uw vraag is niet eens fout. De " tijdcomplexiteit van de Fibonacci-reeks " is niet iets. Er zijn hier twee belangrijke dingen om te vragen: 1) Wat is de asymptotische groei van de Fibonacci-reeks (in $ \ Theta $)? 2) Wat is de asymptotische looptijd van dit algoritme dat de Fibonacci-getallen berekent? – Ik denk dat je 2 bedoelde). Daarvoor hebben we een paar referentievragen , en ook voor het oplossen van recidieven .
Answer
De analyse is niet nauwkeurig, hoewel het resultaat correct is. Je zou het nauwkeuriger kunnen schrijven door $ = $ te vervangen door $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ aangezien niet alle niveaus hetzelfde aantal kinderen hebben, overweeg dan het meest rechtshandige pad, n neemt af met $ 2 $ per stap).
Inderdaad kan een meer zorgvuldige analyse u een strakkere grens opleveren, aangezien vermeld in de opmerking. Het idee is dat de tijd $ T (n) $ wordt berekend met $ T (n-1) + T (n-2) $ op dezelfde manier als de werkelijke fibonacci $ F (n) $, en sinds $ F (n ) = O (\ phi ^ n) $ voor $ \ phi = (1+ \ sqrt {5}) / 2 $ als het gesloten formulier.
Dus $ T (n) = O (\ phi ^ n) $ wat iets kleiner is dan $ 2 ^ n $
Reacties
- Voor het tweede deel moet men rekening houden met de extra toltermijn $ c $ in de herhaling van $ T $. De herhaling voor $ F $ telt alleen bladeren, maar die van $ T $ telt alle knooppunten. Het is niet altijd zo dat het aantal bladeren asymptotisch overheerst, cf. recursieboom-methode.