Exercices corrigés sur la complexité en temps

Les exercices corrigés suivants concernent l’analyse d’algorithmes, en particulier l’exactitude, l’exhaustivité et le calcul de la complexité en temps.

calcul de la complexité en temps

Exercice 1

Déterminez la complexité temporelle de l’algorithme Check :

corrected exercises algorithm analysis correctness completeness time complexity

Solution

Vérifiez l’exactitude et l’exhaustivité, en particulier ce qui s’est passé lors de la première itération.

Exercice 2

Analyser la complexité de l’algorithme. Écrivez un autre algorithme qui fait exactement la même chose qu’Algorithm mais avec une complexité en temps asymptotique strictement meilleure.

corrected exercises algorithm analysis correctness completeness time complexity

Solution

La complexité est O(|A|²). Vous pouvez améliorer l’algorithme en : triant d’abord la table en O(n log n) puis en vérifiant les occurrences en O(n), ainsi la complexité devient O(n log n).

Exercice 3

Quel est le temps d’exécution (asymptotique) de chacun des algorithmes suivants, en fonction de n ? Justifiez vos réponses.

a)

for i = 1 to n do
   for j = 1 to 2n + 1 do
      print (« Hello World)
   end for
end for

b)

for i = 1 to 10 do
   for j = 1 to n do
      print (« Hello World »)
   end for
end for

c)

for i = 1 to n do
   for j = i to n do
      print (« Hello World »)
   end for
end for

d)

for i = 1 to n do
   for j = 1 to 2 ∗ i + 1 do
      print (« Hello World »)
   end for
end for

e)

for i = 1 to n ∗ n do
   for j = 1 to i do
      print (« Hello World »)
   end for
end for

f)

for (i = 0 to m) do
   t ← 1
   while (t < m) do
      print (« Hello world »)
         t ← t ∗ 2
   end while
end for

Solution

  • a) O(n²)
  • b) O(n)
  • c) O(n²)
  • d) O(n²)
  • e) O(n4)
  • f) O(m log(m))

Exercise 4

Soient TA(n), TB(n) et TC(n) les temps d’execution des algorithmes A, B et C, respectivement.

Instruction A
if (n < 100) then
    Instruction B
else
    for (j = 1 to n) do
        Instruction C
    end for
end if

Quelle est la durée d’exécution de cet algorithme, sous chacun des ensembles d’hypothèses suivants ? Justifiez vos réponses.

  1. TA(n) = O(n), TB(n) = O(n2) et TC(n) = O(log n).
  2. TA(n) = O(n2), TB(n) = O(n2) et TC(n) = O(log n).
  3. TA(n) = O(n2), TB(n) = O(n3) et TC(n) = O(log n).

Solution

Étant donné que les grandes valeurs de n déterminent le temps d’exécution asymptotique, nous pouvons négliger la partie if de l’instruction if. Par conséquent, dans tous les cas, le temps d’exécution de cet algorithme est O(TA(n) + nTC(n)).

  1. a) O(n log n)
  2. b) O(n²)
  3. c) O(n²)

Exercice 5

Quelle est la complexité, dans le pire des cas, de chacun des fragments de code suivants ?

Deux boucles d’affilée :

  1. for (i = 0; i < N; i++) {
  2. sequence of statements}
  3. for (j = 0; j < M; j++) {
  4. sequence of statements}

Comment la complexité changerait-elle si la deuxième boucle passait à N au lieu de M ?

Une boucle imbriquée suivie d’une boucle non imbriquée :

  1. for (i = 0; i < N; i++) {
  2. for (j = 0; j < N; j++) {
  3. sequence of statements
  4. }}
  5. for (k = 0; k < N; k++) {
  6. sequence of statements}

Une boucle imbriquée dans laquelle le nombre d’exécutions de la boucle interne dépend de la valeur de l’index de la boucle externe :

  1. for (i = 0; i < N; i++) {
  2. for (j = N; j > i; j–) {
  3. sequence of statements
  4. }}

Solution

  1. La première boucle est O(N) et la deuxième boucle est O(M). Puisque vous ne savez pas lequel est le plus grand, vous dites que c’est O(N+M). Cela peut aussi s’écrire O(max(N,M)). Dans le cas où la seconde boucle va vers N au lieu de M la complexité est O(N). Vous pouvez le voir à partir de l’une ou l’autre des expressions ci-dessus. O(N+M) devient O(2N) et lorsque vous supprimez la constante, c’est O(N). O(max(N,M)) devient O(max(N,N)) qui est O(N).
  2. Le premier ensemble de boucles imbriquées est O(N²) et la deuxième boucle est O(N). C’est O(max(N²,N)) qui est O(N²).
  3. Ceci est très similaire à notre exemple précédent d’une boucle imbriquée où le nombre d’itérations de la boucle interne dépend de la valeur de l’index de la boucle externe. La seule différence est que dans cet exemple, l’indice de boucle interne compte à rebours de N à i+1. C’est toujours le cas que la boucle interne s’exécute N fois, puis N-1, puis N-2, etc., donc le nombre total de fois que la « séquence d’instructions » la plus interne s’exécute est O(N²).

Exercice 6

Donnez une analyse du temps d’exécution (notation Big-Oh) pour chacun des 4 fragments de programme suivants. Notez que le temps d’exécution correspond ici au nombre de fois que l’opération sum++ est exécutée. sqrt est la fonction qui renvoie la racine carrée d’un nombre donné.

corrected exercises algorithm analysis correctness completeness time complexity

  1. S’il faut 10 ms pour exécuter le programme (b) pour n=100, combien de temps faudra-t-il pour exécuter n=400 ?
  2. S’il faut 10 ms pour exécuter le programme (a) pour n=100, quelle taille de problème peut être résolu en 40 ms ?

Solution

A et b dans O(sqrt(n)), c et d dans O(n^5)

Avec produit croisé : sqrt(100)=x et y=10 ms ; sqrt(400)=2x prend 20ms

En 40ms, n=1600.

Partager
fr_FRFR
%d blogueurs aiment cette page :