précédent | suivant | table des matières

Définitions

Algorithme : indiquer comment résoudre un problème. (ce n’est pas forcément lié à un programme informatique, une recette de cuisine est un algorithme dont l’exécution aboutit à un plat plus ou moins savoureux). On ne s’intéressera qu’aux algorithmes destinés à produire des programmes, pour une machine basée sur le modèle de Von Neumann.

Depuis de nombreuses années, les machines sont de plus en plus rapides et puissantes, avec de plus en plus de mémoire ... Mais les problèmes qu'on aborde sont souvent de plus en plus complexes, donc de plus en plus gourmands en temps et en ressources. Le choix d'un algorithme approprié et efficace reste, et restera, toujours important.

Exemple :

Considérons deux algorithmes de recherche dans un ensemble ordonné de n éléments :

• Algorithme de recherche séquentielle : le temps de recherche est proportionnel à n
• Algorithme de recherche dichotomique : le temps de recherche est proportionnel à log₂(n)

Analyse des algorithmes.

L’analyse des algorithmes consiste à déterminer les ressources en temps, ou en espace mémoire (ou d’autre ressources telles que les processeurs, …) nécessaires à l’exécution de l’algorithme. Ce calcul dépend de la taille de la donnée, qui peut être sa grandeur (par exemple calcul de n^ième nombre de Fibonacci, ou du n^ième nombre premier), ou son nombre d’éléments (par exemple ordonner un tableau de n éléments).

Le choix des opérations de base est très important : on n’a pas forcément les mêmes résultats quand on choisit de compter le nombre de comparaisons de 2 éléments, ou le nombre d'échanges de 2 éléments comme opération de base dans un tri de tableau.

Exemple : tri d’un tableau de n éléments.

• L’algorithme de tri d’un tableau par sélection et échange, a un comportement en n, quel que soit le tableau donné.
• L’algorithme de tri d’un tableau par l’algorithme de tri rapide, a un comportement en n² dans le pire cas, un comportement en n×log₂(n)dans le meilleur cas et également en moyenne.

Ordre de complexité.

O.

Définition de la notation O (grand O) : étant donnée une fonction f(n), O(f(n)) est l'ensemble des fonctions g(n) telles qu'il existe une constante positive réelle c et un entier non négatif N tel que pour tout n>N, g(n) < c × f (n).

La notation O(f) décrit le comportement asymptotique d'une fonction, c'est à dire pour des grandes valeurs. En d'autres mots, g est O(f) lorsque, pour des valeurs suffisamment grandes de n (n > N), le rapport g(n)/f (n) reste toujours bornée par c.

Exemple :

• n²+10×n ∈O(n²) pour n≥1 en effet : n²+10×n ≤ n²+10×n² = 11×n² donc c=11 et N=1
• n²+10×n ∈O(n²) pour n≥10 en effet : n²+10×n ≤ n²+n×n = 2×n² donc c=2 et N=10
• n ∈O(n²) pour n≥1 en effet : n ≤ n² donc c=1 et N=1

Ω.

Définition de la notation Ω (grand oméga) : étant donnée une fonction f(n), Ω(f(n)) est l'ensemble des fonctions g(n) telles qu'il existe une constante positive réelle c et un entier non négatif N tel que pour tout n>N, g(n) ≥ c × f (n). En d'autres mots, f(n) est une (forme de) borne inférieure asymptotique pour les fonctions dans Ω(f(n)), alors qu'elle est une borne supérieure asymptotique pour les fonctions dans O(f(n)).

Si une fonction est à la fois dans Ω(f(n)) et dans O(f(n)), alors on peut en conclure que son taux de croissance est équivalent à celui de f(n).

Θ.

Définition de la notation Θ (grand thêta) : étant donnée une fonction f(n), Θ(f(n)) est l'ensemble des fonctions g(n) telles qu'il existe une constante positive réelle c, une constante positive réelle d, et un entier non négatif N tel que pour tout n>N, c× f(n) ≤ g(n) ≤ d × f(n).

En d'autres mots : Θ(f(n))=Ω(f(n))∩O(f(n))

o.

Définition de la notation o (petit o) : Etant donnée une fonction f(n), o(f(n)) est l'ensemble des fonctions g(n) telles que pour toute constante positive réelle c, il existe un entier non négatif N tel que pour tout n>N, g(n) ≤ c × f(n)

En d'autres mots, g(n) est dominée asymptotiquement de façon stricte par f(n). Ainsi, on a la propriété suivante : g(n)∈o(f(n)) ⇒ g(n) ∈ O(f(n)) - &Omega(f(n)).

La notation Θ sépare l’ensemble des fonctions de complexité en une collection de sous-ensembles disjoints (classes d’équivalence). Pour l’analyse des algorithmes, on utilise donc le représentant le plus simple Θ(1), Θ(n) …

Propriétés.

O, Θ et Ω ont les propriétés suivantes :

Si f₁(n) ∈ O(g₁(n)) et f₂(n) ∈ O(g₂(n)) alors (f₁+f₂)(n) ∈ O(g₁(n)+g₂(n))

Si f₁(n) ∈ O(g₁(n)) et f₂(n) ∈ O(g₂(n)) alors (f₁+f₂)(n) ∈ O(max(g₁(n)+g₂(n)))

Si f₁(n) ∈ O(g₁(n)) et f₂(n) ∈ O(g₂(n)) alors (f₁×f₂)(n) ∈ O(g₁(n)×g₂(n))

Ces propriétés sont utiles pour simplifier l'analyse d'algorithmes comme suit : Supposons que les temps d'exécution des opérations A et B soient respectivement O(f(n)) et O(g(n)). Alors le temps pour A suivi de B sera de O(f (n) + g(n)).

Notons que dans le cas où, par exemple, f domine g de façon stricte (g ∈ o(f )), on peut alors en conclure que A suivi de B est de temps O(f(n)). De même, si f ∈ Θ((g)), le temps sera alors simplement O(f(n)).

Supposons que chaque exécution d'une boucle requiert un temps d'exécution O(f(n)) et que la boucle est exécutée O(g(n)) fois. Alors le temps pour la boucle sera O(f(n) × g(n)).

Encore une fois, ces simplifications restent valides si on remplace O par Θ ou &Omega.

Autres propriétés :

1. g(n) ∈ O(f(n)) ⇔ f(n) ∈ Ω(g(n))
2. g(n) ∈ Θ(f(n)) ⇔ f(n) ∈ Θ(g(n))
3. Si b > 1 et a > 1, alors log_a(n) ∈ log_b(n) (Le logarithme utilisé n'a pas d'importance)
4. Si b > a > 0, alors aⁿ ∈ o(bⁿ) (toutes les fonctions exponentielles sont dans des classes différentes)
5. Pour tout a > 0, aⁿ ∈ o(n!) ( n! est la pire des fonctions de complexité exponentielle)
6. Soit les fonctions de complexité ordonnées comme suit, où k > j > 2 et b > a > 1 : Θ(1) Θ(lg n) Θ(n) Θ(n lg n) Θ(n²) Θ(n^j) Θ(n^k) Θ(aⁿ) Θ(bⁿ) Θ(n!). Si une fonction g(n) est dans une catégorie à gauche de la catégorie contenant f(n), alors g(n) ∈ o(f(n)).
7. Si c≥0, d>0, g(n) ∈ O(f(n)) et h(n) ∈ Θ(f(n)) alors c×g(n)+d×h(n) ∈ f(n)

De façon plus générale, la propriété 6 indique que toute fonction logarithmique est éventuellement meilleure que n'importe quelle fonction polynomiale, que toute fonction polynomiale est éventuellement meilleure que n'importe quelle fonction exponentielle, et que toute fonction exponentielle est meilleure que la fonction factorielle. Les propriétés 6 et 7 peuvent être utilisées de façon répétitive pour simplifier des expressions et déterminer la catégorie la plus simple à laquelle appartient une fonction.

Exemple : On veut montrer que 5n + 3 lg n + 10 n lg n + 7n² ∈ Θ(n²) :

• 7n² ∈ Θ(n²)
• 10 n lg n + 7n² ∈ Θ(n²)
• 3 lg n + 10 n lg n + 7n² ∈ Θ(n²)
• 5n + 3 lg n + 10 n lg n + 7n² ∈ Θ(n²)

Remarques.

Remarque sur la notation

De nombreux auteurs utilisent plutôt les notations suivantes :

• f(n) = Θ(n²) plutôt que f(n) ∈ Θ(n²).
• f(n) = O(n²) plutôt que f(n) &isin O(n²).
• Etc.

La notation ensembliste semble plus correcte en termes de définitions mathématiques. Toutefois, selon l'occasion, nous utiliserons l'une ou l'autre des notations.

Remarques sur l'utilisation de O versus Ω versus Θ

La notation O décrit une borne supérieure. On peut donc l'utiliser pour obtenir une borne supérieure sur le temps d'exécution dans le pire des cas. Evidemment, ce faisant, on obtient aussi une borne supérieure pour des données quelconques.

Par contre, on peut aussi utiliser Θ pour décrire une borne, à la fois inférieure et supérieure, du temps d'exécution dans le pire des cas. Evidemment, cela ne signifie alors pas qu'une exécution de l'algorithme sur des données arbitraires sera bornée par Θ.

La notation Ω, quant à elle, décrit une borne inférieure. Habituellement, on l'utilise donc pour borner le temps d'exécution dans le meilleur des cas. Par contre, on peut aussi l'utiliser pour décrire une borne inférieure dans le pire cas.

Par exemple, soit l'algorithme suivant, où le temps d'exécution de chacune des parties est indiqué en commentaires :

void f(int[] t){
   for( int i =0 ; i<t.length; ++i){
     if(test(i))
        f1(); // Θ(1)
     else
        f2(); // Θ(n)
   }
}

• f est O(n²).
• f est Ω(n).
• Dans le pire des cas, f est Θ(n²).
• Dans le meilleur des cas, f est Θ(n).

haut de la page