Lukket . Dette spørgsmål har brug for detaljer eller klarhed . Det accepteres i øjeblikket ikke svar.
Kommentarer
- Dit spørgsmål indeholder allerede et komplet svar på det oprindelige problem, men intet spørgsmål om dette svar. Således er kun " ja / nej " svar, som hverken hjælper dig eller fremtidige besøgende. Læs relaterede metadiskussioner her og her og juster dit spørgsmål i overensstemmelse hermed, f.eks. ved at formulere et specifikt spørgsmål om et enkelt element i dit svar, er du usikker på. Hvis du bare vil have generel feedback, er du velkommen til at besøge os i Computer Science Chat .
- @DavidRicherby Nå så prøv ikke at se på min svar og besvar det, hvis du kan. Jeg elskede dette websted, indtil alle begyndte at finde fejl i de stillede spørgsmål snarere end at hjælpe den med spørgsmålet.
- Fra det jeg tror, du prøver at stille, ville $ T (n) $ være i $ O (2 ^ n) $ men du ' d har en strammere øvre grænse med $ T (n) \ i O (\ phi ^ n) $ hvor $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Brug af billeder alene er heller ikke god stil her. Transkriber venligst tekstelementerne – bemærk at du kan bruge LaTeX her (via MathJax).
- Din forespørgsel er ikke engang forkert. " tidskompleksiteten af Fibonacci-sekvensen " er ikke noget. Der er to meningsfulde ting at spørge her: 1) Hvad er den asymptotiske vækst i Fibonacci-sekvensen (i $ \ Theta $)? 2) Hvad er den asymptotiske driftstid for denne algoritme, der beregner Fibonacci-numrene? – Jeg mente du mente 2). Til det har vi et par referencespørgsmål og også til løsning af gentagelser .
Svar
Analysen er ikke korrekt, selvom resultatet er korrekt. Du kan skrive det mere præcist ved at erstatte $ = $ med $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ da ikke alle niveauer har samme antal børn, skal du overveje den mest højrehåndede vej, n falder med $ 2 $ hvert trin).
Faktisk kan en mere omhyggelig analyse få dig en strammere bundet som nævnt i kommentaren. Ideen er, at tiden $ T (n) $ beregnes med $ T (n-1) + T (n-2) $ på samme måde som den faktiske retracement $ F (n) $, og siden $ F (n ) = O (\ phi ^ n) $ for $ \ phi = (1+ \ sqrt {5}) / 2 $ som den lukkede form.
Således $ T (n) = O (\ phi ^ n) $, der er lidt mindre end $ 2 ^ n $
Kommentarer
- I den anden del skal man være opmærksom på den yderligere vejafgift $ c $ i gentagelsen af $ T $. Gentagelsen for $ F $ tæller kun blade, men den af $ T $ tæller alle noder. Det er ikke altid tilfældet, at antallet af blade dominerer asymptotisk, jf. metode til rekursionstræ.