[INFO] Illustration de la COMPLEXITÉ pour les ORDINATEURS

La suite de Fibonacci est une suite connue, dont chaque terme est la somme des deux précédents :
0, 1, 1, 2, 3, 5, 8, 13, 21...

On peut coder cette suite de plusieurs manières dans le langage Python :

1/

def fibo_naif(i):

    if i == 0:

        return 0

    if i == 1:

        return 1

    else:

        return fibo_naif(i-2) + fibo_naif(i-1)

Si je veux calculer le 40ème terme, mon ordinateur me le donne en 28,7 secondes :

%time fibo_naif(40)



CPU times: user 28.6 s, sys: 110 ms, total: 28.7 s

Wall time: 28.7 s

2/

def fibo_malin(n):

    elif n == 1:

        return (0, 1)

    else:

        (a, b) = fibo_malin(n-1)

        return (b, a+b)

Ici, si je veux calculer le 40ème terme, mon ordinateur me le donne en 44 microsecondes (ce qui est 652272 fois plus rapide que le calcul précédent) :

%time fibonacci(40)



CPU times: user 34 µs, sys: 10 µs, total: 44 µs

Wall time: 50.3 µs

En effet, lorsque je calcule fibo_naif(40), je calcule fibo_naif(38) + fibo_naif(39), puis fibo_naif(38) calcule fibo_naif(36)+fibo_naif(37) et fibo_naif(39) calcule fibo_naif(37) + fibo_naif(38), etc.

La fonction est appelée de l'ordre de 2^(40/2) fois, soit environ 1 million de fois.

Dans le deuxième cas, la fonction est appelée 39 fois.

D'où l'importance de bien optimiser ses programmes.

d'où l'importance de faire de la récursion terminale

Le 05 juillet 2023 à 18:17:25 :
d'où l'importance de faire de la récursion terminale

Y'a pas de récursion terminale dans mon deuxième exemple.

Le 05 juillet 2023 à 18:18:33 :

Le 05 juillet 2023 à 18:17:25 :
d'où l'importance de faire de la récursion terminale

Y'a pas de récursion terminale dans mon deuxième exemple.

je sais

Les gens de microsoft doivent pas connaitre ça vu comme leur OS est lent

Python
HolyC

D'où l'importance de trouver une formule générale au lieu de faire des algos comme un goulem

Le 05 juillet 2023 à 18:21:03 :
D'où l'importance de trouver une formule générale au lieu de faire des algos comme un goulem

C'est beaucoup plus rapide avec un algo hein.

Le 05 juillet 2023 à 18:17:00 :
D'où l'importance de bien optimiser ses programmes.

je suis bien d'accord mais je comprends pas ce qu'on fait avec a+b à la derniere ligne ?

Le 05 juillet 2023 à 18:22:02 :

Le 05 juillet 2023 à 18:17:00 :
D'où l'importance de bien optimiser ses programmes.

je suis bien d'accord mais je comprends pas ce qu'on fait avec a+b à la derniere ligne ?

a c'est fibo(n-2), b c'est fibo(n-1), donc b, a+b = fibo(n-1), fibo(n-2) + fibo(n-1) = fibo(n-1), fibo(n)

Je ne sais pas si c'est clair.

Le 05 juillet 2023 à 18:24:13 :

Le 05 juillet 2023 à 18:22:02 :

Le 05 juillet 2023 à 18:17:00 :
D'où l'importance de bien optimiser ses programmes.

je suis bien d'accord mais je comprends pas ce qu'on fait avec a+b à la derniere ligne ?

a c'est fibo(n-2), b c'est fibo(n-1), donc b, a+b = fibo(n-1), fibo(n-2) + fibo(n-1) = fibo(n-1), fibo(n)

Je ne sais pas si c'est clair.

oui j'ai compris après j'ai écris ça sans même réfléchir, moi les algos comme ça c'est impossible que ça me vienne en tête c'est beaucoup trop complexe franchement

Le 05 juillet 2023 à 18:21:31 :

Le 05 juillet 2023 à 18:21:03 :
D'où l'importance de trouver une formule générale au lieu de faire des algos comme un goulem

C'est beaucoup plus rapide avec un algo hein.

c'est vrai que résoudre une quadratique ça prend longtemps

cest du niveau CP ca tu interesses qui avec ton topic pour bebe

Le 05 juillet 2023 à 18:25:49 :

Le 05 juillet 2023 à 18:21:31 :

Le 05 juillet 2023 à 18:21:03 :
D'où l'importance de trouver une formule générale au lieu de faire des algos comme un goulem

C'est beaucoup plus rapide avec un algo hein.

c'est vrai que résoudre une quadratique ça prend longtemps

Non mais des multiplications sur des flottants c'est surtout plus long que des sommes d'entiers.

On s'en branle zinzolin

J'ai pas compris : quand tu fais la deuxième fonction il te renvoie un duo de chiffres (a, b) avec a le chiffre précédent et b le résultat ?

Le 05 juillet 2023 à 18:26:45 :
J'ai pas compris : quand tu fais la deuxième fonction il te renvoie un duo de chiffres (a, b) avec a le chiffre précédent et b le résultat ?

Oui, absolument.

D'ailleurs j'ai écrit une connerie, c'est pas "elif n==1", c'est "if n == 1".

Le 05 juillet 2023 à 18:27:08 :

Le 05 juillet 2023 à 18:26:45 :
J'ai pas compris : quand tu fais la deuxième fonction il te renvoie un duo de chiffres (a, b) avec a le chiffre précédent et b le résultat ?

Oui, absolument.

D'ailleurs j'ai écrit une connerie, c'est pas "elif n==1", c'est "if n == 1".

Ah d'accord merci

C'est la balance qui a fait tombé John Abruzzi