Feuille 3 : complexité

23. Feuille 3 : complexité#

Le symbole \(\blacksquare\) indique les exercices ou questions obligatoires. Commencez pas ceux-là.
Les symboles \(\star\) et \(\star \star\) indiquent les exercices ou questions de difficulté relative plus importante.

Focus

complexité : analyses et approches expérimentales

Compétences

Avoir les idées claires

Connaitre le principes de l’analyse de la complexité en temps : modèle de calcul, mesure et paramètre de la complexité, meilleur et pire cas
Savoir exprimer et exploiter une complexité asymptotique : principales complexités, interprétation pratique de ces complexités
(\(\star\)) Savoir établir la complexité d’algorithmes itératifs simples ou récursifs terminaux (algorithmes étudiés en cours)

Savoir-faire

Connaitre des exemples significatifs d’algorithmes de complexité polynomiale et logarithmique (complexité, pires et meilleurs cas)
Savoir identifier (sans nécessairement le prouver) la complexité, les meilleur-pire cas d’un algorithme

23.1. Objectif 10#

23.1.1. \(\blacksquare\) QCM (Extrait de CC)#

Dans les questions de cet exercice, le terme ‘’complexité’’ (seul) désigne la complexité en temps.
Dans les questions de cet exercice, le terme “complexité” (seul) désigne la complexité en temps. On précise “complexité en espace” si on s’intéresse à cette notion.

Une analyse de complexité en temps mesure le temps d’exécution d’un programme sur les ordinateurs des salles info. (Vrai/Faux)

Faux
Dans une analyse de complexité en temps, le coût d’une multiplication de 2 entiers codés sur 32 bits est de 1 unité tandis que celui de la multiplication de 2 nombres flottants codés sur 64 bits est de 2 unités. (Vrai/Faux)

Faux
Lors d’une analyse de complexité en temps, le coût d’une répétition while est égal à trois fois celui du for à cause du compteur géré de manière explicite : incrémentation et comparaison. (Vrai/Faux)

Faux
Citer un exemple d’algorithme avec une complexité constante dans le meilleur cas et linéaire dans le pire cas.

Recherche séquentielle
Citer un exemple d’algorithme avec une complexité quadratique dans le pire cas.

Produit matrice-vecteur, tri naïf
Quel est le meilleur cas dans une recherche dichotomique dans \(n\) valeurs triées ?

chercher t[n//2]
Un algorithme a une complexité temporelle cubique en la taille de son entrée, que peut-on dire de son temps d’exécution si l’on double la taille de l’entrée ?

x8
La fonction de complexité \(C(n) = 4n^3 + 25n^2 + 10^2\) est asymptotiquement linéaire? quadratique ? ou cubique ? Pourquoi?

Cubique, équivalence d’un polynôme à son terme de plus haut degré
Les complexités asymptotiques des programmes \(P1\) et \(P2\) sont égales à \(\theta(n)\) donc leurs fonctions de complexité \(C_1(n)\) et \(C_2(n)\) sont égales. (Vrai/Faux)

faux ( égal à des constantes multiplicatives près)
Un algorithme a une complexité en espace quadratique en son paramètre \(n\). Pour \(n = 100\), il requiert 1Mo d’espace mémoire pour pouvoir s’exécuter. De quelle quantité de mémoire aura-t-il approximativement besoin pour s’exécuter avec \(n = 1000\) ?

100 Mo (approximativement permet de s’affranchir de l’effet de l’augmentation de la taille de l’espace pour les données et le résultat qui est d’un facteur 10 par rapport au facteur 100 de l’algorithme)

23.1.2. \(\blacksquare\) Exercice#

Dérouler l’algorithme suivant en explicitant les valeurs de l’ensemble de ses variables.
```
1for i in range (4): 
2    for j in range(i,4): 
3        k = i + j
```
i

j

#add

0

[0..4[

4

1

[1..4[

3

2

[2..4[

2

3

[3..4[

1
Même question en remplaçant la ligne 2 par :
```
 for j in range(i+1,4):
```
i

j

#add

1

[1..4[

3

2

[2..4[

2

3

[3..4[

1
Compter le nombre d’additions dans chacun des deux cas.

4 + 3 + 2 + 1 = 10 additions
3 + 2 + 1 = 6 additions

Coder une vérification de ces deux questions.

On ajoute un compteur c dans la boucle la plus interne :

```{code-block} python
---
linenos: true
---
c = 0
for i in range (4): 
    for j in range(i,4): 
        k = i + j
        c = c + 1
```

23.1.3. \(\blacksquare \) Exercice#

On reprend l’exercice précédent en introduisant un nombre arbitraire \(n\) d’itérations de chaque boucle.

Quelle est une mesure naturelle de la complexité de cet algorithme ? Quel est le paramètre de cette complexité ?

mesure de complexité : le nombre d’additions
paramètre de complexité : n

Pour chacun des cas suivants : compter le nombre d’additions effectuées à chaque itération de la boucle intérieure. En déduire le nombre total d’additions. Quelle est la complexité asymptotique de cet algorithme ?

a. On modifie la ligne 1 :
```
1for i in range(n): 
2	for j in range(i,4):
```
- C(n) = 10
- complexité constante
- Si n est multiplié par 10, le nbre d’additions n’est pas modifié
b. on modifie maintenant la ligne 2 :
```
1for i in range(4): 
2	for j in range(n):
```

4 répétitions (boucle en i) de n additions (boucle en j)
C(n) = 4n
complexité linéaire
Si n est multiplié par 10, le nbre d’additions est multiplié par 10

c.  ou aussi :

```{code-block} python
---
linenos: true
---
for i in range(4): 
	for j in range(i,n):
```

::: sverbat

répétitions (boucle en i) de n, puis n-1, puis n-2 puis n-3 additions (boucle en j)
C(n) = 4n -10
complexité linéaire
Si n est multiplié par 10, le nbre d’additions est (asymptotiquement) multiplié par 10
d. Avec les lignes 1 et 2 suivantes :
```
1for i in range(n): 
2	for j in range(n):
```
n répétitions (boucle en i) de n additions (boucle en j)
C(n) = n x n = n^2
complexité quadratique
Si n est multiplié par 10, le nbre d’additions est (asymptotiquement) multiplié par 100
e. ou aussi les lignes 1 et 2 suivantes :
```
1for i in range(n): 
2	for j in range(i,n):
```
répétition en i :
- i = 0 -> n additions (boucle en j)
- i = 1 -> n-1 additions (boucle en j)
- i = 1 -> n-2 additions (boucle en j)
- …
- i = n-2 -> 2 additions
- i = n-1 -> 1 addition
Donc C(n) = n + (n-1) + (n-1) + … + 2 + 1 = n(n+1)/2
C(n) quadratique
Si n est multiplié par 10, le nbre d’additions est (asymptotiquement) multiplié par 100

23.1.4. \(\blacksquare \) Exercice#

On rappelle la spécification des fonctions est_egal() et nb_communs() d’abord sur des tableaux de dimension 1 (vecteurs) (cf. feuille 2).

La fonction est_egal() compare deux tableaux de dimension 1 et retourne le booléen correspondant. On convient que deux tableaux sont égaux si leurs tailles sont égales et si leurs valeurs sont égales deux à deux.
La fonction nb_communs() retourne le nombre de valeurs communes entre deux tableaux de dimension 1. Ici aussi la comparaison s’effectue “deux à deux” (valeurs de même indice).

Effectuer l’analyse de la complexité de ces fonctions.

param de complexité : n la taille du tableau
mesure de complexité : le nombre de comparaisons
est_egal :
- C(n) = n dans le pire cas (deux tableaux identiques ou qui diffèrent par leur dernière valeur),
- complexité linéaire du pire cas
- meilleur cas : une comparaison
nb_communs()
- C(n) = n, pire cas = meilleur cas : on doit comparer deux à deux les n valeurs de chaque tableau
- complexité linéaire

Ces fonctions s’étendent à des tableaux 2D ou de façon plus générale à des tableaux multi-dimensionnels. L’égalité entre tableaux multi-dimensionnels suppose l’égalité des dimensions, des tailles deux à deux dans chaque dimension, et des valeurs deux à deux pour toutes les valeurs du tableau. Effectuer l’analyse de la complexité de ces fonctions pour des tableaux 2D.

Pour des tableaux 2D, le paramètre de complexité reste n le nombre de lignes et le nombre de colonnes
On mesure toujours le nombre de comparaisons
L’analyse est similaire à celle des tableau 1D en remplaçant n par n x n.

23.1.5. Exercice (palindrome … toujours) extrait d’examen#

Cet exercice reprend l’exercice sur les palindromes des feuilles 1 et 2.

Effectuer l’analyse de complexité en temps de la version itérative de la vérification qu’un mot est ou non un palindrome (feuille 1).

Veillez bien à répondre aux points suivants : para-mètre et mesure de la complexité, meilleur cas et pire cas, expression de cette complexité, comportement asymptotique, effet sur temps de traitement si le paramètre de complexité est doublé.

mesure de la complexité : nbre de comparaisons
param. de complexité : n = longueur du mot
meilleur cas : dépend de l’algorithme, première comparaison : échec -> non palindrome C(n) = 1, constante
pire cas : dépend de l’algorithme, on effectue n//2 comparaisons pour conclure que c’est un palindrome ou non (dernière comparaison) : C(n) = n//2, complexité linéaire
si est n est doublé, on double le nbre de comparaisons dans le pire cas.

Même question pour la version récursive vue dans la feuille 2.

mesure de la complexité : nbre de comparaisons
param. de complexité : n = longueur du mot
on effectue 1 comp par appel récursif
chaque appel récursif réduit la longueur du mot de 2 caractères : n, n-2, n-4 …, 2 ou 1
- Donc C(n) = 1 + C(n-2)
l’arrêt de la récursion est qd g >= d, cad un mot de longueur 0
- Donc C(0) = 1
Par simplification, on trouve : C(n) = 1 + 1 + … + 1 = n/2
Complexité linéaire et identique (*) à celle de la version itérative

(*) Rmq. En toute rigueur, C(n) = n//2 + 1. Ce décompte dépend de la parité de n. Le “+1” vient de la condition d’arrêt (mot de longueur 0). On aurait pu terminer la récursion avec un appel de moins dès que le mot est de longueur 2 (comparaison de deux caractères) ou de longueur 1 (pas de comparaison nécessaire).

23.1.6. Exercice (extrait d’examen)#

On s’intéresse à la complexité en temps de la fonction suivante.

    def mystere(n: int) -> int:
       m = 0
       for i in range(n):
          for j in range(i):
             m = m + i + j
       return m 

Quel est le paramètre de cette complexité ?
- n
Quelles sont les instructions significatives de cette complexité ?
- l’affectation du corps de boucle (mieux) et les 2 add du membre de droite (moins bien)
Quelle est une mesure de sa complexité ?
- le nombre d’affectations (mieux que le nbre d’op. arithm)
Donner l’expression de cette complexité.
- c(n) = n(n-1)/2
Combien y a-t-il d’opérations arithmétiques dans l’exécution de cette fonction pour un paramètre effectif \(N\) donné. ?
- 2 fois plus que d’affectations : N(N-1)
Expliciter sa complexité asymptotique avec les notations de Landau.
- quadratique, ie \(\Theta(n\^2)\)

i	j	#add
0	[0..4[	4
1	[1..4[	3
2	[2..4[	2
3	[3..4[	1

i	j	#add
1	[1..4[	3
2	[2..4[	2
3	[3..4[	1