Lycée Malherbe Année scolaire 2018-2019 MPSI - Informatique pour tous

TP no 7 - Introduction à la complexité
Un corrigé sera placé sur mon site à l’issue des séances:
http://roux.lycee.malherbe.free.fr/
Ce TP est une introduction à la notion de complexité, qui fait l’objet d’un chapitre du cours. Le but
est de vous sensibiliser au fait que des algorithmes différents pour un même problème peuvent avoir une
complexité sensiblement différente. Et aussi qu’un algorithme peut se comporter de façon très différente
suivant l’entrée qu’on lui donne.

En pratique, on se posera différents problèmes (faciles. . . ) sur des listes Python d’entiers, et on
confrontera différentes méthodes pour les résoudre.
Pour étudier expérimentalement la complexité, vous pourrez utiliser la commande time du module
time, dont le petit exemple d’utilisation ci-dessous devrait vous permettre de comprendre le fonctionne-
ment :

1 from time import time
2
3 t=time()
4 for i in range(100000000):
5 continue
6 print(time()-t,"secondes")
 

1 2.9907541275024414 secondes
Pour avoir une mesure universelle du temps pris par les différents algorithmes, et pouvoir les comparer,
on pourra aussi compter des opérations élémentaires significatives lors du déroulement de ces algorithmes.
En l’occurence : le nombre de sommes d’éléments pour la partie 1, et le nombre de comparaisons entre
éléments de la liste, ou avec un autre élément, pour le reste du TP. Dans vos programmes, vous pourrez
compter expérimentalement ces opérations à l’aide de compteurs.

Pour faire des tests intéressants, je vous suggère de définir dès maintenant la fonction liste_alea(n)
suivante.

1 from random import randrange
2
3 def liste_alea(n):
4 ’’’Fonction créant une liste de n entiers aléatoires
5 compris entre 0 et n-1’’’
6 return [ randrange(n) for _ in range(n) ]
 

1 Quelle est la probabilité qu’un nombre i P v0, n ´ 1w soit dans la liste renvoyée par liste_alea(n) ?
Vers quoi tend cette probabilité quand n tend vers l’infini ?

1 Sommes cumulées et ordre de grandeur de complexité

2 Ecrire (et documenter) une fonction sommes_cumulees(L) qui prend en argument une liste et
renvoie une liste de même taille dont le i-ième terme est la somme des i premiers termes de L. Par
exemple, avec L=[2,6,1,0,7], sommes_cumulees(L) donnera [2,8,9,9,16].

1
 3 Evaluez la complexité de votre fonction (on a dit dans l’introduction que pour la partie 1, on
comptait le nombre de sommes calculées), en fonction de la longueur n de la liste passée en argument.
Bien sûr, la réponse peut varier suivant la manière dont vous avez écrit votre programme !

4 ‹ Montrer la différence d’efficacité des algorithmes en les chronométrant avec une liste aléatoire de
longueur 100 000.

5 ‹‹ Montrer en chronométrant votre fonction, que l’ordre de grandeur de leur complexité est bien
celui annoncé plus haut.

Moralité : le choix de l’algorithme peut s’avérer crucial pour résoudre un problème en un temps
raisonnable.

Jusqu’à la fin du TP, comme mesure de la complexité, on prendra le nombre de comparaisons entre
éléments de la liste passée en arguments, et avec un autre élément le cas échéant.

2 Complexité dans le pire et dans le meilleur cas

2.1 Recherche du maximum dans une liste

6 Ecrire une fonction maximum(L) qui renvoie le plus grand élément de la liste L.

7 Ecrire une fonction maximum_indice(L) qui renvoie l’indice de la première occurence du plus grand
élément de la liste L.

8 La complexité dépend-elle de la liste ? Evaluez la complexité des fonctions écrites.

9 Que pensez-vous de la solution suivante qui utilise la fonction maximum écrite avant ?

1 from maximum import *
2
3 def maximum_indice(L):
4 m=maximum(L)
5 for i in range(len(L)):
6 if L[i]==m:
7 return i
8
9 print(maximum_indice([9,15,7,3,19,8,2,7]))
 

2.2 Recherche dans une liste non triée

On considère 4 fonctions de recherche d’un élément dans une liste non triée (chaque fonction prend
en arguments une liste L et un élément x, et renvoie True si x apparaı̂t dans L, et False sinon.

1 def recherche1(L,x):
2 test=False
3 for y in L:
4 if y==x:

2
5 test=True
6 return(test)
 


1 def recherche2(L,x):
2 test=False
3 for y in L:
4 if y==x:
5 test=True
6 break
7 return(test)
 


1 def recherche3(L,x):
2 for y in L:
3 if y==x:
4 return True
5 return False
 


1 def recherche4(L,x):
2 i=0
3 trouve=False
4 while i<len(L) and not trouve:
5 if L[i]==x:
6 trouve=True
7 i=i+1
8 return trouve
 

10 Testez ces fonctions.

11 Ces fonctions parcourent-elles toute la liste pour tous les arguments ?

12 Illustrez la question précédente en comptant expérimentalement des nombres de comparaisons

(modifiez les fonctions pour qu’elles comptent !).

13 ‹ En Python, on peut simplement écrire x in L (booléen) pour savoir si x est dans L ? Mettre en
place une expérience pour savoir si le parcours est interrompu dès que x est trouvé.

14 Créez une nouvelle fonction recherche_premiere_occurence en modifiant la fonction recherche3

pour qu’elle retourne la position i de la première occurence de x dans la liste L. Si x n’apparait pas dans L,
la fonction retourne ´1. Que dire de sa complexité dans le pire et dans le meilleur cas ?

15 Créez une nouvelle fonction recherche_liste_positions qui ne renverra rien, mais selon le cas,
affichera un message du type

Le nombre 98 ne se trouve pas dans la liste.

ou Le nombre 3245 appara^

ıt en tout 221 fois, aux positions [12,21,789,...]

Que dire de sa complexité dans le pire et dans le meilleur cas ?

3
 Moralité : la complexité d’un algorithme peut varier entre deux instances de même taille ! Il est alors
pertinent de donner la complexité dans le meilleur, et dans le pire cas.

3 Recherche dans une liste triée

On suppose désormais que l’on manipule des listes de nombres classés par ordre croissant.
Python dispose d’une commande permettant de trier les éléments d’une liste par ordre croissant,
dont voici la syntaxe :

1 L=[2,7,4,-3,12]
2 L.sort()
 

Attention ! Prenez conscience que cette commande sort n’a rien d’anodin. L’algorithme qui se cache
derrière (appelé “algorithme de tri”) est plus complexe que tous ceux que nous avons vus jusqu’à présent.
Plusieurs algorithmes de tris seront étudiés en IPT en MP, ainsi que cette année en option informatique.

Nous allons implémenter une fonction de recherche dichotomique du cours, qui tient compte du fait
que la liste est triée.
Essayez d’analyser la façon dont vous cherchez un mot dans un dictionnaire (papier). Vous ne le
parcourez assurément pas du début jusqu’à trouver (ou non) le mot recherché.
L’idée est la suivante : supposons que L=[2,6,9,13,16,19,21,34,46,60,62,73,80] et que le nombre
à rechercher soit 34.
— On regarde le terme du milieu : ici c’est L[6] qui vaut 21. Puisque 21 ă 34, si 34 se trouve dans
la liste c’est forcément après 21. On va donc chercher dans la sous-liste qui commence à L[7] et
se termine à la fin, c’est-à-dire [34,46,60,62,73,80].
— On recommence avec cette sous-liste : ici il y a un nombre pair de termes donc on décide (par
exemple) de regarder 62. Celui-ci est plus grand que le nombre cherché, donc on cherche dans la
sous-liste [34,46,60].
— etc.
Ce procédé est appelé recherche dichotomique.

16 Créez une fonction recherche dichotomique(L,x).

17 ‹‹ Quelle est la complexité dans le pire et dans le meilleur cas de la recherche dichotomique ?

18 Chronométrer un peu le tri d’une liste aléatoire, ainsi que l’application de recherche_dicho et de
recherche3 (par exemple).

19 Modifiez les fonctions recherche et recherche_dicho pour qu’elles renvoient le nombre de compa-
raisons effectuées, et comparer par une batterie de tests. (Les temps pour recherche_dicho sont tellement
petits ! ! !)

20 ‹‹ S’il vous reste du temps, vous pouvez tenter d’écrire une fonction de votre cru pour le tri... !