Courbes de complexité
Comment se représenter réellement une complexité en terme de temps passé par l’ordinateur à traiter les données?
Chaque microprocesseur est capable de traiter un certain nombre d’opérations par seconde. Le plus long étant
généralement les calculs sur les réels (flottants), le critère souvent retenu pour déterminer la puissance brute d’un
processeur est le FLOPS : Floating Point Operations Per Second. Un Intel Pentium 4 à 3.2GHz tourne à une moyenne
de 3,1 GFLOPS (GigaFlops) soit 10 9 FLOPS, ou encore un milliard d’opérations sur réels par seconde. Si vous traitez 20
données dans un algorithme de complexité O(n), la vitesse de calcul se chiffre en millionièmes de seconde. Le même
nombre de données dans un algorithme de complexité O(n!) doit effectuer 2432902008176640000 opérations ce qui
prendra 784807099 secondes, ou encore une fois converti autour de 25 ans! Bien entendu, une complexité O(n!) est la
pire qui puisse exister. Avec une complexité inférieure O(2 n ), le traitement prendrait un dixième de seconde tout de
même, ce qui est énorme et relativise fortement la puissance des processeurs…
Vous comprenez maintenant l’utilité de connaître la complexité des algorithmes et d’optimiser ceuxci…
Dans la suite, les complexités ne seront fournies que dans les cas où les traitements, plus compliqués que d’habitude,
sont en concurrence avec diverses méthodes. C’est le cas par exemple des méthodes de tris sur des tableaux. Ceci
dans l’unique but de vous donner un simple ordre d’idée.
- 6 -
© ENI Editions - All rigths reserved - Jonifar lina
14
Comment se représenter réellement une complexité en terme de temps passé par l’ordinateur à traiter les données?
Chaque microprocesseur est capable de traiter un certain nombre d’opérations par seconde. Le plus long étant
généralement les calculs sur les réels (flottants), le critère souvent retenu pour déterminer la puissance brute d’un
processeur est le FLOPS : Floating Point Operations Per Second. Un Intel Pentium 4 à 3.2GHz tourne à une moyenne
de 3,1 GFLOPS (GigaFlops) soit 10 9 FLOPS, ou encore un milliard d’opérations sur réels par seconde. Si vous traitez 20
données dans un algorithme de complexité O(n), la vitesse de calcul se chiffre en millionièmes de seconde. Le même
nombre de données dans un algorithme de complexité O(n!) doit effectuer 2432902008176640000 opérations ce qui
prendra 784807099 secondes, ou encore une fois converti autour de 25 ans! Bien entendu, une complexité O(n!) est la
pire qui puisse exister. Avec une complexité inférieure O(2 n ), le traitement prendrait un dixième de seconde tout de
même, ce qui est énorme et relativise fortement la puissance des processeurs…
Vous comprenez maintenant l’utilité de connaître la complexité des algorithmes et d’optimiser ceuxci…
Dans la suite, les complexités ne seront fournies que dans les cas où les traitements, plus compliqués que d’habitude,
sont en concurrence avec diverses méthodes. C’est le cas par exemple des méthodes de tris sur des tableaux. Ceci
dans l’unique but de vous donner un simple ordre d’idée.
- 6 -
© ENI Editions - All rigths reserved - Jonifar lina
14