td06 Complexite

Lycée Carnot — 2019-2020 Informatique MPSI
TD no 6 : Complexité des algorithmes
E XERCICE 1 Notation de Landau

Simplifier les écritures suivantes :
2 42 n−1
1. Θ(n + 1) 4. O(n e + 3 × 2 )
2
2. O(3n + 3) 5. O(log2 (n + 1) + ln(2n ))
n(n+1)
3. Θ( 2
) 6. Θ(max(n, m))
E XERCICE 2 Vrai ou faux ?

2
1. Une complexité en Θ(n) est toujours mieux qu’une complexité en Θ(n ).
2. Une boucle for a une complexité en Θ(n).
3. La copie d’une liste de taille n prend un temps Θ(n).
4. Un Θ(n) est toujours un O(n).
5. On peut considérer que la méthode .append() pour les listes s’exécute en Θ(1).
6. La taille d’un entier n est l’entier n lui-même.
E XERCICE 3 Calculer le nombre d’opérations élémentaires des fonctions suivantes. Que choisir
comme taille de l’entrée ? Justifier. Donner enfin la complexité asymptotique, avec les notations
de Landau.
P YTHON P YTHON
def machin(n): def bidule(n):
for i in range(n): for i in range(n):
print(i) for j in range(i + 1, n):
for j in range(n): print(i, j)
print(j)
P YTHON P YTHON
def truc(n): def chose(n):
for i in range(n): for i in range(2, n - 2):
for j in range(n): for j in range(i - 2, i + 3):
print(i, j) print(i, j)
E XERCICE 4 Complexité des opérations usuelles

Pour les complexités, on donnera un ordre de grandeur, avec les notations de Landau, et non
pas un décompte précis des opérations élémentaires.
1. Écrire une fonction egal qui vérifie si deux listes sont égales, sans utiliser directement l’éga-
lité sur les listes. Donner sa complexité dans le meilleur et dans le pire cas, en temps et en
espace. Que penser de la complexité de L1 == L2 si L1 et L2 sont deux listes ?
2. Écrire une fonction mininmum qui renvoie le plus petit élément d’une liste non vide. Donner
sa complexité dans le meilleur et dans le pire cas, en temps et en espace. Que penser de la
complexité de min(L) si L est une liste ?
http://cpge.info 1
3. On suppose que L1 et L2 sont des listes de tailles respectives n1 et n2 . Pour chaque opération
1
suivante, décrire succinctement l’algorithme qui pourrait être implémenté en P YTHON et
en donner la complexité.
a) L1 + L2 b) L1.extend(L2) c) L1[i:j]
E XERCICE 5 Retour sur la concaténation

Calculer la complexité des deux fonctions ci-dessous. Comparer le temps mesuré avec le temps
estimé sur un ordinateur à 100 millions d’opérations par seconde. Commenter.
P YTHON
def creation_naive(n):
L = []
for _ in range(n):
L = L + [0]
# %timeit creation_naive(10 ** 5)
# 28.8 s ± 293 ms per loop
def creation_avec_append(n):
L = []
for _ in range(n):
L.append(0)
# %timeit creation_avec_append(10 ** 5)
# 11.5 ms ± 85.7 µs per loop
E XERCICE 6 Retour sur la suite de Fibonacci

Un élève propose la fonction suivante pour déterminer si un entier k ∈ N est un entier de
Fibonacci, c’est-à-dire s’il existe n ∈ N tel que k = f n , avec ( f n )n≥0 la suite de Fibonacci de
premiers termes 0 et 1.
P YTHON
def est_fibo(k):
"""Vérifie si un entier k est un nombre de Fibonacci."""
# On a f n + 1 ≥ n pour n ≥ 0, donc si un nombre
# de fibonacci f n convient, alors 0 ≤ n ≤ k + 1
nombres_de_fibonnaci = []
for i in range(k + 2):
nombres_de_fibonnaci.append(fibo(i))
for i in range(k + 2):
if k in nombres_de_fibonnaci:
return True
return False
1. Calculer la complexité de cette fonction.

2. Commenter tout ce qu’il y a à commenter.
1. On ne demande pas d’écrire la fonction en P YTHON, mais de décrire l’algorithme en une ou deux phrases.
http://cpge.info 2
E XERCICE 7 Neufs
On considère la fonction neufs ci-dessous, qui prend en argument un entier n > 0.
P YTHON
def neufs(n):
chiffres = []
while n > 0:
chiffres.append(n % 10)
n = n // 10
res = 0
for k in range(len(chiffres)):
i = k
while i < len(chiffres) and chiffres[i] == 9:
i += 1
res = max(res, i - k)
return res
1. Donner la complexité de cette fonction en considérant comme taille de l’entrée l’entier n.

2. Que pourrait-on choisir d’autre pour la taille de l’entrée et quelle serait alors la complexité ?
3. Que fait cette fonction ? Remarquons que nous n’avions pas besoin de comprendre son fonc-
tionnement pour analyser sa complexité.
4. Modifier la fonction pour avoir une complexité en temps en O(log n).
5. Modifier la fonction précédente pour avoir une complexité en espace en O(1).
E XERCICE 8 Retour sur la recherche par dichotomie

Voici une des nombreuses implémentations possibles de la recherche par dichotomie dans un
tableau trié :
P YTHON
def recherche_dichotomique(element, tableau):
"""Vérifie si un élément appartient à
un tableau trié croissant de taille non nulle
par recherche dichotomique."""
fin = len(tableau) - 1
debut = 0
while debut < fin:
milieu = (debut + fin) // 2
if element == tableau[milieu]:
debut = fin = milieu
elif element < tableau[milieu]:
fin = milieu - 1
else:
debut = milieu + 1
return debut == fin and element == tableau[debut]
On note t le tableau, n sa taille, x l’élément et d, m, f pour debut, milieu, fin, respective-

ment.
1. Donner la complexité spatiale de cette fonction.
http://cpge.info 3
2. Donner la complexité temporelle de cette fonction dans le meilleur cas, que l’on précisera.
3. Montrer que la complexité temporelle dans le pire cas est en O(n).
Cette borne n’est cependant pas très serrée. On peut dire beaucoup mieux.
n
4. Montrer par récurrence sur k ∈ N qu’après k itérations de la boucle, f − d < .
2k
5. En déduire que la complexité dans le pire cas est en fait en O(log n).
6. Identifier un pire cas et montrer que cette borne est serrée et que la complexité dans le pire
cas est en Θ(log n).
E XERCICE 9 Retour sur les tris

Pour chacun des algorithmes de tri ci-dessous, donner précisément sa complexité, en ne consi-
dérant comme opérations élémentaires que les comparaisons entre éléments des listes. La fonction
echange, qui échange deux cases dans un tableau, a donc par exemple une complexité nulle. Jus-
tifier ensuite précisément la terminaison et la correction de ces deux algorithmes de tri.
1. Tri par sélection
P YTHON
def indice_min(tab, i):
"""Indice du premier élément minimal du tableau tab[i:].
On suppose que `i` est un indice valable."""
i_mini = i
for j in range(i + 1, len(tab)):
if tab[j] < tab[i_mini]:
i_mini = j
return i_mini
def tri_selection(tab):
"""Tri un tableau par la méthode du tri par selection."""
for i in range(len(tab)):
echange(tab, i, indice_min(tab, i))
2. Tri par insertion

P YTHON
def insere(tab, i):
"""Insère tab[i] à la bonne place dans tab[:i] supposé trié
en faisant des échanges successifs."""
k = i
while k > 0 and tab[k - 1] > tab[k]:
echange(tab, k - 1, k)
k -= 1
def tri_insertion(tab):
"""Tri un tableau par la méthode du tri par insertion."""
for i in range(len(tab)):
insere(tab, i)
http://cpge.info 4

td06 Complexite

Transféré par

Droits d'auteur :

Formats disponibles

td06 Complexite

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

td06 Complexite

Transféré par

Droits d'auteur :

Formats disponibles

Lycée Carnot — 2019-2020 Informatique MPSI

TD no 6 : Complexité des algorithmes

E XERCICE 1 Notation de Landau

E XERCICE 2 Vrai ou faux ?

E XERCICE 4 Complexité des opérations usuelles

E XERCICE 5 Retour sur la concaténation

E XERCICE 6 Retour sur la suite de Fibonacci

1. Calculer la complexité de cette fonction.

1. Donner la complexité de cette fonction en considérant comme taille de l’entrée l’entier n.

E XERCICE 8 Retour sur la recherche par dichotomie

On note t le tableau, n sa taille, x l’élément et d, m, f pour debut, milieu, fin, respective-

E XERCICE 9 Retour sur les tris

2. Tri par insertion

Vous aimerez peut-être aussi