Stengt . Dette spørsmålet trenger detaljer eller klarhet . Det aksepteres for øyeblikket ikke svar.
Kommentarer
- Spørsmålet ditt inneholder allerede et komplett svar på det opprinnelige problemet, men ingen spørsmål om dette svaret. Dermed er det bare " ja / nei " svarene som kan være igjen, noe som verken hjelper deg eller fremtidige besøkende. Les relaterte metadiskusjoner her og her og juster spørsmålet ditt deretter, f.eks. ved å formulere et spesifikt spørsmål om et enkelt element i svaret ditt, er du usikker på. Hvis du bare vil ha generell tilbakemelding, er du velkommen til å besøke oss i Datavitenskap chat .
- @DavidRicherby Vel, så prøv å ikke se på min svar og svar på det, hvis du kan. Jeg elsket dette nettstedet til alle begynte å finne feil på spørsmålene i stedet for å hjelpe den med spørsmålet.
- Fra det jeg tror du prøver å stille, ville $ T (n) $ være i $ O (2 ^ n) $ men du ' d har en strammere øvre grense med $ T (n) \ i O (\ phi ^ n) $ hvor $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Det er heller ikke bra å bruke bilder alene. Transkripsjon av tekstelementene – merk at du kan bruke LaTeX her (via MathJax).
- Søket ditt er ikke en gang feil. " tidskompleksiteten til Fibonacci-sekvensen " er ikke noe. Det er to meningsfulle ting å spørre her: 1) Hva er den asymptotiske veksten av Fibonacci-sekvensen (i $ \ Theta $)? 2) Hva er den asymptotiske kjøretiden til denne algoritmen som beregner Fibonacci-tallene? – Jeg antar at du mente 2). For det har vi et par referansespørsmål , og også for å løse gjentakelser .
Svar
Analysen er ikke nøyaktig selv om resultatet er riktig. Du kan skrive det mer nøyaktig ved å erstatte $ = $ med $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ siden ikke alle nivåer har like mange barn, vurder den mest høyrehendte banen, n avtar med $ 2 $ hvert trinn).
En mer nøye analyse kan gi deg en strengere bånd som nevnt i kommentaren. Tanken er at tiden $ T (n) $ beregnes med $ T (n-1) + T (n-2) $ på samme måte som den faktiske retracement $ F (n) $, og siden $ F (n ) = O (\ phi ^ n) $ for $ \ phi = (1+ \ sqrt {5}) / 2 $ som lukket skjema.
Dermed $ T (n) = O (\ phi ^ n) $ som er litt mindre enn $ 2 ^ n $
Kommentarer
- For den andre delen må man være oppmerksom på den ekstra bompengeperioden $ c $ i gjentakelsen av $ T $. Gjentakelsen for $ F $ teller bare blader, men den av $ T $ teller alle noder. Det er ikke alltid slik at antall blader dominerer asymptotisk, jfr. metoden for rekursjonstrær.