Fibonacci sekos skaičiavimo sudėtingumas

Suprantu „Big-O“ įrašą, bet nežinau, kaip ją apskaičiuoti daugeliui funkcijų. Visų pirma, aš bandžiau išsiaiškinti, kaip sudėtingas Fibonacci sekos naivus variantas:

 int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } 

Kas yra skaičiavimo sudėtingumas Fibonacci sekoje ir kaip jis apskaičiuojamas?

276
11 дек. Džuljeta surengė gruodžio 11 d 2008-12-11 23:20 '08 11:20 val. 2008-12-11 23:20
@ 12 atsakymų

Jūs imituojate laiko funkciją, kad apskaičiuotumėte Fib(n) kaip laiko sumą, apskaičiuojant Fib(n-1) plius laiką, apskaičiuojant Fib(n-2) plius laiką, kad juos pridėtumėte ( O(1) ). Tai rodo, kad pakartotiniai to paties „ Fib(n) atliekami tuo pačiu metu, t.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Jūs išspręsite šį pasikartojimo ryšį (pvz., Naudojant generuojančias funkcijas), ir jūs baigsite atsakymą.

Be to, galite piešti rekursijos medį, kurio gylis n ir intuityviai supras, kad ši funkcija yra asimptotiškai O(2 n ) . Tada galite įrodyti savo hipotezę indukcijos būdu.

Priežastis: akivaizdžiai n = 1

Tarkime, kad T(n-1) = O(2 n-1 )

T(n) = T(n-1) + T(n-2) + O(1)

T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )

Tačiau, kaip pažymėta komentaruose, tai nėra sunki linija. Įdomus faktas apie šią funkciją yra tai, kad T (n) asimptotiškai sutampa su Fib(n) verte, nes abi yra apibrėžtos kaip

f(n) = f(n-1) + f(n-2) .

Rekursinio medžio lapai visada grįš 1. Fib(n) reikšmė yra visų vertybių, kurias lapai grąžina rekursijos medyje, suma, kuri yra lygi lapų skaičiui. Kadangi kiekvienam lapui apskaičiuoti reikia O (1), T(n) yra Fib(n) x O(1) . Todėl šios funkcijos standi riba yra pati Fibonacci seka (~ θ(1.6 n ) ). Jūs galite atpažinti šią standžią ribą naudodami generavimo funkcijas, kaip jau minėjau.

317
11 дек. Mehrdad Afshari atsakymas gruodžio 11 d 2008-12-11 23:29 '08 at 11:29 2008-12-11 23:29

Tiesiog paklauskite savęs, kiek pareiškimų, kuriuos reikia užpildyti norint užbaigti F(n) .

F(1) atsakymas yra 1 (pirmoji sąlyginės išraiškos dalis).

F(n) atsakymas yra F(n-1) + F(n-2) .

Taigi, kokia funkcija atitinka šias taisykles? Pabandykite n (a> 1):

a n == a (n-1) + a (n-2)

Padalinkite iš (n-2) :

a 2 == a + 1

Išspręskite ir gaukite (1+sqrt(5))/2 = 1.6180339887 , kitaip žinomas kaip

112
11 дек. Atsakymą pateikė Jason Cohen gruodžio 11 d. 2008-12-11 23:26 '08 at 23:26 pm 2008-12-11 23:26

Labai gerai diskutuojama apie šią konkrečią problemą MIT . 5 puslapyje jie nurodo, kad jei manote, kad pridėjimas trunka vieną skaičiavimo vienetą, laikas, reikalingas Fib (N) skaičiavimui, yra labai glaudžiai susijęs su Fib (N) rezultatu.

Todėl galite tiesiogiai pereiti prie labai artimo Fibonacci serijos derinimo:

 Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately) 

ir tarkime, kad blogiausias naivo algoritmo veikimas

 O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1)) 

PS: Wikipedia aptaria uždarą N-ojo Fibonacci numerio formos išraišką, jei norite daugiau informacijos.

28
12 дек. Atsakymą pateikė Bob Cross 12.12. 2008-12-12 00:10 '08 0:10 2008-12-12 00:10

Sutinku su pgaur ir rickerbh, rekursinio-fibonacio sudėtingumas yra O (2 ^ n).

Prie tos pačios išvados atėjau gana paprasta, bet manau, kad vis dar yra pagrįstų argumentų.

Pirma, visa tai priklauso nuo to, kiek kartų skaičiuojant N-ąjį „Fibonacci“ numerį, išreiškiama, kiek kartų rekursyvi Fibonacci funkcija (nuo šiol yra F). Jei jis yra vadinamas vieną kartą po skaičių sekoje nuo 0 iki n, tada mes turime O (n), jei jis gauna n kartus kiekvienam skaičiui, tada mes gauname O (n * n) arba O (n ^ 2), ir t .d

Taigi, kai F () yra vadinamas numeriu n, kartų skaičius F () yra nurodytas tam tikram skaičiui tarp 0 ir n-1, kai jis artėja prie 0.

Kaip pirmąjį įspūdį, man atrodo, kad jei ją išreiškiame vizualiai, norėdami traukti vienetą laiku F (), turite įvesti tam tikrą skaičių piramidžių (ty, jei mes esame centriniai padaliniai horizontaliai). Kažkas panašaus:

 n * n-1 ** n-2 **** ... 2 *********** 1 ****************** 0 *************************** 

Dabar kyla klausimas: kaip greitai šio piramidės bazė auga didėjant n?

Paimkite tikrąjį atvejį, pavyzdžiui, F (6)

 F(6) * <-- only once F(5) * <-- only once too F(4) ** F(3) **** F(2) ******** F(1) **************** <-- 16 F(0) ******************************** <-- 32 

Matome, kad F (0) yra vadinamas 32 kartus, o tai yra 2 ^ 5, kuris šiuo pavyzdžiu yra 2 ^ (n-1).

Dabar mes norime žinoti, kiek kartų F (x) paprastai vadinama, ir mes galime pamatyti, kiek kartų F (0) yra vadinamas, yra tik jo dalis.

Jei psichiškai perkeliame visas linijas * iš F (6) į F (2) į tiesią F (1) liniją, pamatysime, kad linijos F (1) ir F (0) dabar yra lygios. Tai reiškia, kad bendras laikas F () vadinamas, kai n = 6 yra 2x32 = 64 = 2 ^ 6.

Dabar, atsižvelgiant į sudėtingumą:

 O( F(6) ) = O(2^6) O( F(n) ) = O(2^n) 
26
16 апр. atsakymą pateikė JP balandžio 16 d 2014-04-16 00:38 '14 - 0:38 2014-04-16 00:38

Jūs galite jį įdiegti ir gauti vizualizaciją.

  T(n) = T(n-1) + T(n-2) < T(n-1) + T(n-1) = 2*T(n-1) = 2*2*T(n-2) = 2*2*2*T(n-3) .... = 2^i*T(ni) ... ==> O(2^n) 
14
10 авг. Tony Tannous atsakymas, rugpjūčio 10 d 2017-08-10 18:39 '17, 18:39 pm 2017-08-10 18:39

Jis yra apačioje 2^(n/2) , o viršutiniame gale - 2 ^ n (kaip pažymėta kituose komentaruose). Ir įdomus šio rekursinio įgyvendinimo faktas yra tas, kad jis turi sunkų asimptotinį Fib (n) vertinimą. Šie faktai gali būti apibendrinti:

 T(n) = Ω(2^(n/2)) (lower bound) T(n) = O(2^n) (upper bound) T(n) = Θ(Fib(n)) (tight bound) 

Siaurą sieną galima sumažinti naudojant uždarą formą , jei norite.

9
12 дек. Atsakymą pateikė Dave L. 12.12. 2008-12-12 00:03 '08 0:03 2008-12-12 00:03

Įrodymų atsakymai yra geri, bet aš visada turiu atlikti keletą rankinių iteracijų, kad tikrai įtikintume. Taigi iš savo lentos ištraukiau mažą skambinimo medį ir pradėjau skaičiuoti mazgus. Aš suskirstiau savo sąskaitas į bendrus mazgus, lapų mazgus ir vidinius mazgus. Štai ką aš turiu:

 IN | OUT | TOT | LEAF | INT 1 | 1 | 1 | 1 | 0 2 | 1 | 1 | 1 | 0 3 | 2 | 3 | 2 | 1 4 | 3 | 5 | 3 | 2 5 | 5 | 9 | 5 | 4 6 | 8 | 15 | 8 | 7 7 | 13 | 25 | 13 | 12 8 | 21 | 41 | 21 | 20 9 | 34 | 67 | 34 | 33 10 | 55 | 109 | 55 | 54 

Kas vyksta iš karto, lapų mazgų skaičius yra fib(n) . Keletas kitų iteracijų pastebėjo, kad vidinių mazgų fib(n) - 1 . Todėl bendras mazgų skaičius yra 2 * fib(n) - 1 .

Kadangi jūs klasifikuodami skaičiavimo sudėtingumą, atmetate koeficientus, galutinis atsakymas yra θ(fib(n)) .

9
28 февр. atsakymas, kurį pateikė benkc , vasario 28 d 2014-02-28 04:21 '14, 04:21 AM 2014-02-28 04:21

Rekursinio algoritmo laiko sudėtingumas gali būti geriau įvertinamas piešiant rekursijos medį. Šiuo atveju modelio rekursijos medžio rekursijos santykis bus T (n) = T (n-1) + T (n-2) + O (1), kad kiekvienas žingsnis yra O (1), o tai reiškia pastovumą laikas, nes jis atlieka tik vieną palyginimą, kad patikrintų n reikšmę, jei blokas.Recursion tree atrodys

  n (n-1) (n-2) (n-2)(n-3) (n-3)(n-4) ...so on 

Čia, tarkim, kiekvienas lygis virš medžio žymimas „i“,

 i 0 n 1 (n-1) (n-2) 2 (n-2) (n-3) (n-3) (n-4) 3 (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6) 

Tarkime, kad tam tikra medžio I vertė baigsis, šis atvejis bus tada, kai ni = 1, todėl I = n-1, o tai reiškia, kad medžio aukštis yra n-1. Dabar pažiūrėkime, kiek buvo padaryta darbo kiekvienam medžio n sluoksniui. Atkreipkite dėmesį, kad kiekvienas žingsnis atitinka O (1) laiką, kaip nurodyta pakartojamumo atžvilgiu.

 2^0=1 n 2^1=2 (n-1) (n-2) 2^2=4 (n-2) (n-3) (n-3) (n-4) 2^3=8 (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6) ..so on 2^i for ith level 

kadangi i = n-1 yra medžio aukštis, darbas kiekviename lygyje bus

 i work 1 2^1 2 2^2 3 2^3..so on 

Todėl visas atliktas darbas bus kiekviename lygmenyje atlikto darbo suma, todėl bus 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1), nes I = n- 1. Geometrinių serijų atveju ši suma yra lygi 2 ^ n, todėl bendras laiko sudėtingumas yra lygus O (2 ^ n).

4
29 нояб. atsakymą nikhil kekan pateikė lapkričio 29 d. 2018-11-29 09:30 '18, 9:30, 2018-11-29 09:30

Na, man tai yra O(2^n) , nes šioje funkcijoje tik rekursija trunka daug laiko (suskaidymas ir laimėjimas). Matome, kad pirmiau minėta funkcija medyje tęsis tol, kol lapai bus uždaryti, kai pasiekiame F(n-(n-1)) lygį F(n-(n-1)) ty F(1) . Taigi čia, kai užrašome kiekvieno medžio gylyje atsirandančio laiko sudėtingumą, susumuojamos serijos:

 1+2+4+.......(n-1) = 1((2^n)-1)/(2-1) =2^n -1 

tai yra 2^n [ O(2^n) ] .

2
18 нояб. atsakymas suteiktas pgaur 18 nov. 2012-11-18 03:46 '12 at 3:46 2012-11-18 03:46
1
28 апр. atsakymas pateikiamas nsh3 28 balandis. 2010-04-28 23:33 '10, 23:33, 2010-04-28 23:33

Naivos rekursiškoji Fibonacci versija yra dizaino eksponentinė, nes skaičiavimas kartojasi:

Į šaknį, kurią apskaičiuojate:

F (n) priklauso nuo F (n-1) ir F (n-2)

F (n-1) vėl priklauso nuo F (n-2) ir F (n-3)

F (n-2) vėl priklauso nuo F (n-3) ir F (n-4)

tada kiekviename lygyje turite 2 rekursinius skambučius, kurie, skaičiuojant, praleidžia daug duomenų, laiko funkcija bus tokia:

T (n) = T (n-1) + T (n-2) + C, su konstanta C

T (n-1) = T (n-2) + T (n-3)> T (n-2)

T (n)> 2 * T (n-2)

...

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

Tai tik apatinė riba, kuri turėtų būti pakankama jūsų analizei, tačiau realiojo laiko funkcija yra pastovus to paties Fibonacci formulės faktorius, o uždaroji forma , kaip žinoma, yra auksinio santykio eksponentas.

Be to, galite rasti optimizuotas „Fibonacci“ versijas naudojant dinaminį programavimą taip:

 static int fib(int n) {  int f[] = new int[n+1]; int i;  f[0] = 0; f[1] = 1;  for (i = 2; i <= n; i++) { f[i] = f[i-1] + f[i-2]; } return f[n]; } 

Jis yra optimizuotas ir veikia tik n , bet ir eksponentiškai.

Sąnaudų funkcijos nustatomos pagal įvesties dydį iki žingsnio, skirto spręsti problemą. Kai matote dinaminę Fibonacci žingsnių versiją ( n skaičiuojant lentelę) arba lengviausią algoritmą, kad sužinotumėte, ar numeris yra paprastas ( sqrt (n), norint analizuoti realius numerio daliklius). Galbūt manote, kad šie algoritmai yra O (n) arba O (sqrt (n)) , bet tai paprasčiausiai neteisinga dėl šios priežasties: Jūsų algoritmo įvestis yra skaičius: n , naudojant dvejetainį žymėjimą, įvesties dydis sveikam skaičiui n : log2 (n) , tada atlikite kintamąjį keitimą.

 m = log2(n) // your real input size 

leidžia žinoti, kiek žingsnių priklauso nuo įvesties dydžio

 m = log2(n) 2^m = 2^log2(n) = n 

tada algoritmo kaina priklauso nuo įvesties dydžio:

 T(m) = n steps = 2^m steps 

todėl išlaidos yra eksponentinės.

0
01 окт. atsakymas į Miguel Oct 01 2017-10-01 01:21 '17 ne 1:21 2017-10-01 01:21

Jis veikia geriau:

 unsigned int Fib(unsigned int n) { // first Fibonaci number is Fib(0) // second one is Fib(1) and so on // unsigned int m; // m + current_n = original_n unsigned int a = 1; // Fib(m) unsigned int b = 0; // Fib(m-1) unsigned int c = 0; // Fib(m-2) while (n--) { c = b; b = a; a = b+c; } return a; } 
-4
21 дек. atsakymas duotas pyonas 21 d. 2008-12-21 00:10 '08 0:10 2008-12-21 00:10