Passer d'une complexité quadratique au linéaire

[invite476719f2]

Bonsoir,

J'ai le souvenir d'un programme agissant sur un tableau de longueur n, qui par un algorithme naïf fonctionnait quadratiquement (en parcourant le tableau plus d'une fois)
Cependant, il était possible de le corriger en créeant un deuxième tableau de même longueur n, et en notant à chaque fois quelque chose dans ce tableau, de sorte qu'on ne fait cette fois qu'un seul parcours. Dans ce cas la complexité estlinéaire.

Malheureusement je ne me souviens plus vraiment de la fonction du programme, mais je crois savoir que la démarche de créer un deuxième tableau pour y noter des résultats intermédiaires et réduire la complexité est courante.
Pourriez-vous m'expliquer en quoi cela permet de réduire la complexité? (si vous aviez un exemple de programme par exemple)

Merci beaucoup.
-----

[invite7a96054d]

Bonjour,
Difficile de répondre réellement à ta question. Si je comprends bien ta demande tu ne parles pas de deux algorithmes différents, le premier aurait une complexité temporelle supérieure au second, mais le second une complexité spatiale inférieure au premier. Tu parles bien d'adapter un algorithme de manière "à économiser" des calculs déjà effectués (et coûteux en temps) en augmentant sa complexité spatiale.
Cette technique est appelée mémoization. Un exemple simple de mémoization peut être le classique fibonacci, La version naïve de l'algorithme

fibo(n : entier) : entier
debut
  si n<2 alors
    renvoyer 1
  sinon
    renvoyer fibo(n-1)+fibo(n-2)
  fin si
fin

a une complexité temporelle en O(𝜑ⁿ) avec 𝜑 le nombre d'or, ce qui n'est pas du tout bon ... Le problème vient en partie du fait que lors du calcul de fibo(n-2) on refait tous les calculs déjà faits lors de fibo(n-1). Si nous sauvons tous les résultats intermédiaires nous pourrions alors en réduire la complexité. Cela donne par exemple un algo comme :

fibo_memo(n : entier, memo : tableau d'entiers)
debut
  si memo[n]=0 alors
    memo[n]=fibo_memo(n-1)+fibo_memo(n-2)
  fin si
fin

fibo2(n : entier) : entier
debut
  memo : tableau de max(2,n) entiers initialisés à 0
  memo[0]=1
  memo[1]=1
  fib_memo(n,memo)
  renvoyer memo[n]
fin

L'algorithme qui est essentiellement le même (quoique cela est subjectif) est maintenant de complexité temporelle linéaire O(n) mais la complexité spatiale est augmentée de O(n) en contrepartie.

L'exemple est simple, tu peux par exemple (si tu es anglophone) regarder sur geeksforgeeks l'évolution de l'algorithme pour résoudre le problème de la plus longue chaîne croissante (LIS) : approche naïve + mémoization, approche plus complexe avec mémoization. Et évidemment il y a une tonne de références grâce à google.