Există mai multe modalități de a face lucrurile. Există întotdeauna diferite puncte de vedere și stiluri de pitching. ~Tim Hudson

În acest articol, vom folosi trei tehnici diferite în Python pentru a codifica un program de bază Fibonacci care va da suma succesiunii ca rezultat. Secvența Fibonacci este 0,1,1,2,3,5,8 …

După cum probabil ați observat, adăugăm primul și al doilea număr, 0 și 1, pentru a obține al treilea număr în secvența (1) -> 0 + 1 = 1. Apoi adăugăm al doilea și al treilea număr, 1 + 1 = 2, pentru a obține al patrulea număr din secvență … și așa mai departe.

Puteți implementa acest cod în Jupyter, Colab sau orice IDE sau editor de text cu care vă simțiți confortabil.

Cum se codifică secvența Fibonacci folosind un buclă For în Python

Aici am scris un program de bază Fibonacci folosind o buclă for în Python. Logica din spatele acestui lucru este simplă și am discutat deja mai sus.

Complexitatea timpului este O (N), iar complexitatea spațiului este O (1) sau constantă. Dar, de fapt, este mai complicat decât presupune această complexitate.

“Dacă numărul dvs. este mai mic de N <94, și utilizați un număr întreg pe 64 de biți, atunci algoritmul acționează ca o complexitate liniară. Cu toate acestea, pentru N> 94 începe să se comporte ca un algoritm de complexitate pătratică. “~ Michael Veksler

Memoarea recursiunea si pentru bucle in Python
Tipărirea unui rezultat Fibonacci folosind un For Loop

Voi rula asta cu Python’s %timeit modul. Astfel se evită o serie de capcane comune pentru măsurarea timpilor de execuție. Puteți vedea mai multe utilizări aici.

1611565024 512 Memoarea recursiunea si pentru bucle in Python
A fost nevoie de 675 nanoSec pe buclă pentru 10

Cum se codifică secvența Fibonacci cu recursivitate în Python

Aici, vom implementa secvența folosind recursivitate. Funcțiile recursive tind să se apeleze la repetare până când ajung la cazul de bază. Deci, recursivitatea creează o structură de copac.

Dacă luăm o serie Fibonacci de 5, acesta este arborele care va fi creat prin recursivitate.

1611565024 859 Memoarea recursiunea si pentru bucle in Python

Complexitatea spațială este O (N), iar complexitatea timpului este O (2 ^ N) deoarece nodul rădăcină are 2 copii și 4 nepoți. Și, după cum puteți vedea, fiecare nod are 2 copii.

Acum, adâncimea este N, ceea ce înseamnă că trebuie să facem acest lucru de N ori. De asemenea, este posibil să fi observat că sub-arborele din dreapta este mai mic decât sub-arborele din stânga, astfel încât timpul real de rulare este aproximativ O (1,6 ^N).

Cazul de bază: Fibonacci (2) = Fibra (1) + Fib (0) = 1 + 0 = 1

1611565024 376 Memoarea recursiunea si pentru bucle in Python
Imprimarea rezultatului Fibonacci folosind Recursivitate

Exemplul recursiv Fibonacci este cu siguranță mai rapid decât bucla for.

1611565024 1 Memoarea recursiunea si pentru bucle in Python

Cum se codifică secvența Fibonacci folosind memoizația în Python

Memoarea este o tehnică care poate îmbunătăți semnificativ performanța unei funcții recursive prin reducerea răspunderii de calcul.

Aceasta stochează rezultatele apelurilor funcționale costisitoare într-o matrice sau dicționar și returnează rezultatele cache când se apelează aceeași intrare.

Puteți vedea arborele de mai sus pentru referință și modul în care anumite intrări continuă să fie recomputate la fiecare apel către acestea.

1611565024 778 Memoarea recursiunea si pentru bucle in Python
Tipărirea rezultatului Fibonacci folosind Memoisation

Complexitatea timpului este O (nlogn).

1611565024 745 Memoarea recursiunea si pentru bucle in Python

Ce este mai bun, recursivitate, pentru bucle sau memozație?

Acum, aceste tehnici nu ar trebui să fie mai bune una de cealaltă. Pur și simplu trebuie să știți când trebuie să utilizați care dintre ele. Care depinde desigur de cerințele dumneavoastră.

Iterarea va fi mai rapidă decât recursiunea, deoarece recursivitatea trebuie să se ocupe de cadrul recursiv al stivei de apeluri. Dar, dacă recursivitatea este scrisă într-un limbaj care optimizează apelul, atunci elimină cheltuielile generale și este aproape la egalitate cu buclele.

În cele din urmă, memoarea este mai bună ori de câte ori spațiul de stare este rar, adică nu trebuie rezolvate toate subproblemele mai mici, ci doar câteva dintre ele.

Mulțumesc pentru lectură! Dacă ți-a plăcut acest articol, poți citiți celelalte articole ale mele aici. Poti arată-ți aprecierea pentru acest articol împărtășindu-l. De asemenea, puteți conectează-te cu mine pe LinkedIn.