Geek or not

Accueil du site > MOCA > Complexité des algorithmes

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 16 avril 2006.
3398 personnes ont affiché cette page et sa popularité est de 12.

Pebkac

Mots clefs

Complexité

I see dead pixels.

Outils

SYN

Complexité des algorithmes

Temps d’exécution d’un programme et complexité d’un algorithme

Exemple 1

On cherche à analyser le programme qui cherche l’indice du plus petit élément d’une portion d’un tableau.


Exemple de tableau pour analyse du temps

Algorithme

i : Indice du premier élément de la portion du tableau à analyser. ( $i=3$ dans l’exemple)
n : Indice du dernier élément de la portion du tableau à analyser. ( $n=7$ dans l’exemple)



indice_min = i

Pour j allant de i+1 à n faire

    Si T[j] < T[indice_min] alors

        indice_min = j

    Fin Si

Fin Pour

But
Evaluer le temps d’exécution du programme pour des données de taille $n$ . Pour le faire, il faut compter le nombre d’instructions effectuées dans l’algorithme. Les instructions basiques sont séparées en deux parties de base :

affectation : aff
comparaison : comp

Découpage en nombre d’instructions de base de l’algorithme

$indice\_min = i \rightarrow$ 1 aff
$j = i + 1 \rightarrow$ 1 aff
$j > n \rightarrow ((n-i)+1)$ comp
$j = j + 1 \rightarrow (n-i)$ aff
Si $T[j] < T[indice\_min] \rightarrow (n-i)$ comp
$indice\_min = j \rightarrow 0$ aff si $T[i]$ est minimal (le cas le plus favorable)
$\rightarrow (n-i)$ aff si les $T[i]$ sont classés de façon décroissante (le cas le plus défavorable)
$\rightarrow \frac{(n-i)}{2}$ aff dans le cas moyen

Somme des instructions
$T(n) = 1$ aff $+ 1$ aff $+ (n-i+1)$ comp $+ (n-i)$ aff $+ (n-i)$ comp $+ (n-i)$ aff $= [2+ 2(n-i)]$ aff $+ [2(n-i)+1]$ comp

Si $i=1 \Rightarrow T(n) = 2n$ aff $+ 2(n-1)$ comp

Le temps d’exécution est fonction [1]

du nombre d’éléments à traiter dans le tableau ( $n$ )
du temps d’exécution d’une opération d’affectation
du temps d’exécution d’une opération de comparaison

Dans la pratique, il est difficile de quantifier le temps que prend un ordinateur pour faire une affectation ou une comparaison, c’est pourquoi, dans une optique de simplification, on ne fera pas de différence entre les deux, une étape [2] regroupe les instructions d’affectation et de comparaison.

On pose $E =$ comp = aff

et obtient

$T(n) = 2nE +(2n-1)E = 4nE-E$

En prenant E = 1 unité de temps, on exprime $T(n)$ en fonction de n :
$T(n) = 4n -1$

Conclusion

$T(n)$ nous donne une information sur le nombre d’étapes exécutées par le programme et non plus sur le temps d’exécution.
Le nombre d’étapes exécutées par le programme croît linéairement en fonction de la taille $n$ des données à traiter.


Exemple de déroulement de l’algorithme du tri par sélection

Algorithme

T : tableau
n : nombre d’éléments du tableau



Pour i allant de 1 à n-1 faire

    indice_min = i

    Pour j allant de i+1 à n faire

        Si T[j] < T[indice_min] alors

            indice_min = j

        Fin Si

    Fin Pour

    Tmp = T[i]

    T[i] = T[indice_min]

    T[indice_min] = Tmp

Fin Pour

Evaluation du nombre d’étapes de l’algorithme
On évalue le nombre d’étapes de l’algorithme E = aff = comp :

$i = 1 \rightarrow 1E$
1 ère itération : (i = 1)

$i > n-1 \rightarrow 1 E$
$T(n) = [2 + 2(n-i)]E + [2(n-i)+1]E$
$\qquad = [2+2(n-1)]E + [2(n-1) +1 ]E \qquad$ si $i = 1$
$\qquad = 4(n-1)E + 3E$

$Tmp = T[i] \rightarrow 1E$
$T[i] = T[indice\_min] \rightarrow 1E$
$T[indice\_min] = Tmp \rightarrow 1E$
$i = i+1 \rightarrow 1E$

On à donc pour la première itération :
$T_1(n) = 4(n-1) E + 8E$

2ème itération : (i = 2)

$i > n-1 \rightarrow 1 E$
$T(n) = [2 + 2(n-i)]E + [2(n-i)+1]E$
$\qquad = [2+2(n-2)]E + [2(n-2) +1 ]E \qquad$ si $i = 2$
$\qquad = 4(n-2)E + 3E$

$Tmp = T[i] \rightarrow 1E$
$T[i] = T[indice\_min] \rightarrow 1E$
$T[indice\_min] = Tmp \rightarrow 1E$
$i = i+1 \rightarrow 1E$

On à donc pour la deuxième itération :
$T_2(n) = 4(n-2) E + 8E$

(n-1) ème itération : (i = n - 1)

$i > n-1 \rightarrow 1 E$
$T(n) = [2 + 2(n-i)]E + [2(n-i)+1]E$
$\qquad = [2+2(1)]E + [2(1) +1 ]E \qquad$ si $i = n-1$
$\qquad = 4(1)E + 3E$

$Tmp = T[i] \rightarrow 1 E$
$T[i] = T[indice\_min] \rightarrow 1 E$
$T[indice\_min] = Tmp \rightarrow 1 E$
$i = i+1 \rightarrow 1 E$

On a donc pour la (n-1) ème itération :
$T_{(n-1)}(n) = 4(1) E + 8E$

et enfin $i> n-1 \rightarrow 1E$

Au final il y a au total :

$T(n) = 1E + 4(n-1)E + 8E$
$\qquad\qquad+4(n-2)E + 8E$
$\qquad\qquad\enskip\vdots$
$\qquad\qquad+ 4(1)E + 8E$
$\qquad\qquad+1E$
$\qquad\qquad=2E+S(n)$

$S(n) = 4(n-1)E + 8E + 4(n-2)E + 8E + \ldots + 4(1)E + 8E$
$+ S(n) = 4(1)E + 8E + 4(2)E + 8E + \ldots + 4(n-1)E + 8E$
$=> 2S(n) = (4nE + 16E) + (4nE +16E) + \ldots + (4nE+16E) \rightarrow (n-1) fois$
$\qquad = (n-1)(4nE + 16E)$
$S(n) = \frac{4E(n-1)(n+4)}{2}$
$S(n) = 2E(n-1)(n+4)$

Si on néglige $2E$ on peut dire que $T(n) = S(n)$

$T(n) = 2E(n-1)(n+4)$
$\qquad = 2E (n^2 + 3n - 4)$
$\qquad = E(2n^2 + 3n - 8)$

Si $E = 1$ unité de temps alors :
$T(n) = 2n^2 + 6n -8$

Et donc si $n$ est grand, $T(n) = 2n^2$

On peut dire que :

Le calcul détaillé est long et fastidieux. Un ordre de grandeur du nombre d’étapes exécutées par l’algortihme suffit.
Pour cela on sélectionne une étape élémentaire [3] de l’algorithme pour obtenir un résultat d’un ordre de grandeur similaire à celui obtenu via le calcul détaillé, dans l’exemple précédent. L’étape élémentaire est $T[j] < T[indice\_min]$ (c’est l’étape qui exécutée le plus souvent dans l’algorithme).

Calcul du nombre d’étapes exécutées par l’algorithme en ne tenant compte que de l’étape élémentaire

1 ère itération : (i = 1)

$j = 2$ à n
$T_1(n) = (n-1)E$

2 ème itération : (i = 2)

$j = 3$ à n
$T_2(n) = (n-2)E$

(n - 1) ème itération : (i = n - 1)

$j = n$ à n
$T_{n-1}(n) = 1E$

Nombre total d’exécution de l’opération élémentaire :

$T(n) = T_1(n) + T_2(n) + \ldots + T_{n-1}(n)$
$= (n-1)E + (n-2)E + \ldots + 1E$
$+ = 1E + 2E + \ldots + (n-1)E$
$2T(n) = nE + nE + \ldots + nE \rightarrow (n-1)$ fois
$T(n) = \frac{n(n-1)E}{2} = E ( \frac{n^2}{2} - \frac{n}{2})$

Si $E = 1$ unité de temps, $T(n) = \frac{n^2}{2} - \frac{n}{2}$
Si $n$ est grand, on à $T(n) = \frac{n^2}{2}$

Définition de la complexité d’un algorithme

Soit $A$ un algorithme et $n$ une donnée d’entrée de $A$ . On appelle complexité de $A$ pour $n$ le nombre de fois que l’opération élémentaire est exécutée lors de l’exécution de $A$ sur $n$ .

pages : 1 2 >>

[1] Dans le cas où $i=1$
[2] Une étape vaut une unité de temps
[3] Instruction qui est exécutée le plus souvent dans le programme

Post Scriptum Bon, ok, c’est assez abstrait et obscur comme article.

Commentaires :

Complexité des algorithmes セフレ京子
セフレ恵梨香
セフレ若菜
セフレサチエ
セフレナナ
セフレ梓
セフレかおる
セフレりょう
セフレ理恵子
セフレまなみ
セフレ亜希子
セフレ優樹菜
セフレ真唯
セフレ芽以
セフレユウ
セフレ初音
セフレ真里
セフレ梢
セフレ絵梨
セフレまり子
セフレ来未
セフレ真琴

Posté par wanasite Site : えっちなｾｯｸｽﾌﾚﾝﾄﾞ
Répondre à ce commentaire

Poster un message