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

[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!!

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