Găsirea complexității în timp a secvenței fibonacci [închis]

Închis . Această întrebare are nevoie de detalii sau claritate . În prezent, nu acceptă răspunsuri.

Comentarii

Întrebarea dvs. include deja un răspuns complet la problema inițială, dar nu există nicio întrebare despre acest răspuns. Astfel, pot rămâne doar răspunsurile " da / nu ", ajutându-vă nici pe voi, nici pe viitorii vizitatori. Vă rugăm să citiți meta-discuții conexe aici și aici și ajustați întrebarea în consecință, de ex. formulând o întrebare specifică despre un singur element al răspunsului dvs. despre care sunteți nesigur. Dacă doriți doar feedback general, sunteți binevenit (ă) să ne vizitați în Chat de informatică .
@DavidRicherby Ei bine, atunci încercați să nu vă uitați la răspunde și răspunde-i, dacă poți. Mi-a plăcut acest site până când toată lumea a început să găsească defecte la întrebările adresate, mai degrabă decât să o ajut pe cea cu întrebarea.
Din ceea ce cred că încercați să puneți, da $ T (n) $ ar fi în $ O (2 ^ n) $ dar ' aveți o margine superioară mai strânsă cu $ T (n) \ în O (\ phi ^ n) $ unde $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
De asemenea, folosirea singură a imaginilor nu este un stil bun aici. Transcrieți elementele textului – rețineți că puteți utiliza LaTeX aici (prin MathJax).
Interogarea dvs. nici măcar nu este greșită. " complexitatea temporală a secvenței Fibonacci " nu este un lucru. Există două lucruri semnificative de întrebat aici: 1) Care este creșterea asimptotică a secvenței Fibonacci (în $ \ Theta $)? 2) Care este timpul de rulare asimptotic al acestui algoritm care calculează numerele Fibonacci? – Cred că ai vrut să spui 2). Pentru aceasta, avem câteva întrebări de referință și, de asemenea, pentru rezolvarea recurențelor .

Răspuns

Analiza nu este corectă, deși rezultatul este corect. Puteți să-l scrieți mai precis înlocuind $ = $ cu $ \ le $

$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ întrucât nu toate nivelurile au același număr de copii, luați în considerare calea cea mai dreaptă, n scade cu $ 2 $ la fiecare pas).

Într-adevăr, o analiză mai atentă vă poate face să fiți mai strâns ca menționată în comentariu. Ideea este că timpul $ T (n) $ este calculat cu $ T (n-1) + T (n-2) $ în același mod ca și Fibonacci $ F (n) $ și din moment ce $ F (n ) = O (\ phi ^ n) $ pentru $ \ phi = (1+ \ sqrt {5}) / 2 $ ca formă închisă.

Astfel $ T (n) = O (\ phi ^ n) $ care este puțin mai mic decât $ 2 ^ n $

Comentarii

Pentru a doua parte, trebuie să ții cont de termenul suplimentar de taxare $ c $ în recurența de $ T $. Recurența pentru $ F $ contează doar frunzele, dar cea de $ T $ contează toate nodurile. Nu întotdeauna este cazul ca numărul de frunze să domine asimptotic, cf. metoda arborelui recursiv.

Lasă un răspuns Anulează răspunsul