Solu tions des exer cices du cha pitre 2
451
© Dunod – Toute reproduction non autorisée est un délit.
contraire), T1(i 1 ) est donc inséré en posi tion k de Τ : si a est un élé ment de T1, c’est àdire
a = T1(i 1 – l), puisque T1 est trié, on a a < T1(i 1 ) ; si a est un élé ment de T2 c’est àdire l’élé
ment T2(i 2 – l), à l’étape pré cé dente on avait T1(i 1 ) . T2(i 2 2 1) 5 a, ainsi l’élé ment T1(i 1 )
est donc bien cor rec te ment inséré dans T. La boucle de l’ins truc tion 2 se ter mine lorsque tous
les élé ments de l’un des deux tableaux (mais pas des deux) ont été insé rés. Sup po sons que ce
soit l’ensemble des élé ments de T2 qui soit dans Τ avant que tous les élé ments de T1 soient
insé rés (ici aussi, l’autre cas est ana logue). Le pre mier élé ment non encore inséré de T1 a une
valeur supé rieure au der nier élé ment de T2, sinon il aurait été inséré avant celui ci. Τ est donc
trié, et contient tous les élé ments de T1 et T2.
L’inser tion d’un élé ment dans Τ demande un nombre constant d’opé ra tions élé men taires,
que se soit dans le corps dans la boucle de l’ins truc tion 2 ou dans l’ins truc tion de la ligne 6,
n élé ments sont insé rés, la com plexité est donc O(n) que se soit dans le pire des cas, dans le
meilleur des cas ou dans le cas moyen.
3) Sup po sons dans un pre mier temps que n, la taille du tableau, soit de la forme
n = 2
k
, k étant un entier. Dans ce cas, à chaque étape, un tableau est séparé en deux tableaux
de tailles égales. Ainsi, au pre mier niveau, le tableau est séparé en 2 tableaux de taille 2
k–1
,
au deuxième niveau, il y aura 2
2
= 4 tableaux de taille 2
k–2
, et ainsi de suite jus qu’au moment
où chaque tableau est de taille 1 et n’est donc plus séparé. À ce stade nous sommes arri vés au
niveau k = log 2 n de sépa ra tion et il y a n tableaux.
À tout niveau b il y a donc 2
b
tableaux de taille 2
k–b
; nous avons vu que la fusion de deux
tableaux de taille
t
2
néces si tait O(t) opé ra tions ; à chaque niveau, les opé ra tions de fusion
néces sitent donc O(2
b
2
k–b
) = O(2
k
). Puisque il y a k niveaux, l’ensemble des opé ra tions de
fusion néces site O(k2
k
) = O(n log n) opé ra tions élé men taires. Le nombre d’opé ra tions néces
saires à la sépa ra tion du tableau est O(n) puisque la sépa ra tion s’arrête quand chaque tableau
est de taille uni taire. Le nombre d’opé ra tions pour l’ensemble de l’algo rithme est donc
O(n log n) + O(n) = O(n log n).
Lorsque n n’est pas de la forme n = 2
k
, soit k l’entier tel que 2
k21 , n , 2
k
. Le nombre
d’opé ra tions exé cu tées par l’algo rithme est moindre que celui néces saire pour un tableau de
taille 2
k
. La com plexité de l’algo rithme est donc O(n log n).
451
© Dunod – Toute reproduction non autorisée est un délit.
contraire), T1(i 1 ) est donc inséré en posi tion k de Τ : si a est un élé ment de T1, c’est àdire
a = T1(i 1 – l), puisque T1 est trié, on a a < T1(i 1 ) ; si a est un élé ment de T2 c’est àdire l’élé
ment T2(i 2 – l), à l’étape pré cé dente on avait T1(i 1 ) . T2(i 2 2 1) 5 a, ainsi l’élé ment T1(i 1 )
est donc bien cor rec te ment inséré dans T. La boucle de l’ins truc tion 2 se ter mine lorsque tous
les élé ments de l’un des deux tableaux (mais pas des deux) ont été insé rés. Sup po sons que ce
soit l’ensemble des élé ments de T2 qui soit dans Τ avant que tous les élé ments de T1 soient
insé rés (ici aussi, l’autre cas est ana logue). Le pre mier élé ment non encore inséré de T1 a une
valeur supé rieure au der nier élé ment de T2, sinon il aurait été inséré avant celui ci. Τ est donc
trié, et contient tous les élé ments de T1 et T2.
L’inser tion d’un élé ment dans Τ demande un nombre constant d’opé ra tions élé men taires,
que se soit dans le corps dans la boucle de l’ins truc tion 2 ou dans l’ins truc tion de la ligne 6,
n élé ments sont insé rés, la com plexité est donc O(n) que se soit dans le pire des cas, dans le
meilleur des cas ou dans le cas moyen.
3) Sup po sons dans un pre mier temps que n, la taille du tableau, soit de la forme
n = 2
k
, k étant un entier. Dans ce cas, à chaque étape, un tableau est séparé en deux tableaux
de tailles égales. Ainsi, au pre mier niveau, le tableau est séparé en 2 tableaux de taille 2
k–1
,
au deuxième niveau, il y aura 2
2
= 4 tableaux de taille 2
k–2
, et ainsi de suite jus qu’au moment
où chaque tableau est de taille 1 et n’est donc plus séparé. À ce stade nous sommes arri vés au
niveau k = log 2 n de sépa ra tion et il y a n tableaux.
À tout niveau b il y a donc 2
b
tableaux de taille 2
k–b
; nous avons vu que la fusion de deux
tableaux de taille
t
2
néces si tait O(t) opé ra tions ; à chaque niveau, les opé ra tions de fusion
néces sitent donc O(2
b
2
k–b
) = O(2
k
). Puisque il y a k niveaux, l’ensemble des opé ra tions de
fusion néces site O(k2
k
) = O(n log n) opé ra tions élé men taires. Le nombre d’opé ra tions néces
saires à la sépa ra tion du tableau est O(n) puisque la sépa ra tion s’arrête quand chaque tableau
est de taille uni taire. Le nombre d’opé ra tions pour l’ensemble de l’algo rithme est donc
O(n log n) + O(n) = O(n log n).
Lorsque n n’est pas de la forme n = 2
k
, soit k l’entier tel que 2
k21 , n , 2
k
. Le nombre
d’opé ra tions exé cu tées par l’algo rithme est moindre que celui néces saire pour un tableau de
taille 2
k
. La com plexité de l’algo rithme est donc O(n log n).