L'énoncé
Répondre aux questions suivantes.
Tu as obtenu le score de
Question 1
L = [3, 5, 2, 9]def min(L): min = 0 for i in L : if i < min: min = i return min
Que retourne min(L) ?
Un message d'erreur
0
2
Essayer de faire l'algorithme à la main pas à pas.
Question 2
La complexité linéaire est la meilleure complexité possible.
Vrai
Faux
Il existe des complexités logarithmiques. Or la fonction logarithme est inférieure à la fonction $x\mapsto x$, donc cette complexité est plus faible. C'est le cas par exemple de l'algorithme de recherche par dichotomie.
Penser à l'exponentielle ...
ou au logarithme.
Question 3
L = [5 for i in range(50)]
def max(L): max = L[0]: for i in L: if i >= max: max = i return max
Combien d'affectations sont effectuées pour la variable max si on demande à l'ordinateur max(L)?
1
50
51
La liste contient 50 éléments tous égaux à 5. On initialise la variable max à 5. Puis dans la boucle, de nombre d'itérations égal à 50, on affecte une valeur à la variable max si la valeur courante est supérieure ou égale à la variable max. Or, toutes les valeurs sont égales, donc il y a une affectation par passage dans la boucle, donc 50 affectations.
Au total, il y a 51 affectations.
Quelle est la taille de la liste L?
Question 4
On définit la fonction suivante :def produit(L): produit = L[0] for i in L: produit = produit * i return produit
Si L = [2, 4, 6], que retourne produit(L) ?
0
48
96
On remarque qu'on initialise la variable produit à partir de la première valeur de la liste.
Puis on réutilise cette première valeur dans la boucle, on multiplie donc deux fois par deux le produit final.
Faire le programme à la main
Question 5
On définit la fonction suivante :def produit(L): produit = 1 for i in L: produit = produit * i return produit
Quelle est la complexité de cet algorithme ?
$\mathcal{O}(2n + 1)$
$\mathcal{O}(n)$
La complexité se calcule de la même manière que la fonction som de la vidéo de cours.
Il y a une affectation hors de la boucle puis 1 affectation à chaque passage dans la boucle. La boucle parcourant une liste de taille $n$, il y a donc $n$ nouvelles affections, soit un total de $n + 1$.
En terme d'opération, il y en a une par passage dans la boucle, soit $n$ opérations.
On a donc une complexité de $2n + 1$, que l'on note $\mathcal{O}(n)$. On retiendra qu'il s'agit d'une complexité linéaire.
$\mathcal{O}(2n)$
On pourra se servir de la vidéo de cours.
Le minimum est ici initialisé à 0. Aucun élément étant plus petit que 0, la valeur retournée est donc 0. Il est donc important de bien initialiser au premier élément de la liste !