Une petite remarque pour compléter les réponses précédentes : les CPU modernes, l'accès à la mémoire est tellement étrange (à cause des caches) que la complexité en opérations n'est pas toujours très utile pour évaluer un algorithme. Par exemple, si tu fais un produit de matrice par matrice, la complexité en opérations (nombre de multiplications et d'additions) est en O(n^3) (on peut faire beaucoup mieux, mais c'est très compliqué et je n'ai pas envie d'entrer dans les détails, et de plus c'est délicat à mettre en oeuvre). Si tu programmes ça de façon classique, les accès à la mémoire sont aussi en O(n^3), c'est à dire que tu demandes à la mémoire O(n^3) fois un double. Or, tu peux t'arranger pour descendre à O(n^2). Pour des matrices de taille classique, c'est de coût qui domine largement le temps de calcul (malgré la théorie !) et le passage de n^3 à n^2 pour les accès peut réduire drastiquement le temps de calcul. Cf les papiers sur ATLAS : http://math-atlas.sourceforge.net/(...)
[^] # Re: Avancées technologiques du prochain Kernel
Posté par boubou . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 2.