Bonjour.

Je suis le cours "Découvrez le fonctionnement des algorithmes", partie 4, chapitre 3 "Voyez le monde autrement avec la récursivité".

La professeur prend l'exemple de la suite de Fibonacci pour comparer la complexité de différents algorithmes.

Il est dit que l'ajout d'un nombre demande deux fois plus de mémoire que le précédent, soit une complexité 2^n (d'ailleurs, ne vaudrait-il mieux pas écrire 2^(n-1) ?).

Lorsque je dessine les arbres relatifs à l'algorithme dit "naïf", si je compte le nombre de fois où les opérations de soustraction (n-1, n-2) sont faites, cela nous donne pour n = 2, 3, 4 et 5 respectivement : 2 opérations, puis 4, puis 8 puis 14.

Ce qui donnerait plutôt une complexité pour le niveau n : (complexité niveau n-1) + (complexité niveau n-2) + 2...

Ou bien mon association complexité = nbre opérations fibo n'est pas bonne ?

Merci.

-
Edité par Un débutant 14 mars 2019 à 10:24:10

Bonjour ! Est-ce que le 2^n, ce n'est pas juste pour l'algorithme récursif ? Parfois, un algorithme récursif n'est pas aussi efficace. Ici, par exemple, pour calculer le terme 12, on doit calculer les termes 11 et 10. Par récursivité, pour calculer le terme 11, on doit calculer les termes 10 et 9 : ça fait deux calculs du terme 10. Et ainsi de suite avec les termes précédents. Le premier terme va être calculé 2^n fois (ou 2^(n-1), peu importe). À moins que quelque chose m'échappe, il ne faut surtout pas utiliser la récursivité pour Fibonacci. (Sauf bien sûr d'un point de vue pédagogique pour illustrer les problèmes de complexité.)

Cela dit, si tu obtiens 2, 4, 8, 14, ce n'est pas n, au contraire ça ressemble à du 2^n (il faudrait voir la suite mais c'est bien parti pour).

-
Edité par robun 14 mars 2019 à 12:21:36

Re.

Je pense comprendre ce que tu expliques dans ton premier paragraphe : effectivement, comme le calcul d'un terme appelle les deux termes précédents, on a le calcul d'un terme donné en doublon.

Par contre, dans ta dernière phrase, selon moi, il y a un souci :

2^1 = 2 ; 2^2 = 4 ; 2^3 = 8 ; mais 2^4 = 16 et non 14 ... d'où ma question initiale...

Car pour avoir 2, 4, 8, 14 opérations, on fait plutôt :

nbre opérations niveau n = nbre opé niv n-2 + nbre opé niv n-1 + 2

2 = 0 + 0 + 2

4 = 0 + 2 + 2

8 = 2 + 4 + 2

14 = 4 + 8 + 2

mais encore une fois, tout cela se base sur l'hypothèse que la complexité est le nombre d'opérations faites, l'opération faite étant ici les soustractions liées à n-1 et n-2...

Quand on dit qu'un algorithme est en 2^n, ça veut dire qu'il y a de l'ordre de 2^n opérations, pas exactement 2^n.

C'est quoi après 14 ?

-
Edité par robun 14 mars 2019 à 16:20:44

Si tu le dessines sur une feuille, pour les n suivants 0,1,2,3,4,5,6, tu as, en nombre total de soustractions du type n-2 ou n-1 :

0, 0 (normal pour l'initialisation), puis 2 op, 4 op, 8 op, 14 op, 24 op...

ce qui donne pour un terme n >=2 :

nbre opérations pour n = nbre opérations pour n-2 + nbre opérations pour n-1 + 2.

Exemples : pour n = 4, on prend le nombre d'opérations pour n = 3 (à savoir 4 op) et pour n = 2 (2 op) auxquels on rajoute 2, ce qui nous fait bien 8 op.

Ce qui d'ailleurs est assez visuel sur l'arborescence quand on la dessine : on remarque la recopie, deux fois, de la partie de plus haut degré du niveau précédent, et on ajoute une double branche sur l'un des deux "massifs" recopiés.

Alors, j'entends le "de l'ordre" :

2 ; 4 ; 8 ; 14 ; 24 (ce que je remarque)

2 ; 8 ; 16 ; 32 ; 64 (2^n)

Alors, à la rigueur, on peut même raisonner sur 2^(n-1), ce qui donnerait :

2 ; 4 ; 8 ; 14 ; 24 (ce que je remarque)

1 ; 2 ; 8 ; 16 ; 32 (2^(n-1))

Je ne sais pas si un matheux peut nous éclairer. De premier abord, cette approximation, qui marche au début, ne fonctionne plus ensuite. En effet, j'ai tout de même l'impression que la suite que je je remarque croit bien moins vite que 2^n :

2 ; 3 ; 4 ;  5  ;  6  ; 7  ;  8  ;  9    (n)

2 ; 4 ; 8 ; 14 ; 24 ; 38 ; 62 ; 100 (ce que je remarque)

1 ; 2 ; 8 ; 16 ; 32 ; 64 ; 128 ; 256 (2^(n-1))

Après, je pars du principe qu'on compte les soustractions comme des opérations mais peut-être qu'il faut raisonner autrement.

Dans le texte du cours, elle raisonne effectivement sur la capacité de la mémoire en disant qu'en passant au nombre d'après, il faut deux fois plus de mémoire. Il y a peut-être une subtilité qui m'échappe ou alors je ne me concentre pas sur le bon angle d'attaque. En tout cas, je ne vois pas d'où vient ce "x 2".

Je viens seulement de me rendre compte qu'il s'agissait de la complexité en mémoire, pas de la complexité en calculs. Du coup la suite de ce message est hors-sujet. Mais comme je trouve le raisonnement intéressant, notamment la petite récurrence, je laisse tout ça. Et je n'ai plus le courage de calculer la complexité en mémoire. Je ne serais pas surpris qu'elle ressemble elle aussi à une suite de Fibonacci.

On parle bien de l'algorithme récursif ?

1) Algorithme non-récursif ; on calcule les Fib(k) au fur et à mesure.

Fib(2) = Fib(1) + Fib(0) --> 1 addition.

Fib(3) = Fib(2) + Fib(1) --> 1 addition.

On voit bien que pour calculer Fib(n), il faudra de l'ordre de n additions (n-2 je pense).

2) Algorithme récursif : chaque Fib(k) est calculé en fonction de Fib(k-1) et Fib(k-2).

Je note N(k) = le nombre d'additions requises pour calculer Fib(k).

Au début :

− N(0) = 0,

− N(1) = 0,

− N(2) = 1 (on calcule Fib(0) + Fib(1)),

− N(3) = N(2) + N(1) + 1 = 2 (1 addition pour calculer Fib(2) + Fib(1), et 1 addition dans le calcul de Fib(2)).

Ensuite, pour tout k >= 2 : Fib(k+2) = Fib(k+1) + Fib(k). Il faut N(k+1) calculs pour le premier terme, N(k) pour le second, et 1 addition pour les sommer.

− Pour Fib(4) je trouve 4 additions : 2 pour Fib(3), 1 pour Fib(2) et 1 pour les sommer.

− Pour Fib(5) il y a 7 additions : 4 pour Fib(4), 2 pour Fib(3) et 1 pour les sommer.

− Bref, la formule est : N(k+2) = N(k+1) + N(k) + 1 (qui ressemble à Fibonacci mais ce n'est pas le cas à cause du +1).

Ça donne la suite 0 ; 0 ; 1 ; 2 ; 4 ; 7 ; 12 ; 20 ; 33 ; 54 ; 88.

Apparemment N(k) = Fib(k+1) - 1 à partir de k=4. Voyons si ça peut se démontrer par récurrence.

Propriété P(k) : pour tout k >=4, N(k) = Fib(k+1) - 1 et N(k+1) = Fib(k+2) - 1. (Eh oui, il faut mettre deux termes dans la récurrence.)

Initialisation :

N(4) = 4, et en effet Fib(5) - 1 = 5 - 1 = 4.

N(5) = 7, et en effet Fib(6) - 1 = 8 - 1 = 7.

Hérédité :

Supposons que P(k) est vraie pour un certain k >=4. Alors :

N(k+1) = Fib(k+2) - 1 (par hypothèse),

N(k+2) = N(k+1) + N(k) + 1 = (Fib(k+2) - 1) + (Fib(k+1) - 1) + 1 = Fib(k+3) - 1,

ce qui montre qu'alors P(k+1) est vraie. La propriété est héréditaire.

Conclusion :

Pour tout k >= 4 : N(k) = Fib(k+1) - 1.

Comme Fib(n) est équivalent à φ^n (à un facteur près) où φ est le nombre d'or, la complexité de la méthode récursive est φ^n. En effet ce n'est pas 2^n.

Si je ne me suis pas trompé...

-
Edité par robun 14 mars 2019 à 19:19:12

Salut,

Pour commencer je tiens à dire qu'on peut coder Fibonacci en récursif avec une complexité linéaire.

def fibo(n):
    def aux(a, b, n):
      if n == 0:
          return a
      else:
          return aux(b, a + b, n - 1)
    return aux(0, 1, n)

Sinon, en résolvant l'équation u_{n + 2} = u_{n + 1} + u_n (on laisse de côté l'addition supplémentaire) on a déjà quelque chose d'exponentiel (c'est un cas classique de suite récurrente linéaire d'ordre 2 et en fait, c'est l'équation qui définit la suite de Fibonacci et qui donne lieu à la formule de Binet, et l'équivalence u_n équivalent en plus l'infini à \phi(n) / sqrt(5) avec phi le nombre d'or).

-
Edité par yo@n97one 14 mars 2019 à 19:27:17

Re.

Merci pour vos réponses mais là vous allez un peu trop loin pour moi les gars !

J'ai suivi vite fait le raisonnement et ai jeté un petit coup d'oeil sur wiki pour les formules de Binet...

Donc si je résume...

La complexité en mémoire n'est pas forcément celle en opérations. Ce que tu proposes robun, c'est la complexité en opérations, ici des additions. D'ailleurs si j'ai bien compris le raisonnement, il ne faut pas considérer les soustractions n-1 et n-2 mais plutôt les opérations de la ligne de code, à savoir l'addition de fib(n-1) et de fib(n-2). Au final, la complexité en opérations n'est pas de 2^n.

Si je comprends, le terme de la suite de fibonacci de rang n sera quasiment égal au nombre d'or phi à la puissance n ?

Autre question de "curieux" : l'équation version suite "u_{n + 2} = u_{n + 1} + u_n" est dite récurrente linéaire d'ordre 2, càd qu'on peut faire un parallèle avec x^2 - x - 1 = 0 comme si les indices n+2, n+1, et n faisaient références aux puissances de x ?

J'ai compris le programme que tu proposes yo@n97one. Je suis un peu long à la détente mais je crois que c'est bon. En ce qui concerne sa complexité, elle est linéaire dans le sens où le passage de fib(n) à fib(n+1) n'ajoute qu'un tour de "boucle", avec une seule opération (je viens de le faire avec un papier et un crayon... on ne rajoute effectivement qu'une ligne...) ?

Comment fait-on pour calculer la complexité en mémoire si ce n'est pas la même chose que celle en opérations ? Quel élément prend-on en compte pour faire ce calcul ?

Pour calculer la complexité en mémoire, il faut savoir quelle variable va être créée en mémoire à chaque appel récursif. Il me semble que chaque appel nécessite deux variables : on calcule Fib(n+1) et on le stocke en mémoire, on calcule Fib(n) et on le stocke en mémoire, puis on les additionne et on retourne Fib(n). On a donc eu besoin de deux cases mémoire.

Du coup, notons M(n) le nombre de variables utilisées au total (avec la récursivité « naïve »).

M(0) = 0 (pas de calcul, donc rien à mémoriser).

M(1) = 0 (pas de calcul, donc rien à mémoriser).

M(2) = 2 (on appelle Fibonacci de 1 et de 0, qui ne nécessitent pas de calculs mais doivent quand même être mémorisées avant d'être additionnées).

M(3) = 2 (on mémorise Fib(2) et Fib(1) avant de les additionner) + M(2) (la mémoire nécessaire au calcul de Fib(2)) + M(1) (celle pour Fib(1)) = 2 + 2 + 0 = 4.

De façon générale :

M(k+2) = 2 (on mémorise Fib(k+1) et Fib(k) avant de les additionner) + M(k+1) + M(k).

La suite des M(k) est donc : 0, 0, 2, 4, 8, 14, 24, 40, 66...  Je crois que ça correspond bien à ce que tu as trouvé.

Je ne vois pas de formule évidente. J'ai l'impression que ça ressemble à du φ^n + 2^n (avec n-3 à la place de n en fait), qui est équivalent à 2^n à un facteur près. L'idée, c'est que le +2, il y en a deux fois plus pour le terme n que pour le terme n-1.

-
Edité par robun 15 mars 2019 à 12:59:45

Oui, effectivement, ce que tu proposes semble être ce dont je parlais au-dessus. Ce que j'appelais "opérations en tant que soustractions" serait donc la complexité en mémoire...

Je tombe sur la même formule, par contre, j'ai dû me tromper au 40 car j'avais trouvé 38... Mais j'ai oublié de faire +2 après la somme de 14 et 24. Le boulet !

Donc même si ce n'est pas exact, on part du principe que le terme d'après prend environ 2 fois plus de place :

2 x 2 = 4 ; 4 x 2 = 8 ; 8 x 2 ≈ 14 ; 14 x 2 ≈ 24 ; 24 x 2 ≈ 40 ; 40 x 2 ≈ 66 ; 66 x 2 ≈ 108 ; etc

Bon, et bien, merci pour toutes ces explications et discussions !