Discussion :

[souviron34]

En termes de temps d'exécution,Oui. Mais en terme de complexité en O(.) c'est négligeable.

c'est surtout que la définition de la complexité est par rapport une valeur considérée comme paramètre

Les "opérations" simples (telles que fnpour etc) ne sont en général pas considérée comme des paramètres...

Dans un calcul de complexité en général, on évalue par rapport à la taille d'un élément entrant caractéristique...

Il y a un seul cas je crois (je ne me souviens plus du nom) où l'on veut calculer la complexit en termes d'opérations élémentaires...

Le cas général est donc par rapport à la taille du paramètre d'entrée..

Par exemple, dans le quicksort, bien évidemment on calcule la complexité par rapport au nombre d'éléments à trier..

[davly]

Bonjour,

Comme expliqué précédemment, le paramètre joue beaucoup sur ton calcul de complexité, tu peux comparer le nombre d’accès à un tableau, le nombre d'itération de tes boucles, le nombre de comparaison (if), nb d'appel de fonctions.. etc.

Généralement tu calcules une compléxité pour comparer deux algo qui font la même chose.

Ce calcul se fait de 3 façons différentes, le calcul de la compléxité dans le pire des cas, dans le meilleurs des cas et la compléxité moyenne.

Quand tu compares deux algo il faut s'assurer de partir sur la même base de comparaison.
Pour les algo un peu complexe, c'est le nombre d'itération des boucles qui va jouer beaucoup, ou appel de fonction si algo récursive.


David.

[lyess]

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
seq1:
i=1
while(i<n) do
{
i=2*i;
op;
}
MaSol:T(n)=O(n)

Je ne pense pas que Seq1 soit O(n),pour voir ça il suffit de le dérouler avec un exemple.
Ici j’ai pris le cas particulier ou n=8

i = 1 = 2^0 -------- 1 exécution de « op »
i = 2 = 2^1 -------- 1 exécution de « op »
i = 4 = 2^2 -------- 1 exécution de « op »
i = 8 = 2^3 -------- Fin de la condition de la boucle.

Pour n=8,l’opération « op » s’est exécutée 3 fois,à travers l’exemple on peut déduire que d’une manière générale l’opération « op » s’exécute « k » fois tel que 2^(k-1)<n<=2^k
Dans le meilleurs des cas on a n=2^k donc k=Log2 n
Donc T(n) = Log2 n.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
seq2:
for i=1 to n do
j=1
while(j<n) do
j=2*j;
op;
end while
end for
MaSol: T(n)=O(n.log(n))

Ici Seq1 est exécuté n fois donc ça m'a l'air correcte. T(n) = O(n Log2 n).

SVP, dites moi comment vous avez trouvé n(log2^n) ??
Moi j'ai trouvé log(2^n) parce que pour n=8, la deuxième boucle s'exécute 3 fois, donc c'est comme le seq1 non ?!

[ToTo13]

SVP, dites moi comment vous avez trouvé n(log2^n) ??
Moi j'ai trouvé log(2^n) parce que pour n=8, la deuxième boucle s'exécute 3 fois, donc c'est comme le seq1 non ?!

La deuxième boucle se trouve dans la première.

[lyess]

SVP, comment peut-on calculer la Complexité de cet Algorithme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
Algo()
{
 
    i=1
    while(i<n) do
        i=2*i;
        for j=1 to i do
            <operation>;
        end for
    end while
 
}

Merci d'avance.

[b_reda31]

Il ne faut pas hésiter à faire le déroulement de l'algorithme en prenant plusieurs valeurs pour n. De cette façon vous allez pouvoir y voir plus clair.

Prenons l'exemple où n = 8 :

Etant donnée qu'on cherche à calculer la complexité asymptotique, on se limitera au calcul du nombre de fois que l'instruction <Op> est exécutée.

• i = 1<n
  
  • i = i * 2 = 2
    
    • j = 1 <operation>
    
    
    • j = 2 <operation>

• i = 2<n
  
  • i = i * 2 = 4
    
    • j = 1 <operation>
    
    
    • j = 2 <operation>
    
    
    • j = 3 <operation>
    
    
    • j = 4 <operation>

• i = 4<n
  
  • i = i * 2 = 8
    
    • j = 1 <operation>
    
    
    • j = 2 <operation>
    
    
    • j = 3 <operation>
    
    
    • j = 4 <operation>
    
    
    • j = 5 <operation>
    
    
    
    • j = 6 <operation>
    
    
    
    • j = 7 <operation>
    
    
    
    • j = 8 <operation>

Dans notre exemple, l'opération est exécutée 2 + 4 + 8 fois. Et dans un cas général on a : 2 + 4 + 8 + 16 + . . . + m
Tel que m est la plus petite puissance de 2 supérieure ou égale à n.
Dans le meilleur des cas on a m = n :
2 + 4 + 8 + ... + n.
C'est donc la somme des terme d'une suite géométrique à raison égale à 2.


le nombre de terme k représente le degré de puissance de n. soit k = log2(n).
(dans notre exmple k = 3, si on avait n = 16 ==> k = 4...etc).
En appliquant la formule de la suite, on obtient alors une complexité linéaire O(n).

[lyess]

Merci beaucoup pour votre gentil retour.
Oui j'ai déroulé l'algorithme sauf que je me suis bloquée au niveau de la borne supérieure de la somme...

D'après ce que j'ai compris, la formule finale de la somme est la suivante:
∑(2^k) tel que: k varie de 1 à Log2(n)

N'est ce pas?

[b_reda31]

D'après ce que j'ai compris, la formule finale de la somme est la suivante:
∑(2^k) tel que: k varie de 1 à Log2(n)

N'est ce pas?

Oui, dans le cas où "n" est une puissance de deux (n = 2^k). C'est d'ailleurs le meilleur des cas.
Le pire des cas se produit lorsque "n" est de la forme (2^k) + 1... si je ne me trompe pas ...on aurait ici : ∑(2^k) tel que: k varie de 1 à Log2(m) où m est la plus petite puissance de 2 supérieure à n.
Mais dans les deux cas l'algo est en O(n)... sauf erreur de ma part

[lyess]

Merci beaucoup! Bonne journée.

[mannour85]

bonjour merci la description des séquences de complexité précédente bon j'ai cette séquence si possible de m'aider à calculer sa complexité

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
i ← 1
FOR k ← 1 TO n DO
  i ← 2*i
  FOR L ← 1 TO i DO
    FOR m ← 1 TO k DO
      Opération ;
    END-FOR
  END-FOR
END-FOR

[yahiko]

Tout d'abord, il est (fortement) recommandé d'indenter son code. C'est beaucoup plus lisible.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
i ← 1
FOR k ← 1 TO n DO
  i ← 2*i
  FOR L ← 1 TO i DO
    FOR m ← 1 TO k DO
      Opération ;
    END-FOR
  END-FOR
END-FOR

L'exemple est simple. On remarque qu'il y a 3 boucles imbriquées. Et il faut sans doute supposer que Opération s'effectue en temps constant. Le but est donc de déterminer le nombre d'itérations pour chacune des boucles et de les multiplier entre elles puisqu'elles sont imbriquées.

• Combien d'opérations x pour la boucle FOR k ?
• Combien d'opérations y pour la boucle FOR l ?
• Combien d'opérations z pour la boucle FOR m ?

Connaissant x, y et z, le produit de ces nombres x * y * z te donnera la complexité de l'algorithme en fonction d'un nombre d'opérations N.

La seule petite difficulté de cet exemple réside dans le calcul du nombre d'opérations z de la boucle FOR m. Il faudra faire un peu de dénombrement, mais rien de bien méchant à priori.

Bon courage.

[mannour85]

merci pour votre réponse ; pour mon cours je pense que se sera ordre de N à la puissance trois car X et Z vont êtres N fois alors que Y est N/2 donc sera O(N)*O(N/2)*O(N)=O(N^3) n'est ce pas ou c'est faux

[yahiko]

Ce n'est pas exact.
Pour s'en convaincre, le mieux est de faire des tests avec différentes valeurs de N.

[mannour85]

bonsoir j'ai vérifié encore donc la deuxième boucle d'ordre deux seulement donc pour n=4
k=1
i=2
l=1....donc m=1 une première opération
l=2....donc m=2 une deuxième opération ça fait 2 op

k=2
i=2
l=1 donc m=1 et m=2 donc 2op
l=2 donc m=1 et m=2 donc 2op ça fait 4 op

k=3
i=2
l=1 donc m=1 et m=2 et m=3 donc 3op
l=2 donc m=1 et m=2 et m=3 donc 3op ça fait 6 op

k=4
i=2
l=1 donc m=1 et m=2 et m=3 et m=4 donc 4op
l=2 donc m=1 et m=2 et m=3 et m=4 donc 4op ça fait 8op
alors
la somme 2+4+6+8=20op pour n=4 donc c'est de l'ordre de O(n^2)

j'attends votre remarque et merciii

[yahiko]

Ca me semble pas trop mal.
Il faudrait démontrer plus formellement ton hypothèse.
Je t'invite à lire les précédents posts pour voir comment t'y prendre.
On peut utiliser les séries ou les dénombrements, ça revient au même.