1.Écrire T(n)=O(n2) signifie que l’algorithme effectue exactement n2 opérations élémentaires.
2.Si la complexité dans le meilleur des cas d’un algorithme est O(n), sa complexité dans le pire des cas est nécessairement, elle aussi, en O(n).
3.Deux boucles imbriquées, chacune parcourant les n éléments d’un tableau, donnent en général lieu à une complexité en O(n2).
4.La base du logarithme utilisée dans O(logn) n’a pas d’incidence sur la classe de complexité.
5.La complexité spatiale d’un algorithme est toujours égale à sa complexité temporelle.
On considère la fonction suivante, qui compte le nombre d’éléments pairs d’une liste de n entiers :
def compte_pairs(t):
c = 0
for x in t:
if x % 2 == 0:
c = c + 1
return c
En reprenant la convention de l’exemple du cours (une opération élémentaire par affectation, comparaison ou test), donner le nombre exact d’opérations effectuées par compte_pairs dans le pire des cas (préciser quelle entrée réalise ce pire cas).
Le pire cas est atteint lorsque tous les éléments de t sont pairs : à chaque itération, le test x % 2 == 0 (une opération) est vrai, donc l’affectation c = c + 1 s’exécute également (une addition et une affectation, soit deux opérations). Chaque itération coûte donc 1+2=3 opérations dans ce cas.
En comptant l’initialisation c = 0 (une opération), les n itérations (chacune à 3 opérations dans le pire cas), et le renvoi de c (une opération), le nombre total d’opérations est : Tmax(n)=1+3n+1=3n+2
En déduire la classe de complexité de compte_pairs dans le pire des cas.
3n+2=O(n) (une constante et un terme linéaire sont chacun des O(n), donc leur somme aussi, d’après la règle de somme du cours) : compte_pairs est de complexité linéaire.
On considère la fonction suivante :
def produit_scalaire_toutes_paires(t):
n = len(t)
s = 0
for i in range(n):
for j in range(n):
s = s + t[i] * t[j]
return s
Combien de fois le corps de la boucle interne (s = s + t[i] * t[j]) est-il exécuté, en fonction de n ?
La boucle externe s’exécute n fois (une fois par valeur de i de 0 à n−1), et pour chacune de ces valeurs, la boucle interne s’exécute également n fois (une fois par valeur de j) — le nombre de répétitions de la boucle interne ne dépend pas de i. Le corps de la boucle interne est donc exécuté n×n=n2 fois au total, conformément à la règle du cours : « pour des boucles imbriquées, multiplier les coûts ».
Donner le nombre exact d’opérations élémentaires effectuées par produit_scalaire_toutes_paires, en détaillant le compte à chaque exécution du corps de la boucle interne.
Chaque exécution du corps s = s + t[i] * t[j] comporte : un accès t[i] (une opération), un accès t[j] (une opération), une multiplication (une opération), une addition (une opération), une affectation à s (une opération) — soit 5 opérations par exécution. Comme le corps s’exécute n2 fois (question a.), et en ajoutant l’initialisation (n = len(t) et s = 0, soit 2 opérations) et le renvoi de s (une opération), le nombre total d’opérations est : T(n)=5n2+3
En déduire la complexité de cette fonction.
5n2+3=O(n2) (d’après la règle d’absorption des termes dominés, ou directement : 5n2+3⩽8n2 dès que n⩾1) : produit_scalaire_toutes_paires est de complexité quadratique.
6 blocs de plus : les autres énoncés et tous les corrigés, rédigés en entier. Le reste du programme est écrit de la même main, avec les figures interactives et votre progression.