DEUG MIAS

INFORMATIQUE
Cours, TD, TP

Estimation quantitative d'un algorithme: la complexité

Dans la perspective de réaliser cette estimation, on doit avant introduire des outils mathématiques basé sur le taux d'accroissement de quelques fonctions.

On veut comparer les taux d'accroissement des différentes fonctions et d'introduire les cinq symboles asymptotiques utilisés pour décrire ces taux d'accroissement. Ceci est utile en particulier pour comparer, à l'aide d'un langage rigoureux, les vitesses d'exécution de plusieurs algorithmes effectuant la même tâche, I'espace mémoire qu'ils utilisent, ou toute autre forme de mesure de la complexité des algorithmes que nous pourrons être amenés à utiliser.

Supposons que nous disposions d'unc méthode pour inverser les matrices carrées regulières. Comment mesurer sa vitesse? La plupart du temps nous dirons, par exemple, "pour une matrice n * n, la méthode va prendre un temps 16,8n³. Ainsi, si une matrice 100 x 100 peut être inversée, avec cette méthode, en 1 minute de temps de calcul, une matrice 200 x 200 nécessiterait 2³ = 8 fois plus de temps, soit 8 minutes. La constante "16,8" n'intervient pas dans cet exemple; seul le fait que le temps de cal cul varie comme la 3^ième puissance de la dimension de la matrice est significatif.

Nous avons donc besoin à partir de maintenant, d'un langage qui permette de préciser que le temps de calcul, en tant que fonction de n, varie "de l'ordre de n³, "au plus aussi vite que n³, ou "au moins aussi vite que n⁵ log n", etc.

Les nouveaux symboles utilisés pour la comparaison des taux d'accroissement des fonctions sont les cinq suivants:

prononcer "est petit o de ..."

prononcer "est grand o de..."

prononcer "est theta de..."

~ prononcer "est asymptotiquement égal, ou, tilde à ..."

prononcer "est omega de..."

Voyons maintenant la signification des deux premiers. Les autres étant laisser à la curiosité du lecteur.

La complexité en temps d'un algorithme est habituellement exprimée à l'aide de la notation .

Symbole

Soient f (x) et g (x) deux fonctions de x. Chacun des cinq symboles précédents est destiné à comparer la vitesse de croissance de f et g. On écrit

f (x) = (g (x))

pour exprimer que f croît plus lentement que g quand x est tres grand, ce qui conduit à énoncer, en toute rigueur:

Définition: On dit que f (x) =(g (x)) (x) si lim f(x)/g(x) existe est vaut 0 quand x.

Exemple:

x²=(x⁵)

 

Symbole

Définition: Une fonction g(n) est dite en (f(n)) s'il existe des constante c et n₀ telles que pour tout n>n₀ on a:

g(n)< c*f(n)

Illustration de la notion de complexité

Un super-ordinateur peut être 1000 fois plus rapide qu'un micro-ordinateur, mais ce facteur est indépendant des données traitées. Cette observation permet de faire totalement abstraction de la machine utilisée dans la mesure de la complexité: il suffit d'exprimer celle-ci à un facteur constant près. On considère alors que la complexité en temps donne une estimation du nombre d'opérations élémentaires nécessaires à l'exécution d'un algorithme, indépendamment de la vitesse d'exécution de ces opérations.

Remarques:

Exprimer la complexité en temps d'un algorithme à un facteur constant près a aussi l'avantage de rendre cette mesure insensible à la représentation exacte des données: la fonction de complexité est identique pour toutes les représentations dont la taille ne diffère que d'un facteur constant.

Un algorithme opérant sur des nombres a une fonction de complexité identique que ces nombres soient représentés en binaire ou en décimal. En effet, le rapport entre la longueur de la représentation binaire et décimale des nombres est un facteur constant.

La notation simplifie l'expression des fonctions de complexité. En effet, elle introduit implicitement le facteur constant nécessaire. De plus, elle n'exprime qu'une borne supérieure sur les fonctions et permet donc de donner une indication sur la complexité d'un algorithme sans nécessairement la caractériser complètement. Finalement, la notation ignore le comportement des fonctions pour les petites valeurs, ce qui permet souvent de simplifier l'expression de la complexité d'un algorithme pour des données de petite taille, la complexité d'un algorithme est souvent dominée par des opérations d'initialisation qui deviennent négligeables pour des données plus grandes.

Exemple 1

La fonction cn² est (n²). Il en va de même de c₁n² + c₂n puisque pour n > 1, c₁n² + c₂n < (c₁ + c₂)n². On dira donc qu'un algorithme dont le temps de calcul est donné par c₁n² + c₂n a une fonction de complexité (n²).

Exemple 2

L'algorithme de tri à bulle est un algorithme en (n²).

Exercice 1

Donner la complexité dans le pire des cas de l'algorithme implémenté dans TriRapide.

Correction