Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
Chapitre 1 — Complexité algorithmique
Exercices
1 Algorithme de type seuil
1.1 Calcul du n-ième terme d’une suite
(
u0 = 4
uk+1 = 2uk − 1 ∀k ∈ N
def u_n(n):
u = 4
k = 0
while k < n:
u = 2*u - 1
k = k + 1
return u
Complexité temporelle Les deux premières instructions entraînent 2 opérations. Le premier test conditionnel et
le return ajoutent 2, ainsi le coût initial vaut 4 opérations.
À chaque tour de boucle, la nouvelle valeur de u requiert 3 opérations tandis que celle de k 2 opérations, auxquelles
s’ajoutent le test conditionnel de la boucle ce qui fait 6 opérations par tour de boucle.
Ce qui donne : ∀n ∈ N, CT (n) = 4 + 6n.
u0 = −1, un+1 = 2un ∀n ∈ N
Exercice 1. On définit les suites
v0 = 5, vn+1 = un + vn ∀n ∈ N
Proposer une fonction termesUV(n) qui renvoie le couple (un , vn ). Déterminer le coût temporel en fonction de n.
1.2 Premier dépassement d’un seuil par une suite
On considère (uk ) définie par uk = 3 × 2k + 7, pour tout k ∈ N et on cherche à déterminer le premier indice où
un terme dépasse strictement un entier s.
def seuil_u(s) :
k = 0
u = 10
while not( u >= s ):
k = k + 1
u = 3 * 2**k + 7
return k
T. Lopez Page 1 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
Complexité temporelle Lorsque l’on veut connaître le nombre de tours de boucles, on doit résoudre uk < s. Ce
qui équivaut à k > log2 s−73 . Il y aura n tours de boucles avec n = log 2
s−7
3
Les deux premières instructions entraînent 2 opérations plus 3 pour le test conditionnel et le return, soit 5
opérations initiales. À chaque tour de boucle, il y a 8 opérations (7 si l’on avait écrit u < s).
Ce qui donne : ∀n ∈ N, CT (n) = 5 + 8n. Le coût est linéaire selon n (en O(n)) et logarithmique selon s (en
O(log(s))).
Exercice 2. Étant donné un entier s, on cherche à déterminer le plus petit entier n de sorte que s divise n!.
Proposer une fonction divFacto(s) et déterminer sa complexité temporelle en fonction de n.
2 Algorithme de type somme
Dans un algorithme de somme, on parcourt le tableau en entier.
2.1 Algorithme de somme
On calcule la somme des éléments d’un tableau (une liste Python).
def somme(tab):
som = 0
for i in range(len(tab)):
som = som + tab[i]
return som
Complexité temporelle En considérant la boucle while équivalent à la boucle for
i = 0
while i < len(tab):
...
i = i + 1
On note n la longueur du tableau. L’appel de la fonction nécessite 5 opérations initiales.
Chaque tour de boucle entraîne 7 opérations, ainsi le coût temporel est donné par : ∀n ∈ N, CT (n) = 5 + 7n.
Le coût est linéaire (en O(n)).
Exercice 3. Proposer une fonction diviseurs(n), qui renvoie la liste des diviseurs positifs inférieurs à n. Déterminer
un majorant du coût temporel en fonction de n.
T. Lopez Page 2 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
2.2 Algorithme du maximum
On calcule le maximum d’un tableau (supposé non vide)
def maximum(tab):
vmax = tab[0]
for i in range(len(tab)):
if vmax < tab[i]:
vmax = tab[i]
return vmax
Complexité temporelle On note n la longueur du tableau. L’appel de la fonction nécessite 6 opérations initiales.
Lors d’un tour de boucle,
— si vmax est supérieure à la nouvelle valeur, il faut 6 opérations.
— si vmax est strictement inférieure à la nouvelle valeur, il faut 8 opérations.
Dans les deux cas, on effectue len(tab) tours de boucle et le coût temporel est dans le pire des cas : ∀n ∈ N∗ , CT (n) =
6 + 8n.
Le coût est linéaire (en O(n)).
Exercice 4. Proposer une fonction nbMax(tab), qui renvoie le nombre de fois qu’apparaît le maximum dans tab.
Déterminer le coût temporel dans le pire des cas.
3 Algorithme de type recherche
3.1 Cas général
Dans un algorithme de recherche d’existence, on parcourt le tableau jusqu’à trouver la valeur recherchée.
Lors du parcours du tableau, si la valeur du tableau vaut celle recherchée :
— on renvoit True et on s’arrête.
— Sinon, on continue.
Enfin, si tout le tableau a été vérifié et que la valeur recherchée n’a pas été trouvée, on renvoie False.
Ainsi le tableau sera parcouru entièrement lorsque la valeur cherchée est en dernière position ou si elle n’existe
pas.
def recherche(val, tab):
for i in range(len(tab)):
if val == tab[i]:
return True
return False
Complexité temporelle L’appel de la fonction nécessite 4 opérations initiales. Lors d’un tour de boucle,
— si la valeur est trouvée, il faut 3 opération avant de renvoyer la valeur False et arrêter le programme.
— si la valeur n’est pas trouvée, il faut 6 opérations et le programme continue.
T. Lopez Page 3 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
Ainsi dans le meilleur des cas, la valeur est trouvée à la première vérification. Dans le pire des cas, on doit parcourir
tout le tableau, ce qui donne un coût temporel : ∀n ∈ N, CT (n) = 4 + 6n
Le coût est au pire linéaire (en O(n)).
Exercice 5. Proposer une fonction tabCroissant(tab), qui précise si les valeurs de tab sont trié dans l’ordre
croissant. Préciser le pire des cas et en déterminer le coût temporel.
3.2 Cas d’un tableau trié : la recherche dichotomique
Lorsque le tableau est déjà trié, il est possible de rechercher efficacement une valeur en divisant par deux la zone
de recherche à chaque étape.
On procède avec l’algorithme suivant :
— Tant que le tableau sélectionné n’est pas vide
— Comparer la valeur cherchée à celle du milieu.
— Si la valeur cherchée est plus petite, sélectionner le sous-tableau de gauche
— SI la valeur cherchée est plus grande, sélectionner le sous-tableau de droite
— Si la valeur cherchée est égale, on a trouvé : arrêt
def recherche_dic(tab):
btrouve = False
indg = 0
indd = len(tab) - 1
while (not btrouve) and (indd - indg >= 0):
indm = (indg + indd) // 2
if val < tab[indm]:
indd = indm - 1
elif val > tab[indm]:
indg = indm + 1
else:
btrouve = True
return btrouve
Complexité temporelle Considérons un tableau de longueur n et posons k = ⌈log2 (n)⌉ (autrement dit 2k−1 <
n ≤ 2k ).
Posons CT (n) le coût de la recherche pour un tableau de taille n. On a CT (0) = 11. Sinon, à chaque étape,
— Soit la valeur est trouvée et l’algorithme s’arrête ; 8 instructions ont alors été passées.
— Soit la valeur n’est pas trouvée et le tableau de recherche est divisé en deux après au pire 14 instructions
passées.
Ainsi dans le pire des cas, CT (n) = CT ( n2 ) + 14.
On obtient CT (n) = CT (2k ) = CT (n/2) + 14 = CT (n/4) + 2 ∗ 14 = . . .
CT (n) = CT (1) + 14 × k = CT (0) + 14 × (k + 1)
Donc CT (n) = 25 + 14k = O(k).
Le coût temporel est majoré par CT (n) ≤ 25 + 14k = 25 + 14⌈log2 (n)⌉. Le cout est au pire logarithmique selon
n, en O(log(n)).
Exercice 6. Proposer une fonction rechercheDicho(tab), qui à partir d’un tableau trié croissant renvoie un couple
(booléen, entier) qui précise si la valeur est dans le tableau et auquel cas l’indice où l’on peut trouver une occurrence
de val dans tab.
T. Lopez Page 4 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
4 Exercices
Exercice 7. truc et bidule sont deux fonctions quelconques, sans arguments. On considère les 4 scripts ci-dessous :
for i in range(n): for i in range(n): for i in range(n): for i in range(n):
truc() truc() truc() truc()
for i in range(n): for j in range(n): for j in range(i): for j in range(i):
bidule() bidule() bidule() bidule()
for k in range(j):
truc(), bidule()
Script A Script B Script C Script D
1. Déterminer le nombre de fois que chaque fonction est appelées dans chacun des scripts.
On rappelle que 1 + 2 + . . . + n = n(n+1)
2 et 12 + 22 + . . . + n2 = n(n+1)(2n+1)
6
2. En supposant que les fonctions s’exécutent en O(1), donner la complexité de ces scripts.
3. Redonner la complexité pour les scripts A et B si un truc a un complexité quadratique
Exercice 8. On considère la fonction itérative ci-contre.
def f(n):
Préciser sa complexité, en justifiant.
while n > 1:
n = n / 10
print("Fini!")
Exercice 9. Voici deux fonctions permettant toutes les deux le calcul de an pour n ∈ N∗ avec interdiction d’utiliser
la commande **.
1 def Obvious_exp(a,n): 1 def Quick_exp(a,n):
2 y = 1 2 if n == 1:
3 for k in range(1, n+1): 3 return a
4 y *= a 4 if n % 2 == 0:
5 return y 5 y = Quick_exp(a, n//2)
6 return y*y
7 else:
8 y = Quick_exp(a, (n-1)//2)
9 return y*y*a
Calculer leur complexité, en détaillant. (Pour Quick_exp, on calculera CT (2n ) pour simplifier.
Exercice 10. On considère les fonctions ci-dessous :
1 def f(n): 1 def g(n):
2 p = 1 2 s = 0
3 for i in range(1, n+1): 3 for i in range(n+1):
4 p *= i 4 s += f(i)
5 return p 5 return s
1. Que fait f ? Préciser sa complexité.
2. Que fait g ? Préciser sa complexité.
3. Proposer une amélioration pour l’algorithme de g ayant une complexité linéaire.
Exercice 11.
T. Lopez Page 5 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
Trouver la complexité de la fonction Fib(n) qui cal-
1 def Fib(n):
cule le n-ième term de la suite de Fibonacci.
2 if n==0 or n ==1:
Elle est bien entendu exponentielle, mais on cherchera le
3 return 1
réel α tel qu’il existe une constant K vérifiant :
4 return Fib(n-1) + Fib(n-2)
CT (n) ∼ Kαn
T. Lopez Page 6 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
5 De multiples programmes pour des mêmes problèmes
Pour chacun des programmes suivants, déterminer la complexité dans le pire des cas et dans le meilleur des cas.
def sans_doublon1(L): def sans_doublon2(L):
for x in L: for i in range(len(L)):
s = 0 for j in range(i+1, len(L)):
for y in L: if L[i] == L[j]:
if x == y: return False
s += 1 return True
if s > 1:
return False
return True
def sans_doublon3(L): def sans_doublon4(L):
Ldejavu = [] Ddejavu = []
for x in L: for x in L:
if x in Ldejavu(L): if x in Ddejavu(L):
return False return False
else: else:
[Link](x) Ddejavu[x] = True
return True return False
def sans_doublon5(L):
Lrestant = [Link]()
while Lrestant != []:
x = [Link]()
if x in Lrestant:
return False
return True
def est_croissante1(L): def est_croissante2(L):
for i in range(len(L)): for i in range(len(L)):
for j in range(len(L)): for j in range(i+1, len(L)):
if i < j and f(i) > f(j): if L(i) > L(j):
return False return False
return True return True
def est_croissante3(L):
for i in range(len(L)-1):
if L[i] > L[i+1]:
return False
return True
T. Lopez Page 7 Louis-le-Grand
Exercices — Chapitre 1 — Complexité algorithmique ITC — MPSI
def somme1(L): def somme2(L, i, j):
if len(L) == 0: if i == j:
return 0 return L[i]
else: else:
return L[0] + somme1(L[1:len(L)]) return L[i] + somme2(L, i + 1, j)
def somme3(L, i, j):
if i == j:
return L[i]
else:
m = (i + j) // 2
return somme3(L, i, m) +
somme3(L, m + 1, j)
def recherche1(x,L): def recherche2(x,L):
for i in range(len(L)): a = 0
if x == L[i]: b = len(L) - 1
return i m = (a + b) // 2
return None while a <= b:
if L[m] == x:
return m
if L[m] < x:
a = m+1
else:
b = m-1
m = (a + b) // 2
return None
def recherche3(L, x, i, j): def recherche4(L, x, i, j):
if i > j: if i > j:
return None return None
if L[i] == x: m = (i + j) // 2
return i if L[m] == x:
else: return m
return recherche3(L, x, i+1, j) if L[m] > x:
return recherche4(L, x, i, m - 1)
if L[m] < x:
return recherche4(L, x, m + 1, j)
T. Lopez Page 8 Louis-le-Grand