blog2geek.com
jbibolletAvatar de jbibollet

2 billets | Profil

Recherche Google

ce blog tous
Derniers billets Connexion
Archives

ordregrandeur

17/05/2007

Ordre de grandeurs et notation theta

ATTENTION: La mise en page de ce billet pose problème, veuillez vous référer aux liens donnés dans le billet précédent pour consulter l'article sous une meilleure forme.

Complexité structurelle: ordre de grandeur et notation $\theta

Julien BIBOLLET, Dimitri BISOO, Benjamin GANDON

 

Résumé: Lorsque l'on doit choisir parmis plusieurs algorithmes celui qui est le plus performant, on a besoin d'exprimer une approximation de sa complexité ou de son temps d'exécution. Pour ce faire, on utilise la notation $\theta d'une fonction de base. Cet article a pour but d'introduire quelques unes de ces fonctions de base, ainsi que de présenter la notation $\theta.

 

 

Table des matières

 

Ordre de grandeurs En général, un algorithme possède un paramètre $N$ qui affecte de manière significative son temps d'exécution. Ce paramètre est proportionnel à la taille de l'ensemble de données à traiter (taille de la chaîne de caractères, nombre de noeuds de l'arbre, nombre d'éléments dans la liste, ...). L'objectif est d'estimer le temps d'exécution de l'algorithme en fonction de ce paramètre, en le ramenant à l'une des fonctions de base qui sont définies dans la section suivante.

 

Ordres de grandeurs courants $1$
La majorité des instructions n'est exécutée qu'une seule fois, ou un petit nombre de fois; le temps d'exécution du programme est donc considéré constant. $\log(N)$
Un temps d'exécution logarithmique signifie que l'algorithme va aller très légèrement plus lentement à mesure que $N$ augmente. Typiquement, les programmes qui résolvent de grands problèmes en les divisant en de plus petits de complexité moindre font parties de cette catégorie. La base du logarithme change simplement quelque peu la constante: par exemple, pour $N 1000$" width="72" height="14" align="bottom" />, $\log(N) 3$" width="81" height="32" align="middle" /> si la base est $10$ et $10$ si la base est $2$. A chaque fois que $N$ double de valeur, $\log(N)$ augmente d'une constante, mais il ne double pas tant que $N$ n'augmente pas jusqu'à $N^2$. $N$
Le temps d'exécution est linéaire lorsque quelques opérations sont appliquées à chaque élément en entrée. Le temps d'exécution double chaque fois que $N$ double. Un temps de $N$ est optimal pour un algorithme ayant $N$ entrées à traiter, ou $N$ sorties à produire. $N\log(N)$
Cette classe est typique des programmes algorithmes qui résolvent un problème en le découpant en de plus petits, en les traitant indépendamment puis en combinant ensuite les solutions. Quand $N$ double, $N\log(N)$ vaut légèrement plus du double, mais tout en restant largement acceptable. $N^2$
Un temps d'exécution quadratique est surtout adapté à la résolution de petits problèmes et traite tous les couples d'éléments (d'où le $N^2 N \times N$" width="96" height="34" align="middle" />). Dans un tel cas, quand $N$ double, le temps d'exécution est multiplié par 4. $N^c$
Similairement au précédent, un temps d'exécution polynomiale ou géométrique va traiter tous les $c$-uplets d'éléments. Quand $N$ double, le temps d'exécution se voit multiplier par $2^c$, ce qui limite l'utilisation de tels algorithmes à de très petits problèmes. $2^N$
Un algorithme en temps d'exécution exponentiel est quasiment inutilisable dans la pratique: quand $N$ double, le temps d'exécution est élevé au carré. $N!$
Un algorithme en temps d'exécution factoriel n'est même pas envisageable, tant le temps d'exécution va grandir pour chaque unité de $N$ supplémentaire.

 

. Dans la pratique, le temps d'exécution d'un algorithme n'est pas rigoureusement exact à l'une des fonctions précédentes, mais plutôt à une constante multiplée par l'une de ces fonctions plus quelques petits termes. Les valeurs de cette constante et de ces termes supplémentaires dépendent des détails de l'implémentation et nécessitent une analyse plus précise de l'algorithme pour être déterminés. Pour faire simple, la constante est très liée au nombre d'instructions dans la boucle interne de l'algorithme. Toutefois, dans la plupart des cas, on dit simplement d'un algorithme que son temps d'exécution est logarithmique, linéaire, quadratique, ...via l'utilisation de la notation $\theta comme nous le verrons dans la section suivante.

 

Tableaux comparatifs

 

Tableau: Résultats de quelques fonctions utilisées dans l'analyse des algorithmes. $\log(N)$ $N$ $N\log(N)$ $N\log(N)^2$ $N^{3/2}$ $N^²$ 3 10 33 110 32 100 7 100 664 4 414 1 000 10 000 10 1 000 9 966 99 317 31 623 1 000 000 13 10 000 132 877 1 765 633 1 000 000 100 000 000 17 100 000 1 660 964 27 588 016 31 622 777 10 000 000 000 20 1 000 000 19 931 569 397 267 426 1 000 000 000 1 000 000 000 000

 


En étudiant le tableau 1, on peut, par exemple, se rendre compte de la grande différence qu'il existe entre $\log(N)$ et $N$. Par ailleurs, on remarque que pour de petites valeurs de $N$, $N^{3/2}$ se comporte mieux que $N\log(N)^2$, mais la situation s'inverse dès lors que $N$ est assez grand. De ce fait, l'analyse précise d'un algorithme nécessite également de savoir dans quelles conditions il sera utilisé.

 

 

Tableau: Temps de résolution en fonction de la complexité. Opérations Taille du problème de 1 million Taille du problème de 1 milliard par seconde $N$ $N\log(N)$ $N^2$ $N$ $N\log(N)$ $N^2$ $10^6$ Secondes Secondes Semaines Heures Heures Jamais $10^9$ Immédiat Immédiat Heures Secondes Secondes Décennies $10^{12}$ Immédiat Immédiat Secondes Immédiat Immédiat Semaines

 


Le tableau 2 montre le temps moyen de résolution d'un problème avec 1 million et 1 milliard d'éléments, en fonction de sa complexité et de la capacité de calcul de la machine. Ce tableau permet de se rendre compte qu'un algorithme rapide sera à même de résoudre un gros problème, même sur une machine lente, mais que l'inverse n'est pas vrai: une machine, même très performante, ne sera pas en mesure de résoudre un problème avec un algorithme en $N^2$ par exemple.

 

Notation $\theta En théorie de la complexité, on s'intéresse à l'équivalence asymptotique de fonctions positives à variables entières. Pour ce faire, on utilise la notation $\theta.

 

Définitions mathématique Avant de définir la notation $\theta, nous avons besoin de définir la notation $O$. Cette dernière, aussi appelée symbole de Landau (du nom du mathématicien allemand qui l'introduisit), est le symbole utilisé en mathématique pour décrire la dominance asymptotique de fonctions. On utilise la lettre $O$ car on parle de l'ordre de la fonction. Mathématiquement, on la définie comme suit:

 

Notation $O$ $f(x) O(g(x))$" width="111" height="32" align="middle" /> quand $x \forall x > N_0 \mid f(x) \mid \leq C_0 \mid g(x) \mid$" width="340" height="32" align="middle" /> (autrement dit, on est simplement en train de définir le fait que $f$ ne croît pas plus vite que $g$).

 

Notation $\theta En théorie de la complexité, on va surtout utiliser l'équivalence asymptotique, notée $\theta et définie par:

$f(n) et $f(n) avec $f(n) \mid f(x) \mid \geq M \mid g(x) \mid \forall x > x_0$" width="428" height="32" align="middle" />.

 

Utilisation On peut voir la notation $\theta comme un artifice mathématique permettant de s'affranchir des détails lorsque l'on analyse des algorithmes.

Cette notation permet d'écrire, en toute rigueur mathématique, le comportement d'une fonction, ou, dans notre cas, la complexité approximée d'un algorithme. En effet, si l'on prend l'exemple d'un algorithme de complexité $T(N) 3 \times N^2 + 2 \times N - 3$" width="202" height="34" align="middle" />, on l'associe à la classe $\theta(N^2)$. La notation $\theta permet donc de s'affranchir des constantes (ce qui est fondé puisque l'on peut dire qu'elles dépendent de l'implémentation de l'algorithme) et des termes plus faibles (puisqu'ils sont 'dominés'). Les constantes $C_0$ et $N_0$ de la définition de la notation $O$ servent à masquer les détails d'implémentation.

Ainsi, en écrivant $T(N) 3 \times N^2 + 2 \times N - 3 = \theta(N^2)$" width="265" height="34" align="middle" />, on reste rigoureux au niveau mathématique (la notation $\theta se chargeant de contenir les termes négligeables afin d'obtenir une égalité), et cela donne une approximation de la complexité de l'algorithme permettant de rapidement comparer différents algorithmes entre eux pour déterminer le plus performant.

 

. Pour résumer, on peut dire que la notation $\theta est utilisée dans trois buts:
  • borner les erreurs faites lorsque l'on ignore les petits termes dans les formules mathématiques
  • borner les erreurs faites lorsque l'on ignore des morceaux de l'algorithme qui influencent très peu le temps total dans le cadre de l'analyse en cours
  • classer les algorithmes selon les bornes supérieures de leur temps total d'exécution

 

Exemple d'application: QuickSort Nous allons expliquer comment calculer la complexité d'un algorithme à travers un exemple: l'algorithme de QuickSort.

 

Principe de QuickSort: Le principe consiste à séparer l'ensemble des éléments en deux parties. Pour effectuer la séparation, une valeur pivot est choisie. Ensuite les deux ensembles sont séparés par rapport à la valeur du pivot : ceux qui sont plus petits vont à gauche et ceux qui sont plus grand vont à droite, le pivot étant intercalé entre les deux.


\begin{algorithm}

 

Problème: Le problème de cet algorithme est la recherche du pivot. En effet, l'idéal consiste à prendre un pivot permettant de séparer les deux ensembles en deux parties de taille sensiblement égales. Dans la pratique, le pivot est le premier élément ou le dernier élément de l'ensemble à fractionner. En moyenne, les deux ensembles seront de taille sensiblement égale.

 

Complexité: La complexité du tri rapide pour trier une liste de $n$ éléments est égale à la complexité pour le tri de $p$ et de $q$ éléments ou $p+q+1=n$. Soit $T(n)=T(p)+T(q)+C$ (avec $C$ une constante). Dans le meilleur des cas, $p=q=n/2$, soit $T(n)=2T(q)$. Dans ce cas, la complexité de l'algorithme est en $\theta(n. Cependant, dans le pire cas, c'est-à-dire dans le cas où la liste est déjà triée, la complexité tombe alors dans $\theta(n^2)$. Pour contrer cet effet là, on effectue un mélange de la liste avant d'effectuer QuickSort (en s'assurant que la temps passé à effectuer ce mélange n'est pas trop important).

 

Bibliographie

 

1 Robert Sedgewick.
Algorithmes en C++.
Pearson Education, troisième edition, 2004.

 

2 wikipedia.
http://fr.wikipedia.org/wiki/Notation_O.

 

À propos de ce document... Complexité structurelle: ordre de grandeur et notation $\theta

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html complexite_structurelle.tex -dir website -split 0

The translation was initiated by on 2007-05-17