Zárt . Ehhez a kérdéshez részletekre vagy egyértelműségre van szükség . Jelenleg nem fogadja el a válaszokat.
Megjegyzések
- Kérdése már tartalmaz teljes választ az eredeti problémára, de nincs kérdés erről a válaszról. Így csak " igen / nem " válaszok maradhatnak, amelyek sem Önnek, sem a jövőbeni látogatóknak nem segítenek. Kérjük, olvassa el a kapcsolódó meta-beszélgetéseket itt és itt , és ennek megfelelően állítsa be kérdését, pl. egy konkrét kérdés megfogalmazásával a válasz egyetlen elemével kapcsolatban, amelyben nem biztos. Ha csak általános visszajelzést szeretne, akkor látogasson el hozzánk a Számítástechnikai csevegésben .
- @DavidRicherby Nos, akkor próbáljon meg nem nézni válaszolj és válaszolj rá, ha tudsz. Szerettem ezt a weboldalt, amíg mindenki nem kezdte megtalálni a feltett kérdések hibáit, ahelyett, hogy segített volna a kérdésben.
- Amiből azt gondolom, hogy megpróbálja feltenni, igen $ T (n) $ dollárban lenne O (2 ^ n) $, de ' d szorosabb felső korlátja van, $ T (n) \ -vel O-ban (\ phi ^ n) $, ahol $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Ezenkívül önmagában a képek használata sem jó stílus. Kérjük, írja át a szöveges elemeket – vegye figyelembe, hogy itt használhatja a LaTeX-et (a MathJax-on keresztül).
- A lekérdezése nem is hibás. A Fibonacci-szekvencia " időbeli összetettsége " nem dolog. Két értelmes dolgot kell itt feltenni: 1) Mi a Fibonacci-szekvencia aszimptotikus növekedése ($ \ Theta $ -ban)? 2) Mennyi az aszimptotikus futási ideje ennek az algoritmusnak, amely a Fibonacci-számokat számolja ki? – Azt hiszem, 2-re gondoltál. Ehhez van pár referencia kérdésünk , valamint az is az ismétlődések megoldására .
Válasz
Az elemzés nem pontos, bár az eredmény helyes. Pontosabban írhatná úgy, hogy a $ = $ helyett $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ mivel nem minden szinten van ugyanannyi gyerek, vegye figyelembe a legtöbb jobbkezes utat, n lépésenként $ 2 $ -kal csökken.
Valójában egy körültekintőbb elemzés szorosabb kötést eredményezhet, mint említik a megjegyzésben. Az ötlet az, hogy a $ T (n) $ időpontot kiszámítják a $ T (n-1) + T (n-2) $ értékkel ugyanúgy, mint a tényleges fibonacci $ F (n) $, és mivel $ F (n ) = O (\ phi ^ n) $ for $ \ phi = (1+ \ sqrt {5}) / 2 $, mint zárt űrlap.
Így $ T (n) = O (\ phi ^ n) $, amely valamivel kisebb, mint $ 2 ^ n $
Megjegyzések
- A második részhez figyelembe kell venni a további $ c $ díjfizetési kifejezést a $ T $ visszatérésekor. A $ F $ megismétlődése csak a leveleket számolja, de a $ T $ értéke az összes csomópontot. Nem mindig van az, hogy a levelek száma aszimptotikusan dominál, vö. rekurziós fa módszer.