algorithm
Complexité de l'algorithme
Recherche…
Remarques
Tous les algorithmes sont une liste d'étapes pour résoudre un problème. Chaque étape a des dépendances sur un ensemble d'étapes précédentes ou le début de l'algorithme. Un petit problème peut ressembler à ceci:
Cette structure est appelée graphe acyclique dirigé, ou DAG en abrégé. Les liens entre chaque nœud du graphique représentent des dépendances dans l'ordre des opérations et il n'y a pas de cycle dans le graphique.
Comment se produisent les dépendances? Prenons par exemple le code suivant:
total = 0
for(i = 1; i < 10; i++)
total = total + i
Dans ce pseudo-code, chaque itération de la boucle for dépend du résultat de l'itération précédente car nous utilisons la valeur calculée dans l'itération précédente dans cette itération suivante. Le DAG de ce code peut ressembler à ceci:
Si vous comprenez cette représentation des algorithmes, vous pouvez l'utiliser pour comprendre la complexité de l'algorithme en termes de travail et de portée.
Travail
Work est le nombre réel d'opérations à exécuter pour atteindre l'objectif de l'algorithme pour une taille d'entrée donnée n .
Envergure
La portée est parfois appelée le chemin critique et est le plus petit nombre d'étapes qu'un algorithme doit effectuer pour atteindre l'objectif de l'algorithme.
L'image suivante met en évidence le graphique pour montrer les différences entre le travail et la durée sur notre échantillon DAG.
Le travail est le nombre de nœuds dans le graphique dans son ensemble. Ceci est représenté par le graphique ci-dessus à gauche. La portée est le chemin critique ou le plus long chemin du début à la fin. Lorsque le travail peut être effectué en parallèle, les nœuds surlignés en jaune à droite représentent la portée, le moins d’étapes requises. Lorsque le travail doit être effectué en série, la durée est la même que le travail.
Le travail et l'étendue peuvent être évalués indépendamment en termes d'analyse. La vitesse d'un algorithme est déterminée par la durée. La quantité de puissance de calcul requise est déterminée par le travail.
Notation Big Theta
Contrairement à la notation Big-O, qui ne représente que la limite supérieure du temps d'exécution pour certains algorithmes, Big-Theta est une limite étroite; les deux limites supérieure et inférieure. La limite étroite est plus précise, mais aussi plus difficile à calculer.
La notation Big-Theta est symétrique: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))
Une manière intuitive de le comprendre est que f(x) = Ө(g(x)) signifie que les graphes de f (x) et g (x) croissent au même rythme, ou que les graphes se comportent de la même manière pour les grands suffisamment de valeurs de x.
L'expression mathématique complète de la notation Big-Theta est la suivante:
Ө (f (x)) = {g: N 0 -> R et c 1 , c 2 , n 0 > 0, où c 1 <abs (g (n) / f (n)), pour tout n> n 0 et abs est la valeur absolue}
Un exemple
Si l'algorithme pour l'entrée n prend 42n^2 + 25n + 4 opérations pour finir, on dit que c'est O(n^2) , mais c'est aussi O(n^3) et O(n^100) . Cependant, c'est Ө(n^2) et ce n'est pas not Ө(n^3) , Ө(n^4) etc. L'algorithme qui est Ө(f(n)) est aussi O(f(n)) , mais non l'inverse!
Définition mathématique formelle
Ө(g(x)) est un ensemble de fonctions.
Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}
Comme Ө(g(x)) est un ensemble, nous pourrions écrire f(x) ∈ Ө(g(x)) pour indiquer que f(x) est un membre de Ө(g(x)) . Au lieu de cela, nous écrirons habituellement f(x) = Ө(g(x)) pour exprimer la même notion - c'est la manière commune.
Chaque fois que Ө(g(x)) apparaît dans une formule, nous l'interprétons comme représentant une fonction anonyme à laquelle nous ne tenons pas compte. Par exemple, l'équation T(n) = T(n/2) + Ө(n) signifie T(n) = T(n/2) + f(n) où f(n) est une fonction de l'ensemble Ө(n) .
Soit f et g deux fonctions définies sur un sous-ensemble des nombres réels. Nous écrivons f(x) = Ө(g(x)) comme x->infinity si et seulement si il y a des constantes positives K et L et un nombre réel x0 tel que:
K|g(x)| <= f(x) <= L|g(x)| pour tout x >= x0 .
La définition est égale à:
f(x) = O(g(x)) and f(x) = Ω(g(x))
Une méthode qui utilise des limites
si limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) c'est-à-dire que la limite existe et qu'elle est positive, alors f(x) = Ө(g(x))
Classes de complexité communes
| prénom | Notation | n = 10 | n = 100 |
|---|---|---|---|
| Constant | Ө (1) | 1 | 1 |
| Logarithmique | Ө (log (n)) | 3 | 7 |
| Linéaire | Ө (n) | dix | 100 |
| Linearithmique | Ө (n * log (n)) | 30 | 700 |
| Quadratique | Ө (n ^ 2) | 100 | 10 000 |
| Exponentiel | Ө (2 ^ n) | 1 024 | 1.267650e + 30 |
| Factorial | Ө (n!) | 3 628 800 | 9.332622e + 157 |
Notation Big-Omega
La notation Ω est utilisée pour la borne inférieure asymptotique.
Définition formelle
Soit f(n) et g(n) deux fonctions définies sur l'ensemble des nombres réels positifs. On écrit f(n) = Ω(g(n)) s'il y a des constantes positives c et n0 telles que:
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .
Remarques
f(n) = Ω(g(n)) signifie que f(n) augmente asymptotiquement plus lentement que g(n) . On peut aussi dire à propos de Ω(g(n)) lorsque l’analyse des algorithmes ne suffit pas pour énoncer sur Θ(g(n)) ou / et O(g(n)) .
De la définition des notations suit le théorème:
Pour deux fonctions f(n) et g(n) nous avons f(n) = Ө(g(n)) si et seulement si f(n) = O(g(n)) and f(n) = Ω(g(n)) .
La notation graphique Ω peut être représentée comme suit:
Par exemple, on peut avoir f(n) = 3n^2 + 5n - 4 . Alors f(n) = Ω(n^2) . Il est également correct que f(n) = Ω(n) , ou même f(n) = Ω(1) .
Un autre exemple pour résoudre l'algorithme d'appariement parfait: Si le nombre de sommets est impair, alors la sortie "Pas de correspondance parfaite" est utilisée, sinon essayez tous les appariements possibles.
Nous voudrions dire que l'algorithme nécessite un temps exponentiel mais en fait vous ne pouvez pas prouver une limite inférieure Ω(n^2) utilisant la définition habituelle de Ω puisque l'algorithme s'exécute en temps linéaire pour n impair. Nous devrions plutôt définir f(n)=Ω(g(n)) en disant pour une constante c>0 , f(n)≥ cg(n) pour un nombre infini de n . Cela donne une belle correspondance entre les limites supérieure et inférieure: f(n)=Ω(g(n)) ssi f(n) != o(g(n)) .
Les références
La définition formelle et le théorème sont tirés du livre "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction aux algorithmes".
Comparaison des notations asymptotiques
Soit f(n) et g(n) deux fonctions définies sur l'ensemble des nombres réels positifs, c, c1, c2, n0 sont des constantes réelles positives.
| Notation | f (n) = O (g (n)) | f (n) = Ω (g (n)) | f (n) = Θ (g (n)) | f (n) = o (g (n)) | f (n) = ω (g (n)) |
|---|---|---|---|---|---|
| Définition formelle | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n) | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n) | ∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n) |
Analogie entre la comparaison asymptotique des nombres f, g et réels a, b | a ≤ b | a ≥ b | a = b | a < b | a > b |
| Exemple | 7n + 10 = O(n^2 + n - 9) | n^3 - 34 = Ω(10n^2 - 7n + 1) | 1/2 n^2 - 7n = Θ(n^2) | 5n^2 = o(n^3) | 7n^2 = ω(n) |
| Interprétation graphique |  | |  |
Les notations asymptotiques peuvent être représentées sur un diagramme de Venn comme suit: 
Liens
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction aux algorithmes.