Discussion :

[antares56]

Bonjour à tous,
Je bosse en ce moment sur la notion de complexité, mais je ne saisis pas tout... je n'arrive pas à comprendre la méthode pour calculer une complexité d'un algo, par exemple on m'a donné ces exemples à faire :

Code :

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

1
2
3
4
5
6
7
8
9
 
void f(int [] t){
for(int i=0; i < t.length; i++){
t[i]=t[i]+1;
}
for(int i=0; i < t.length; i++){
t[i]=t[i]*2;
}
}

Code :

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

1
2
3
4
5
6
7
8
9
10
 
int f(int i){
boolean trouve=false;
int j=1;
while(!trouve){
if (j>=100) { trouve=true;}
j=j*2;
}
return j;
}

Code :

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

1
2
3
4
5
6
 
void f(int [] t){
for(int i=0; i < t.length; i++){
t[i]=t[i]*t[i];
}
}

Pour ces exemples, comment feriez vous pour trouver la complexité ? Quelle technique utiliseriez vous?
Merci de vos réponses !

[WhiteCrow]

Bonjour,

Souvent on entend parler de «la complexité d'un algorithme» mais c'est un peu un abus de langage qui n'est clair que dans un contexte. Il faut d'abord définir de quelle complexité on parle : spatiale ou temporelle, en quoi on va mesurer la complexité : en actions élémentaires, en nombre d'échange d'éléments dans un tableau, … et de quoi on mesure la complexité : un tableau de taille N, un entier de k bits, un graphe avec V sommets et E arrêtes,…

En général quand c'est balancé de but en blanc avec des fonctions à la C++, complexité signifie «complexité temporelle en actions élémentaires en fonction du paramètre d'entrée de la fonction».

Code :

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

1
2
3
4
5
6
7
8
9
 
void f(int [] t){
    for(int i=0; i < t.length; i++){
        t[i]=t[i]+1;
    }
    for(int i=0; i < t.length; i++){
        t[i]=t[i]*2;
    }
}

Ici f est une séquence de 2 boucles. La première effectue autant de tours de boucles qu'il y a d'éléments dans le tableau, idem pour la seconde. Le corps de la première, tout comme celle de la deuxième, ne contient que des actions élémentaires, celles que l'on considère en O(1).
f a une complexité en O(N) pour une entrée étant un tableau de N éléments.
La complexité temporelle revient réellement à compter, ou plutôt à estimer, le nombre de fois qu'une chose est faite.

[antares56]

Pourquoi ce n'est pas en O(N²) sachant qu'il y a 2 for?

[WhiteCrow]

Parce que les boucles sont en séquence : la première effectue N additions puis ensuite la seconde N multiplications, il y a 2N opérations élémentaires → complexité temporelle en O(N).

Une complexité temporelle en N² correspond souvent (à ce niveau) à une boucle dans une boucle comme par exemple :

Code :

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

1
2
3
4
5
6
7
8
 
int sum=0;
for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
        sum += 1;
    }
    sum -= i;
}

Dans ce cas la deuxième boucle est exécutée à chaque tour de la première boucle.
Dans le monde réel, le tri par sélection est un algo en complexité temporelle quadratique.

[antares56]

Ah d'accord je vois, et du coup la deuxième et la troisième sont en O(N)?

[WhiteCrow]

la troisième oui …
la deuxième … non ; en plus elle est piégeuse …
pour la deuxième poses-toi ces questions :
combien de tours de boucle while sont effectués ?
combien de tours de boucle while sont effectués en fonction de l'entrée i ?

[antares56]

Il y a autant de tour de boucle que de fois ou le boolean est égal à "false" ?

[WhiteCrow]

Oui … et cela fait combien de tours ?

[antares56]

100 fois?

[WhiteCrow]

Non, fais une trace à la main …
au début j vaut 1 et trouvé false
premier tour :
comme trouve vaut false on rentre dans le while
j est inférieur à 100 on passe la conditionnelle
on multiplie j par 2, j vaut maintenant 2
on boucle

deuxième tour: …

[antares56]

Ok donc du coup c'est en O(N²)?

[WhiteCrow]

Non.
Comme je te le dis, fais une trace à la main.

[antares56]

Déjà merci de prendre votre temps.
J'ai fait mais justement c'est la méthode calcul que je ne comprends pas, on fait j*2 tant que j est inférieur à 100, donc 1*2,2*2,4*2 etc...

[WhiteCrow]

Deviens la machine et exécute à chaque pas la ligne de code ... c'est ça faire une trace.

j vaut 1, trouve false
tour 1 →à la fin du tour, j vaut 2, trouve false
tour 2 →à la fin du tour, j vaut 4, trouve false
tour 3 →à la fin du tour, j vaut 8, trouve false
tour 4 →à la fin du tour, j vaut 16, trouve false
tour 5 →à la fin du tour, j vaut 32, trouve false
tour 6 →à la fin du tour, j vaut 64, trouve false
tour 7 →à la fin du tour, j vaut 128, trouve false
tour 8 →à la fin du tour, j vaut 256, trouve true

On fait donc 8 fois le tour de boucle.

Maintenant est-ce que cette valeur dépend de i ?

[antares56]

Mais elle ne dépend jamais de i non? Puisque à aucun moment on a besoin de "i" dans le programme

[WhiteCrow]

Donc quelle que soit la valeur de i il y aura toujours le même nombre d'instructions élémentaires d'exécutées … tu peux donc en déduire que …

[Flodelarab]

Bonjour

J'ajoute qu'avec une telle situation, certains compilateurs, pour un langage compilé évidemment, mettent directement la valeur en mémoire. Et la boucle n'existe réellement que dans la tête programmeur, car la boucle a disparu dans le binaire exécutable.

[antares56]

C'est en O(1)?

[WhiteCrow]

oui.

[antares56]

oui.

Ok donc si j'ai compris la méthode:
pour celle là

Code :

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

1
2
3
4
5
 
int f(int [] t){
int j=t.length * t.length;
return j;
}

C'est du O(1) (car opération élémentaire)
pour celle là

Code :

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

1
2
3
4
5
6
7
8
9
 
void f(int [] t){
int i=t.length-1;
while(i<t.length && i>0){
if (t[i]>=0 && t[i]<t.length){
i=t[i];
} else { i=0; }
}
}

C'est du O(N)

Code :

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

1
2
3
4
5
6
7
8
9
 
void f(int [] t){
int m= t.length;
int res= 0;
while (m>0){
m=m/2;
res=res+1;
}
}

Et celle là du O(1) aussi ?