<åt sidan class = "s-notice s-notice__info js-post-notice mb16" role = "status ">
Stängd . Den här frågan behöver detaljer eller tydlighet . För närvarande accepteras inte svar.
Kommentarer
- Din fråga innehåller redan ett fullständigt svar på det ursprungliga problemet men ingen fråga om detta svar. Således kan bara " ja / nej " svar kvar, vilket varken hjälper dig eller framtida besökare. Läs relaterade metadiskussioner här och här och justera din fråga därefter, t.ex. genom att formulera en specifik fråga om ett enda element i ditt svar är du osäker på. Om du bara vill ha generell feedback är du välkommen att besöka oss i Datavetenskapschatt .
- @DavidRicherby Tja, försök att inte titta på min svara och svara på det, om du kan. Jag älskade den här webbplatsen tills alla började hitta fel på de frågor som ställts snarare än att hjälpa den med frågan.
- Från vad jag tror att du försöker ställa, skulle $ T (n) $ vara i $ O (2 ^ n) $ men du ' d har en strammare övre gräns med $ T (n) \ i O (\ phi ^ n) $ där $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Att använda bilder ensam är inte heller bra här. Transkribera textelementen – notera att du kan använda LaTeX här (via MathJax).
- Din fråga är inte ens fel. " tidskomplexiteten i Fibonacci-sekvensen " är ingen sak. Det finns två meningsfulla saker att fråga här: 1) Vad är den asymptotiska tillväxten av Fibonacci-sekvensen (i $ \ Theta $)? 2) Vad är den asymptotiska körtiden för denna algoritm som beräknar Fibonacci-numren? – Jag antar att du menade 2). För det har vi ett par referensfrågor , och även för att lösa återfall .
Svar
Analysen är inte korrekt även om resultatet är korrekt. Du kan skriva det mer exakt genom att ersätta $ = $ med $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ eftersom inte alla nivåer har samma antal barn, tänk på den mest högerhänta vägen, n minskar med $ 2 $ varje steg).
En mer noggrann analys kan faktiskt göra att du blir tätare nämns i kommentaren. Tanken är att tiden $ T (n) $ beräknas med $ T (n-1) + T (n-2) $ på samma sätt som den faktiska Fibra $ F (n) $, och sedan $ F (n ) = O (\ phi ^ n) $ för $ \ phi = (1+ \ sqrt {5}) / 2 $ som den stängda formen.
Således $ T (n) = O (\ phi ^ n) $ som är något mindre än $ 2 ^ n $
Kommentarer
- För den andra delen måste man vara medveten om den extra avgiftsperioden $ c $ vid återfallet av $ T $. Återkommet för $ F $ räknar bara löv men den av $ T $ räknar alla noder. Det är inte alltid så att antalet löv dominerar asymptotiskt, jfr. rekursionsträdmetoden.