20 Exos Complexité
Exercice 1 - Classes de complexité⚓︎
Voici quelques complexités d’algorithme, cherchons les complexités de référence qui sont du même ordre de grandeur.
- \(n^3+5n^2+2=\mathcal{O}(. . .)\) c'est une compléxité . . . . . . . . . . . . . . . .
- \(\frac13n^4+7n^3+2n=\mathcal{O}(. . .)\)
- \(2+3n\log(n)= \mathcal{O}(. . .)\)
- \(n\log(n)+2^n+7n^3=\mathcal{O}(. . .)\)
- \(n!+8^n+9n^2=\mathcal{O}(. . .)\)
Exercice 2 - Fonction mystère⚓︎
Un élève un peu anxieux a réalisé le code suivant.
def mystere(L):
nombre = L[0]
n = len(L)
for i in range(n):
if nombre < L[i]:
nombre = L[i]
# Deuxième verif au cas où
for j in range(i):
if nombre < L[j]:
nombre = L[j]
return nombre
print(mystere([1,2,-8,14,17,10,0]))
- Que fait cette fonction ?
- Quel est le temps d’exécution au pire des cas ? Quelle est la classe de complexité de cet algorithme ?
Exercice 3 - Parcours séquentiel d’une liste⚓︎
On écrit une fonction est_element qui prend en paramètres un objet a et une liste L et retourne un booléen traduisant la véracité de l’affirmation « l’objet a est un élément de la liste L ».
def est_element(a, L):
for elt in L:
if elt == a:
return True
return False
Quelle est la classe de complexité de cet algorithme ?
Exercice 4 - Calcul de moyenne⚓︎
On écrit un programme en Python calculant la moyenne d’une liste de flottants.
def moyenne(liste):
if not(liste):
return None
somme = 0
for val in liste:
somme += val
return somme / len(liste)
Quelle est la classe de complexité de cet algorithme ?
Exercice 5 - Recherche d’un extremum⚓︎
On écrit un programme en Python recherchant le plus grand élément d’une liste de flottants.
def recherche_max(liste):
if not(liste):
return None
val = liste[0]
for elt in liste:
if elt > val:
val = elt
return val
Quelle est la classe de complexité de cet algorithme ?
Exercice 6 - Recherche par dichotomie⚓︎
On écrit en Python le programme de recherche par dichotomie.
def recherche_dichotomique(liste, element):
"""
liste doit être triée dans l'ordre croissant
Renvoie True si l'élément est dans la liste, False sinon
"""
indice_debut = 0
indice_fin = lent(liste) - 1
while indice_debut <= indice_fin:
indice_centre = (indice_debut + indice_fin) // 2
valeur_centrale = liste(indice_centre)
if valeur_centrale == element: # element est trouvé !
return indice_centrale
elif valeur_centrale < element:# on cherche dans la seconde moitié
indice_debut = indice_centre + 1
else:# on cherche dans la première moitié
indice_fin = indice_centre - 1
return -1
Quel est le temps d’exécution au pire des cas ? Quelle est la classe de complexité de cet algorithme ?