Discussion :

[soussou80]

bonsoir tout le monde,
j'ai un probleme dans le calcul de la complexité?
j'ai cherché mais j'a pas trouvé un bon tutoriel ou le bon cours qui peut m'aider surtout que je suis débutante

par exemple j'ai l'algo suivant:

Code :

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

1
2
3
4
for i=1 to N do
{ for j=1 to i do
     operation;
}

ou par exemple si j'ai:

Code :

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

1
2
3
4
5
6
i=1;
j=1;
if((i<n) && (j<n)) then
 i++;
else
 j++;

SVP quelcun peut me donner un bon lien pour mieux comprendre comment calculer la complexité et si possible quelcun qui peut m'aider à calculer la compl de ces 2 algo ci dessus
BN et meci d'avance

[Zavonen]

Pour le premier, par exemple, tu as N boucles
Pour la première boucle tu as 1 sous boucle, pour la seconde 2 et ainsi de suite.
Le nombre total des boucles est donc 1+2+...+N= N(N+1)/2
Admettons maintenant que 'operation' est à temps constant O(1). Ton algo sera en O(N²/2)
car N(N+1)/2= N²/2 + N +1/2 et que pour N grand N+1/2 est négligeable devant N²/2

[soussou80]

Bonjour,
merci bien Zavonen d'avoir me répondre, mais SVP est ce que vous pouvez me dire comment calculer la comlexité pour le 2eme exemple car je sais pas c'est quoi la regle qui me permet da calculer la complexité en cas de condition(if condition then i else j)
merci davance

[Zavonen]

Pour la seconde c'est difficile à dire.
Il ne s'agit pas à proprement parler d'algorithme mais d'une brève suite d'instructions.
2 affectations, 2 tests, une incrémentation.
La 'complexité' est la somme des 'complexités' de chacune.
La 'complexité' de chacune ne peut être définie indépendamment du langage du compilateur, du processeur, etc...
Je ne peux guère t'en dire plus.
On s'intéresse à ces questions quand de telles suites se trouvent dans des boucles répétées un très grand nombre de fois. On sait par exemple que dans presque tous les systèmes, un test est beaucoup plus rapide qu'un échange (trois affectations), c'est pourquoi on va privilégier des algorithmes qui pour un même O en fonction de N privilégie les tests par rapport aux échanges.

[ToTo13]

Bonjour,

le calcul de Zavonen est bien évidemment juste, mais petite précision, lorsque tu donnes la complexité, tu ne mets pas la constante. Donc ton algo a une complexité en O(N²).

Sinon pour ton algo 2, une condition a une complexité en 0(1).

[Zavonen]

Sinon pour ton algo 2, une condition a une complexité en 0(1).

Plus précisément on 'sort' la constante, algo en (1/2)O(N²).
Parmi les algos en O(N²) un algo en 1/2O(N²) est quand même 4 fois plus rapide qu'un algo en 2O(N²). Il n'y a pas de petites économies...
C'est par de telles considérations qu'on peut dire qu'un tri par insertion et meilleur qu'un tri à bulles, alors qu'ils sont tous du même ordre polynomial.

[soussou80]

merci bien à vous tous
just une demande est ce quelcun a un bon cours qui peux m'aider à mieu comprendre la complexité et si c'est possible des exerxices ou des exemple.
j'ai vraiment cherché mais j'ai pas trouvé une chose importatnte
bn

[ToTo13]

Bonjour,

on trouve toujours son bonheur sur Développez.

Sinon en tapant Cours Algorithmique dans Google, le premier et troisième lien ont l'air très bien.

Une référence en la matière est un livre nommé "Introduction à l'algorithmique". Un beau pavé mais très complet et très utile.

[soussou80]

merci Toto13 pour les liens à vous meme Zavonen
j'ai une autre question, est ce que vous pouvez m'aider vous meme à mieux comprendre meme un peut la complexité.
Par exemple j'ai trouvé quelques application sans correction j'ai essayé de trouver la complexité mais je sais pas si ce que j'ai fait est just ou non
exp:
seq1:

Code :

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

1
2
3
4
5
6
 i=1
while(i<n) do
{
    i=2*i;
    op;
}

MaSol:T(n)=O(n)

seq2:

Code :

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

1
2
3
4
5
6
7
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))
question: toujours lorsque j'ai while T(n)=log(n)????

seq3:

Code :

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

1
2
3
4
5
6
7
i=1
while(i<n) do
     i=2*i;
     for j=1 to i do
       op
     end for
end while

MaSol: T(n)=!!!!!

seq4:

Code :

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

1
2
3
4
5
6
7
i=1
for j=1 to n do
    i=2*i;
end for
for j=1 to i do
   op;
end for

MaSol: T(n)=O(n.2^n) => n pour la 1ere boucle for et 2^n pour la 2emm


seq5:

Code :

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

1
2
3
while(i<n) do
   i=i*i;
end while

MaSol=???

seq6:

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 toi do
        for m=1 to k do
             op;
       end for
    end for
end for

MaSol: T(n)=O(n.n.2^n)=O(n^2.2^n)???


Bon je sais que cen'est trop mais
Merci

[b_reda31]

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).

[ToTo13]

Bonjour,

bon ok... +1 avec reda, j'ai tout lu de travers et raté les multiplications sur i et j.

[soussou80]

Bonsoir à tous,
J'ai tjrs des problemes avec le calcul de la complexité
Ce que je veux savoir, si la complexité change para rapport au type d'operations???
Par exemple si on calcule la complexité d'un algo en nombre d'operation de comparaisons, la complexité ne sera pas la meme pour le meme algo mais cette fois en nombre d'addition par exemple????

Pour l'algo suivant:

Code C :

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

1
2
3
4
5
6
7
8
i=1;
while(i<=N && t[i])<>x)
{
    i=i+1.
}
 
if(i>N) return false;
else return true;

Ici on désire calculer la complexité en nombre de comparaison, mais ici je vois pas d'operaton de comparaison ds la boucle while, juste affectation "i=i+1;"

SVP vous pouvez m'aider à répondre à ma question et à m'aider à calculer la complexité d'un te type d'algo
BN et merci d'avance

[ToTo13]

Bonjour,

il y a quand même des comparaisons dans les conditions de la boucle while : i<=N && t[i])<>x

Donc dans le pire des cas, tu auras :
- 2N comparaisons
- N incrémentations.

[soussou80]

Bonsoir,
Merci bien Toto de me répondre
Mais j'ai un autre problème:
Est ce que dans chaque algo je dois calculer la complexité au meilleure, au pire et au moyenne des cas ou bien seulement lorsqu'ils me le demande???
Sinon, en cas générale je dois calculer la complexité au pire des cas???

dans cet algo:

Code C :

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

1
2
3
4
5
6
7
8
9
 
int min=max=t[0];
for(int i=1;i<n;i++)
{
      if(t[i]>max)
             max=t[i];
      else if(t[i]<min)
             min=t[i];
}

J'ai trouvé cet exercice corrigé sur net mais j'ai pas compri la correction, correction non expliqué.
En fait, dans la correction la complexité est calculé au moyenne des cas:
T(n)moyenne=3/2(n-1).J'ai pas copmri la solution en fait au moyenne des cas la complexité doit etre egale à (n-1)/2 ou non???
Bonne nuit et j'espere que je trouve la réponse

[ToTo13]

Bonsoir,

Merci d'utiliser les balises CODE lorsque tu écris du code (le bouton #).


Sauf si c'est précisé, la complexité est calculée dans le pire des cas.
Pour certains algorithmes, comme le QuickSort, la complexité dans le pire des cas n'est pas représentative. En moyenne sa complexité est en O(N log N).

Pour ce qui est de la complexité de cet algorithme, elle est calculée en moyenne pour le nombre de comparaison je suppose. Je ne saurai donner la théorie exacte, mais voilà :
- il y a (N-1) itérations.
- à chaque itération on fait au moins une comparaison, mais parfois on peut faire la deuxième.
- dans le pire des cas, donc Max=T[0], donc on fait systématiquement la deuxième comparaison et donc on fait 2N comparaisons. Dans le meilleur des cas, le tableau est classé par ordre croissant, donc à chaque itération on affecte Max et donc on ne fait qu'une comparaison O(N). Ainsi en moyenne la complexité est en 3/2 (N-1).

[Mademoiz-ailes]

Pour le premier, par exemple, tu as N boucles
Pour la première boucle tu as 1 sous boucle, pour la seconde 2 et ainsi de suite.
Le nombre total des boucles est donc 1+2+...+N= N(N+1)/2
Admettons maintenant que 'operation' est à temps constant O(1). Ton algo sera en O(N²/2)
car N(N+1)/2= N²/2 + N +1/2 et que pour N grand N+1/2 est négligeable devant N²/2

Bonsoir;
Pour cette solution, peut-on raisonner de cette maniere :
1ére boucle, on a N iterations (N-1+1)
2éme boucle, on a N itérations (N-1+1) (le j va de 1 à N ou i c'est pareil)
Total = O(n) * O(n) = 0(n²)

[pitifarfadet974]

Bonjour,

après avoir tout lu, j'ai encore du mal avec le calcule de complexité, pourriez vous corriger mon raisonnement?

AlgoCinq(n) :
1. x <- 0
2. pour i <- 1 à n faire :
3.

pour j <- 1 à 5 faire :

4.

x <- x + 5

5. renvoie x

AlgoCinq(n) :
1. 1
2. 1+2+...+n = (n(n+1))/2)
3. (5-j)
4. 1

donc on a T(n)= 1+ (1*(5-j)*(n(n+1))/2 +2 (on ajoute 1 pour l'incrémentation de i et 1 pour j))

T(n)= 1+(2+5*(n(n+1))/2) = 3+ (5n^2/2)+ (5n/2)
quand n grand
donc l'algo est en O(n^2/2) donc quadratique.

Est-ce que c'est correcte?
merci d'avance

[b_reda31]

Bonjour,
Tout d'abord il faut utiliser les mots-clé FinPour afin de lever l'ambiguité et délimiter le bloc qui sera itéré :

Code :

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

1
2
3
4
5
6
7
8
9
10
AlgoCinq(n) :
1.  x <- 0
 
2.   pour i <- 1 à n faire :
3.      pour j <- 1 à 5 faire :
4.            x <- x + 5
         FinPour
      FinPour
 
5. renvoie x

Les instructions 1 et 5 sont exécutées qu'une seule fois (Hors de la boucle).
L'instruction 4 (x <- x + 5) est exécutée 5*n Fois (5 Fois pour chaque valeur de i, et i varie de 1 à N).
En ignorant les tests des instruction 2 et 3 on a :
T(n) = 1 + 5*n + 1

La complexité est donc en O(k*n) , tel que k=5 soit O(n).

[pitifarfadet974]

bonjour,

merci et désolé mais j'ai recopier l'énoncé tel quel et il n'y avait pas les mont-clés "finpour".

Je ne comprend pas en faits pourquoi "En ignorant les tests des instruction 2 et 3" ??

Car en terme de pas, ces instructions compte et donc joue sur le
temps d'éxécution!!

[b_reda31]

Je ne comprend pas en faits pourquoi "En ignorant les tests des instruction 2 et 3" ??

Car en terme de pas, ces instructions compte et donc joue sur le
temps d'éxécution!!

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

Lorsque la complexité est polynomiale, elle est exprimée en O(.) par le degré du polynôme.

Ex :

O(k1*n^3 + k2*n^2 + k3*n + k4) = O(n^3).