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 ?