aquestion.py

Created on December 16, 2024
1.4 KB
Quel algorithme a été utilisé :
le tri par
insertion ou le tri fusion ?:
  
D'après l'illustration, 
la liste a été 
triée avec l'algorithme de tri
fusion. En
effet, à chaque étape de cet 
arbre, la liste est partagée 
en deux morceaux de
même taille. Lorsque l'on 
remonte des feuilles de 
l'arbre vers la racine, on
s'aperçoit que chaque nœud 
contient la liste triée
obtenue en fusionnant la
liste triée de son fils
gauche avec celle de son
fils droit

Identifier le tri qui a une 
complexité, dans le pire des 
cas, en O(n2) et identifier 
le tri qui a une
complexité, dans le pire 
des cas, en O(n log2 n). 
Justifier brièvement ces 
deux complexités : 


Étudions la complexité de 
ces deux algorithmes.
Commençons par le tri par 
insertion. Dans le pire cas,
le tableau est au
départ trié par ordre 
décroissant et il faut 
parcourir, à chaque insertion,
tous les précédents afin 
de trouver l’emplacement 
où insérer. Le nombre
total d’accès au tableau
est alors de ∑
i=2
n
i=(n−1)(n+2)
2 =O(n 2) .
Pour le tri fusion, nous nous 
appuierons sur l'illustration
en arbre fournie à
la question précédente.
La hauteur de l'arbre est 
en O(log2 n). Pour
chaque passage au niveau 
supérieur de l'arbre, 
l'ensemble des valeurs est
parcouru (chacune des 
sous-listes est parcourue 
au moment de sa fusion
avec sa voisine). 
La complexité de cet 
algorithme est donc en 
O(n log2 n)