Exercice 1
Déterminez la complexité temporelle de l’algorithme Check :
Avant de calculer la complexité, il faut vérifier si l’algorithme se termine. Les éléments de la matrice sont des entiers, donc peuvent dépasser la valeur de 9, ce qui signifie que tab[value-1] sort de la taille du tableau. L’algorithme n’est donc pas viable et inutile de continuer l’analyse plus loin.
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.
L’algorithme est vraiment compliqué à comprendre. Le plus simple est de tester son fonctionnement avec un petit vecteur comme par exemple <3, 5, 4, 4, 5, 7>. Je vous laisse tester pas à pas sur papier.
Dans la boucle, quand deux cases sont identiques, on incrémente la valeur de c. Compte tenu du contenu séquentiel dans la boucle, i reste stable tandis que j évolue. Donc on compte le nombre d’occurence dans le tableau de la valeur de la case i. Le deuxième embranchement donne une condition lorsque j atteint sort de la taille du vecteur. Dans ce cas on vérifie que le nombre d’occurence de la valeur de la case i dépasse le dernier compte enregistré dans m. Puis on incrémente i et place j sur la même case.
Cela ne change pas le fonctionnement de trouver le nombre d’occurence de chaque case car si la valeur se trouvait avant, il a déjà été compté dans sa totalité. Justement, faire commencer i et j au même endroit produit moins de calcul.
Si on reprend le fonctionnement, i et j se trouvent sur la même case. j incrémente jusqu’à la fin du tableau. Puis i avance d’une case et j se place au même endroit. Le nombre d’itération est donc la somme de n (taille du tableau) à 1, soit n(n-1)/2. Les deux embranchements ont la même complexité en 0(1), donc la complexité de l’algorithme est de O(n²).
Pour faire plus simple, il suffit de réaliser l’algorithme en deux temps. Dans un premier temps, on trie le tableau (possible en O(n log(n)).Puis on lit le tableau par deux cases tab[i] et tab[i+1]. Tant que les valeurs sont égales, on incrémente un compteur c. Si c’est différent, on regarde si c>m comme l’algorithme proposé. La complexité est donc de O(n log(n) + n), soit O(n log(n)).
Exercice 3
Remplir les deux tableaux ci-dessous :
Exercice 4
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
a) O(n²). Ici la première boucle fait (n-1) itérations et la deuxième boucle 2n itérations, donc un total de (n-1)*2n.
b) O(n). Ici la première boucle fait 10 itérations et la deuxième boucle n itérations, donc un total de 10n. Attention, selon certain calcul cela ferait 9 itérations suivi de n-1 itérations. Heureusement, dans la notation de Landau cela ne change rien donc inutile de chipoter pour le comptage d’itérations !
c) O(n²). Très classique, chaque boucle fait n-1 itérations.
d) O(n²). La première boucle est classique. La deuxième va de 1 à 2i+1, donc si on fait quelques exemples : 3, 5, 7, …, 2n+1 (ici on fait fonctionner les deux boucles en même temps). On a donc la somme des n premiers termes inpairs donc quadratique.
Il est aussi possible de calculer la complexité en multipliant la complexité de chacune des boucles. La première boucle tend vers n itérations quand n est grand; la deuxième boucle tend vers n itérations quand n est grand. Nous avons donc une complexité de O(n*n)=O(n²).
Attention à bien vérifier quand même le nombre d’itération quand n est grand, ce ne sera pas toujours en O(n) !
e) O(n^4). La réflection est la même que pour l’algorithme d. Ici, nous avons les n premiers termes au carré.
f) O(m log(m)). Pour la première boucle tout va bien, le problème va venir de la deuxième. Ici la valeur de t double à chaque itération et la boucle s’arrête quand t dépasse la valeur de m. On pose k le nombre d’itération réalisée. On s’arrête quand 2^k >m donc quand k > log(m). D’où la complexité.
Exercice 5
Soient TA(n), TB(n) et TC(n) les temps d’éxecution 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.
- TA(n) = O(n), TB(n) = O(n2) et TC(n) = O(log n).
- TA(n) = O(n2), TB(n) = O(n2) et TC(n) = O(log n).
- TA(n) = O(n2), TB(n) = O(n3) et TC(n) = O(log n).
É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)).
- O(n log n)
- O(n²)
- O(n²)
Si vous avez un doute sur vous pouvez aussi utiliser la formule classique en cas d’embranchement 0(max(T_branches)). Dans ce cas, on aurait eu O(TA(n) + max(TC(n), nTC(n)) ).
Exercice 6
Quelle est la complexité, dans le pire des cas, de chacun des fragments de code suivants ?
Deux boucles d’affilée :
- for (i = 0; i < N; i++) {
- sequence of statements}
- for (j = 0; j < M; j++) {
- 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 :
- for (i = 0; i < N; i++) {
- for (j = 0; j < N; j++) {
- sequence of statements
- }}
- for (k = 0; k < N; k++) {
- 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 :
- for (i = 0; i < N; i++) {
- for (j = N; j > i; j–) {
- sequence of statements
- }}
- 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).
- Le premier ensemble de boucles imbriquées est O(N²) et la deuxième boucle est O(N). C’est O(N²+N) qui est O(N²).
- 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 7
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é.
- 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 ?
- 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 ?
A est en O(sqrt(n)) c’est une suite séquentielle de boucles, on a 0(sqrt(n)/2 + sqrt(n)/4 + sqrt(n)/4 +8)
B ne se termine pas, la deuxième boucle n’st pas bien écrite ! En considérant la boucle écrite convenablement, on aurait eu trois boucles interdépendantes bornées en 0(sqrt(n)), 0(1) et O(1) — de i à i+8; de j à j+8 cela fait seulement 8 itérations. Ce qui vaut 0(sqrt(n)).
c est en O(n^5). Trois boucles imbriquées de complexités respectives 0(n), 0(n²), 0(n²) donc 0(n*n²*n²).
d possède une condition d’embranchement qui n’est pas valide car cela ne renvoie pas un booléen, l’algorithme ne se termine pas donc pas besoin de calculer la complexité.
Avec produit croisé : sqrt(100)=x et y=10 ms ; sqrt(400)=2x prend 20ms
En 40ms, n=1600.
FR 
EN 
ES