Discussion :

[drakes00]

Bonjour,

Dans le cadre de mes études, j'ai à rendre un devoir de complexité et j'avoue que ce n'est pas mon fort. J'ai fait la plus part des exercices (à la rigueur des pistes pour certains) et j'aimerais avoir des avis sur mes réponses.

Le premier exercice demande de donner la compléxité de morceaux de code. Tout d'abord, l'énoncé (en anglais) parle de "computational complexity", est-la notation "grand O" ou bien un calcul plus "exact" du nombre d'opérations effectuées ?

Algorithme 1

Code :

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

1
2
3
4
5
6
7
8
for (int i=n ; i>0 ; i/=2) { Pour moi, log(n) passages
   for (int j=1 ; j<n ; j*=2) { Pour moi, log(n-1) passages
      for (int k=0 ; k<n ; k+=2) { Pour moi, n/2 passages
         // Constant number of operations
      }
   }
}

Ici j'ai répondu O(n.log²(n)).

Algorithme 2

Code :

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

1
2
3
4
5
6
7
8
for (int i=1 ; i<n ; i++) { Pour moi, n passages
   for (int j=i ; j<n ; j++) { Pour moi, (n-i) passages, au maximum n-1 passages
      for (int k=0 ; k<j ; k++) { Pour moi, j passages, au maximum n passages
         // Constant number of operations
      }
   }
}

Ici j'ai répondu O(n^3).

Algorithme 3

Code :

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

1
2
3
4
5
6
7
8
for (int i=n ; i>0 ; i--) { Pour moi, n passages
   for (int j=1 ; j<n ; j*=2) { Pour moi, log(n-1) passages
      for (int k=0 ; k<j ; k++) { Pour moi, j passages, au maximum log(n-1) passages
         // Constant number of operations
      }
   }
}

Ici j'ai répondu O(n.log²(n)).


L'exercice 2 est le suivant :

Vous vous trouvez au pied d'un très long mur (comme la grande muraille de chine), vous savez qu'il y a une porte à n kilomètres mais vous ne savez pas si elle est à gauche ou à droite. Montrez qu'il est possible de trouver la porte en marchant au pire Grand Theta(n) kilomètres.

Je n'ai pas véritablement de réponse à celui-ci.
Mon idée d'algorithme serait de marche une certaine distance (laquelle) sur la gauche puis si l'on ne trouve pas la porte, revenir au point de départ et marcher le double à droite, puis le double à gauche, ...

Mais je ne vois vraiment pas comment cela peut se rapprocher des Grand Theta(n) kilomètres.

Merci ^^

[joss63]

Je suis pas d'accord sur la troisième complexité.
Pour moi, ça serait plus n²log(n).

Code :

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

1
2
3
4
5
6
7
for (int i=n ; i>0 ; i--) { Pour moi, n passages
   for (int j=1 ; j<n ; j*=2) { Pour moi, log(n-1) passages
      for (int k=0 ; k<j ; k++) { Pour moi, j passages, au maximum log(n-1) passages
         // Constant number of operations
      }
   }
}

Dans ta boucle la plus interne, la complexité est log(n). Quand j augmente de 1, et que tu passes de j à 2*j, tu fais aussi 2 fois plus d'opérations à l'intérieur et pas seulement une de plus..

[drakes00]

Ah oui effectivement, d'autant que dans la boucle la plus interne, la valeurs maximale de j est bien n.

Merci :-)