Bonjour,
Lorsqu'on a le choix entre deux algorithmes, faut-il systématiquement choisir l'algorithme dont l'ordre de grandeur de la complexité en moyenne est le plus petit ?
J'aurais envie de dire oui mais si ça se trouve il peut exister des cas où ce n'est pas conseillé : en connaissez-vous ?
Il y a plein de cas où on n'utilise pas les algorithmes avec la complexité moindre parce que leur implémentation est trop lourde ou parce qu'en pratique, ils ne deviennent plus efficaces que pour des tailles plus grandes que celles qu'on manipule.
Tu peux regarder https://en.wikipedia.org/wiki/Comput...cal_operations par exemple et tu verras qu'il y a des algorithmes pour la multiplication qui sont d'une complexité très faible.
Et on ne s'en sert pas.
Tu peux aussi regarder les produits de matrice sur le même lien.
Merci beaucoup pour ta réponse rapide !
Je vais regarder ça.
Oui, tout simplement le cas où le volume de données est petit. Il sera souvent préférable d'utiliser un algorithme simple et lent qu'une usine à gaz inutile.
Par exemple, suppose que tu cherche un élément dans une liste.
L'algo le plus simple est de comparer ton élément à chaque élément de la liste.
Si c'est une liste de 10 éléments , c'est suffisant (sauf si tu as à faire la recherche des milliards de fois)
Si ta liste comporte des millions d'éléments, il sera sans doute plus intéressant de la trier et de faire une recherche dichotomique.
Si ta liste compte 100 milliards d'élément, même le tri va être dur : il faut sûrement réfléchir à d'autres solutions, en essayant de profiter des particularités de la liste, et en tenant compte du nombre de fois où tu vas faire la recherche.
Un autre exemple courant est l'inversion de matrices : on ne raisonne pas du tout de la même façon si c'est une matrice 3x3 ou si c'est une matrice 1000000x1000000.
[edit] Grillé par PM42 ! [/EDIT]
Hello,
Tout à fait d'accord avec pm42 et Chanur.
Un autre exemple bien connu (souvent donné en exercice d'ailleurs) concerne la convolution (avec des images 2D par exemple). On peut calculer un seuil T tels que, étant donnée une image de taille NxN, le calcul de la convolution dans l'espace image est plus rapide pour N < T alors que pour N > T il est plus rapide de faire la convolution dans l'espace de fourier via FFT.
