INFO Exercices de complexité l.

albert

1. Donner un exemple d’algorithme dont la complexité spatiale vérifie une relation t(n) = t(n − 1) + t(n − 2) + f (n)
On suppose que f est positive croissante d’ordre polynomial. Chercher une estimation asymptotique de t.

2. Étudier la complexité temporelle de la recherche par dichotomie. En faire l’étude asymptotique.

3. Résoudre la récurrence un = 4un/2 + n2 pour n = 2k .

Solution proposée
On pose vk = u2k et on a vk = 4vk−1 + 22k , d’où u2k = vk = (u1 + k)22k .

4. Résoudre asymptotiquement les complexités des relations de récurrence :

1o t(n) = 2t(dn/2e) + n log2 n
2o t(n) = 2t(b(n − 1)/2c) + n

5. On définit une suite (un ) par les relations :

u0 = 1, un = ubn/2c + ubn/3c pour n > 1.
Les deux algorithmes suivants calculent un :
let rec u_1(n) =
if n = 0 then 1 else u_1(n/2) + u_1(n/3)
;;

let u_2(n) =
let v = make_vect (n+1) 0 in
v.(0) <- 1;
for i=1 to n do v.(i) <- v.(i/2) + v.(i/3) done;
v.(n)
;;

Comparer les complexités spatiales et temporelles de ces deux fonctions Caml.

6. Résoudre asymptotiquement les relations de récurrence :

t(n) = 5t(n − 1) + 3n + 2 t(0) = 7
c(n) = 7c(E(n/2)) + O(n2 ).
(le O(·) est supposé être une fonction croissante).

Solution proposée
Pn 3k+2
On pose u(n) = t(n)/5n d’où t(n) = 5n [7 + k=1 5k
] = O(5n ).
c(2k )
On résout pour n = 2p . On pose v(k) = 2k log2 7
. On trouve c(n) = Θ(nlog2 7 ).
L. Albert Exos Complexité 2

7. Montrer l’assertion suivante :

Pour A, B 6 N , le nombre de divisions euclidiennes effectuées√pour calculer le PGCD de A et B par
1+ 5
l’algorithme d’Euclide est majoré par logφ (N ) + 2, où φ = . Le pire des cas est obtenu lorsque A
2
et B sont des nombres de Fibonacci consécutifs.
Indication : on pourra choisir un nombre d’étapes e et chercher quelle est la plus petite valeur Ne pour laquelle on
peut trouver deux entiers A, B 6 Ne pour lesquels le calcul du pgcd nécessite e divisions.

8. On considère la suite f de Dijkstra définie par :

f (0) = 0, f (1) = 1, f (2k) = f (k), f (2k + 1) = f (k) + f (k + 1).

En considérant une suite auxiliaire à valeurs dans N2 , déterminer un algorithme récursif de calcul de f (n) de com-
plexité logarithmique.

Indications
Définition récursive brute :

let rec suite1 n =

match n with
| 0 -> 0
| 1 -> 1
| _ -> if (n mod 2)=0 then suite1 (n/2)
else let m = n/2 in suite1 m + suite1 (m+1);;

Supposons l’existence d’une fonction suite2 telle que

µ ¶
f2k
suite2 k =
f2k+1
qui ne soit programmée que par un appel récursif à suite2 (k/2). Sa complexité sera ainsi logarithmique.
Voyons son cahier des charges
- si k est pair (k=2p) suite2 k doit retourner µ ¶
f4p
f4p+1
sachant que par l’appel récursif elle connaı̂t
µ ¶ µ ¶
f2p x
suite2(k/2) = suite2(p) = =
f2p+1 y
dans ce cas suite2 retourne µ ¶ µ ¶ µ ¶
f4p f2p x
= =
f4p+1 f2p + f2p+1 x+y
- si k est impair (k=2p+1) suite2 k doit retourner
µ ¶
f4p+2
f4p+3
sachant que par l’appel récursif elle connaı̂t toujours
µ ¶ µ ¶
f2p x
suite2(k/2) = suite2(p) = =
f2p+1 y
Cette fois ci suite2 retourne
µ ¶ µ ¶ µ ¶
f4p+2 f2p+1 f2p+1
= =
f4p+3 f2p+1 + f2p+2 f2p+1 + fp+1
µ ¶ µ ¶ µ ¶
f2p+1 f2p+1 y
= = =
f2p+1 + f2p+1 − fp f2p+1 + f2p+1 − f2p 2y − x
Voici la traduction Caml de ces considérations :
L. Albert Exos Complexité 3

let suite2 n = (* en se ramenant a une suite vectorielle *)

let rec suitevect p =
if p=0 then (0,1)
else let (x,y) = suitevect (p/2) in
if (p mod 2) =0 then (x,x+y) else (y,2*y-x)
in let (u,v) = suitevect (n/2) in
if (n mod 2)=0 then u else v;;

(* suite1 4321, suite2 4321;; *-> int * int = 85, 85 *)

9. Vous vous trouvez face à un mur, trop haut et trop lisse pour que vous puissiez l’escalader. À gauche comme à
droite, le mur semble continuer jusqu’à l’infini. Vous savez qu’une porte est percée dans ce mur, mais vous ne savez
pas si elle est à votre gauche ou à votre droite, vous ne connaissez même pas la distance d à laquelle elle se trouve de
vous ; et la porte est à peine visible, si bien qu’il faut être juste devant elle pour la voir. Décrire une stratégie vous
permettant de trouver cette porte, tout en parcourant une distance O(d).

Solution proposée
Parcourir un km vers la gauche, revenir au point de départ ; parcourir deux km vers la droite, revenir au point de
départ ; et ainsi de suite en doublant à chaque fois la distance. Soit n tel que 2n < d 6 2n+1 ; au pire, on devra
parcourir 2(1 + 2 + . . . + 2n+1 ) + d = 2n+3 − 2 + d < 9d.

10. Soit n > 1 un entier. Le but de l’exercice est d’évaluer le nombre de multiplications requises pour calculer an
connaissant a. Ainsi, on peut calculer a10 en 4 multiplications de la façon suivante : a.a = a2 , a2 .a = a3 , a3 .a2 = a5 ,
a5 .a5 = a10 . On note P (n) le nombre minimal de multiplications requises pour calculer la puissance n-ième d’un
nombre et B(n) le nombre de bits égaux à 1 dans la représentation de n en base 2.
1o Établir les inégalités :
- (1) P (nm) 6 P (n) + P (m),
- (2) dlog2 ne 6 P (n) 6 blog2 nc + B(n) − 1
2o a. En déduire les valeurs de P (n) pour n différent de 7 et inférieur ou égal à 10 en justifiant votre calcul.
b. Montrer que P (15) 6 5. En déduire que l’inégalité P (n) 6 blog2 nc + B(n) − 1 n’est pas optimale.

11. Que fait la fonction Caml suivante :

let rec f = function
| [] -> failwith "liste vide"
| [t] -> (t,t)
| t::q -> let (a,b) = f q in
if t<a then (t,b) else
if t>b then (a,t) else (a,b);;
Prouvez votre réponse, étudiez la complexité de cette fonction. Qu’en pensez vous ?

Solution proposée
Cette fonction calcule le couple (minimum, maximum) d’une liste. On prouve le résultat par récurrence immédiate
sur la longueur de la liste considérée.
La complexité de cette fonction en nombre de comparaisons vérifie c(0) = c(1) = 0 et c(n) 6 2 + c(n − 1). On en
déduit que c(n) = O(n) (plus précisément ∀ n > 2, c(n) 6 2(n − 1)).
La complexité linéaire était attendue (il faut de toute façon lire toute la liste). La complexité est ici inférieure à
celle de l’algorithme naı̈f qui agit en deux passes. Il existe des raffinements de cet algorithme pour faire diminuer les
constantes (cf. cours).
L. Albert Exos Complexité 4

12. La fonction Caml suivante utilise une méthode diviser pour régner en vue de calculer la plus petite et la plus
grande composante d’un vecteur d’entiers :

let minmax t =
let rec minmax_rec t i j =
if i=j then (t.(i),t.(i))
else if i+1=j then begin
if t.(i)<t.(j) then (t.(i),t.(j))
else (t.(j),t.(i))
end
else let k=(i+j)/2 in
let (min1,max1) = minmax_rec t i k
and (min2,max2) = minmax_rec t (k+1) j in
((min min1 min2),(max max1 max2))
in minmax_rec t 0 (vect_length t - 1);;

Justifier la validité de cette fonction puis, notant Cn le nombre de comparaisons entre éléments de t effectuées lorsque
la fonction est appliquée à un vecteur de n éléments, déterminer des constantes a et b optimales telles que :

∀n > 2 : an 6 Cn + 2 6 bn

Solution proposée
La suite (Cn )n>1 est définie par :

C1 = 0, C2 = 1, C2n = 2Cn + 2 pour n > 2, et C2n+1 = Cn + Cn+1 + 2 pour n > 1

En posant Dn = Cn + 2, on a les relations plus simples :

D1 = 2, D2 = 3, D2n = 2Dn pour n > 2, et D2n+1 = Dn + Dn+1 pour n > 1

Restent à trouver les constantes a et b optimales pour l’encadrement an 6 Dn 6 bn.

(Dn ) est une suite croissante comme on le vérifie sans peine par récurrence.
L’examen de la suite de terme général Dnn (avec Maple par exemple) suggère les valeurs a = 32 et b = 35 .
Le cas minimal semblant être atteint pour (D2n ). Le calcul fournit D2n = 3 · 2n−1 , ∀ n > 1. On vérifie ensuite par
3
récurrence (forte1 ) que ∀ n > 2, Dn > n.
2

Ainsi a = 3/2 convient.

5
Pour b, il semblerait que le maximum, , soit atteint pour n = 3 · 2n , ∀ n > 0.
3
Il suffit alors de le vérifier en 2 temps :
– D3·2n = 5 · 2n ,
5
– ∀ n > 2, Dn 6 n.
3
La première assertion est immédiate puisque D3·2n = 2D3·2n−1 = . . . = 2n · D3 = 5 · 2n ; la seconde se vérifiant alors
par récurrence (”forte” à nouveau).
Pour info, voici le code Maple
u := proc(n)
local k;
option remember;
if n = 1 then 2
elif n = 2 then 3
else
1 J’entends par récurrence ”forte” la proposition :
¡ ¢
p(0) et (∀ n ∈ N, [∀k 6 n, p(k)]) =⇒ p(n + 1) =⇒ (∀ n ∈ N, p(n)).
alors que dans la preuve par récurrence usuelle, on suppose seulement p(n) pour montrer p(n + 1).
L. Albert Exos Complexité 5

k := iquo(n, 2);
if type(n, odd) then u(k) + u(k + 1)
else 2*u(k)
end if
end if
end proc

> for i to 30 do i,‘ ‘, (u(i)/i), ‘ ‘, evalf(u(i)/i) od;

1, , 2, , 2.
2, , 3/2, , 1.500000000
3, , 5/3, , 1.666666667
4, , 3/2, , 1.500000000
5, , 8/5, , 1.600000000
6, , 5/3, , 1.666666667
7, , 11/7, , 1.571428571
8, , 3/2, , 1.500000000
9, , 14/9, , 1.555555556
10, , 8/5, , 1.600000000
18
11, , --, , 1.636363636
11
12, , 5/3, , 1.666666667
21
13, , --, , 1.615384615
13
14, , 11/7, , 1.571428571
23
15, , --, , 1.533333333
15
16, , 3/2, , 1.500000000
26
17, , --, , 1.529411765
17

13. Deuxième plus grand élément.

Soit V un vecteur d’entiers de taille n > 1. On cherche à déterminer l’indice du deuxième plus grand élément de V
(celui qui viendrait en deuxième position si on rangeait les éléments de V par ordre décroissant).
1o Proposer une solution naı̈ve en Caml à ce problème. Quel nombre de comparaisons entre entiers de V effectue
cette fonction ?
2o Pour imaginer une meilleure solution, penser à un tournoi de Tennis. Le deuxième meilleur joueur n’est pas
forcément le finaliste mais figure parmi les adversaires du gagnant.
En déduire une nouvelle solution et analyser sa complexité.

14. Recherche linéaire du k-ième plus petit élément d’une liste

1o Méthode élémentaire.
On se donne une liste non triée d’éléments d’un ensemble ordonné (nous travaillerons sur des entiers) dont il s’agit
ième
de chercher le k élément dans l’ordre croissant.
Proposer en Caml un algorithme naı̈f permettant d’atteindre ce but.
En préciser la complexité en nombre de comparaisons.
L. Albert Exos Complexité 6

2o Une méthode linéaire

Supposons la liste partagée en deux morceaux autour d’un pivot, les éléments plus petits que le pivot d’une part
(liste1 de taille n1 ) et les éléments plus grand (strictement) d’autre part (liste2 de taille n2 ).
Si n1 > k, on applique la procédure à la première liste sinon, on applique la procédure à la deuxième liste en
remplaçant k par (k − n1 ).
La procédure est donc récursive.
Écrire une fonction Decoupe liste pivot qui prend en argument une liste et un pivot et renvoie le quadruplet
(liste1 , n1 , liste2 , n2 )
3o Bien sûr, l’algorithme tournera d’autant plus vite que l’on aura choisi le pivot proche de l’élément médian2 de
la liste, mais il faut le trouver lui aussi de façon linéaire.
Une bonne idée consiste à découper la liste de départ en paquets de 5 éléments (que l’on peut trier en temps
constant) puis à appliquer récursivement la méthode de recherche du pivot à la liste des médians de ces sous-listes.
a. Écrire en Caml l’algorithme de tri par insertion.
b. Écrire une fonction Quintuplifie liste dont le résultat est la liste des éléments de liste groupés en
quintuplets (un peu moins peut-être pour le dernier paquet).
c. Écrire une fonction Medians liste qui aprés avoir trié toutes les sous listes de longueur 5 (on utilisera un
map) renvoie la liste de leurs éléments médians (i.e. les 3èmes éléments des quintuplets triés).
Si le dernier paquet n’a pas 5 éléments, on se contentera de renvoyer son premier élément.
ième
d. Écrire une fonction nth n liste qui retourne le n élément d’une liste quelconque.
e. L’algorithme récursif est alors le suivant :
let rec nth_lin\’{e}aire i liste=
let choisit_pivot l n = nth_lin\’{e}aire ((n+4)/10) (M\’{e}dians l) in
let n=list_length liste in
if i>n then failwith "liste trop courte"
else if n<=5 then nth i (Tri_insertion liste)
else let l1,n1,l2,n2=D\’{e}coupe liste (choisit_pivot liste n) in
if i<n1 then nth_lin\’{e}aire i l1
else nth_lin\’{e}aire (i-n1) l2;;
Commenter ce code puis montrer que la récurrence vérifiée par le coût T (n) de l’algorithme vérifie :

T (n) 6 T (n/5) + T (7n/10) + c · n

et en déduire que cet algorithme est bien linéaire.

Solution proposée

15. En considérant qu’il y a 256 caractères possibles on veut comparer 2 textes composés de n caractères. On les
compare jusqu’à épuiser une chaine ou trouver 2 caractères différents. Majorer le nombre moyen de comparaisons à
effectuer pour comparer 2 textes de longueur au plus n.

16. 1o Quelle est la complexité du calcul d’un déterminant d’ordre n, développé récursivement suivant la première
colonne ?
2o Quelle est cette complexité temporelle si on mémorise tous les déterminants mineurs, afin d’eviter de les
calculer plusieurs fois ? Quelle est alors la complexité spatiale ?

17. La multiplication classique de deux matrices 2 × 2 requiert 8 multiplications et 4 additions scalaires, la multi-
plication de deux matrices n × n nécessitant O(n3 ) opérations arithmétiques. Le nombre de multiplications peut être
réduit à l’aide du paradigme diviser pour régner.
2 Celui qui réalise |liste1 | = |liste2 | à 1 près.
L. Albert Exos Complexité 7

1o L’algorithme de Strassen repose sur la décomposition des deux matrices à multiplier en 4 blocs :
µ ¶ µ ¶
A B E F
M= , N= ,
C D G H
µ ¶
−P2 + P4 + P5 + P6 P1 + P2
La matrice produit vaut M N = avec :
P3 + P4 P1 − P3 + P5 − P7

P1 = A(F − H),
P2 = (A + B)H,
P3 = (C + D)E,
P4 = D(G − E),
P5 = (A + D)(E + H),
P6 = (B − D)(G + H),
P7 = (A − C)(E + F ).

Quel est le nombre d’opérations arithmétiques effectuées ?

2o Pour multiplier des matrices n × n, on applique l’égalité précédente récursivement (attention, la multiplication
de matrices n’est pas commutative !) (on peut supposer que n est une puissance de deux). On note c(n) le coût
n
pour effectuer la multiplication de deux matrices n × n. Exprimer c(n) en fonction de c( ).
2
3o En déduire c(n). Estimer le gain par rapport à la méthode naı̈ve.

18. Multiplication Rapide. Pn Pm

On considère deux polynômes P = i=0 ai X i et Q = j=0 bj X j de Q[X]. On note N = max(deg P, deg Q) + 1
(ainsi N désigne un majorant de la place mémoire allouée par polynôme).
1o Le produit de ces deux polynômes peut se faire suivant l’algorithme naı̈f :
 
XN XN
P ·Q=  (ai × bj )X i+j 
i=0 j=0

Quelle est la complexité C(N ) de cet algorithme en nombre de multiplications élémentaires × ?

2o Soit M = dN/2e (partie entière supérieure). On écrit chacun des deux polynômes sous la forme

P = P1 + X M P2 Q = Q1 + X M Q2

avec P1 , P2 , Q1 , Q2 quatre polynômes de degrés inférieurs strictement à M .

a. On a alors
P · Q = P1 · Q1 + X M (P1 · Q2 + P2 · Q1 ) + X 2M P2 · Q2
On note C 0 (N ) le nombre de multiplications élémentaires nécessaires au calcul du produit sous cette forme.
C 0 (1) = 1. Vérifier que
C 0 (N ) = 4C 0 (dN/2e) + O(N )
(on considère en effet que les coûts ”autres” sont un O(N )). En déduire C 0 (N ). Commentaires ?
b. On écrit
P · Q = R1 + X M (R2 − R1 − R3 ) + X 2M R3
avec R1 = P1 · Q1 , R2 = (P1 + P2 ) · (Q1 + Q2 ) et R3 = P2 · Q2 . Déterminer la nouvelle complexité C 00 (N ).
3o On désire appliquer ce qui précède au produit de grands entiers écrits en base B (algorithme de Karatsuba).

n = aB m + b m = cB m + d

a. Que se passe-t-il qui ne se produisait pas avec le produit de deux polynômes ?

b. Ceci change-t-il la complexité en nombre de multiplications élémentaires ?

Solution proposée
L. Albert Exos Complexité 8

P
1o Le calcul du produit naı̈f nécessite deux boucles for imbriquées (une par ) et le nombre de multiplications
élémentaires est (degP + 1)(degQ + 1) soit O(N 2 ).
2o a. La résolution de cette équation de récurrence est un classique du cours : on trouve C 0 (N ) = O(N log2 4 ) =
O(N 2 ). On n’a donc rien gagné en ordre de grandeur par rapport à la méthode brutale.
Remarque(s). Comme c’est la première fois dans cette épreuve, vous avez tout intérêt à redémontrer le
résultat du cours. Il faudra donc
– commencer par signaler que la fonction C 0 (N ) est croissante en fonction de N .
– supposer donc dans un premier temps que N = 2p
– poser up = C 0 (2p ) et déterminer up
– enfin conclure dans le cas général pour N par monotonie (i.e. en encadrant).
b. Cette fois ci C 00 vérifie :
C 00 (N ) = 3C 00 (dN/2e) + O(N )
On obtient donc C 00 (N ) = O(N log2 3 ) et log2 3 ' 1, 58.
3o Dans le cas d’entiers, apparaissent les retenues qui n’existaient pas au niveau des polynômes. Cela ne change
pas le nombre de multiplications élémentaires mais complique quelque peu la vie au programmeur.
Notons finalement que si on compare dans la pratique la multiplication naı̈ve des grands entiers avec la multipli-
cation de Karatsuba, le gain en complexité ne se fait sentier que pour de très grands entiers...

19. On suppose connue une fonction ppcm2 qui calcule le ppcm de 2 entiers. On veut généraliser cette fonction
au calcul du ppcm de n entiers. Proposer une solution Caml itérative et une solution Caml récursive à l’aide d’une
méthode ”diviser pour régner”. Comparer les performances des deux approches.

20. Analyse en moyenne d’un algorithme.

1o Donner un algorithme qui trouve le plus petit et le plus grand élément d’un tableau contenant n entiers
naturels en effectuant un nombre de comparaisons de l’ordre de 3n 2 (prouver votre programme et sa complexité,
bien sûr !).
Indication : considérer les éléments du tableau 2 par 2 et commencer par comparer 2 éléments successifs.
2o Un étudiant a proposé la solution suivante :
let minmax v =
let min = ref 0 and max = ref 0 in
for i=1 to vect_length(v)-1 do
if v.(i) < v.(!min) then min:= i
else if v.(i) > v.(!max) then max:=i done; (!min,!max);;
Ainsi le nombre de comparaisons effectuées pour chaque i est soit 1 soit 2. L’étudiant se demande si sa solution
bien que fausse dans le cas le pire ne serait pas correcte en moyenne.
Le but de cet exercice est de montrer qu’il n’en est rien. Pour ce faire on retient le modèle des permutations et
au lieu d’examiner les tableaux à trier on se penche sur la permutation associée, c’est à dire que l’on suppose
que l’algorithme est exécuté sur un tableau α contenant tous les entiers naturels entre 1 et n, et que toutes les
permutations de ces nombres sont équiprobables.
a. Pour toute permutation α on on appelle minimum local un entier j tel que :

∀ i ∈ [[1, j[[, α(i) > α(j)

On convient que 1 est toujours un minimum local de α. Exprimer le nombre de comparaisons effectuées par
l’algorithme précédent en fonction du nombre k de minima locaux de la permutation α.
b. On note par un,k le nombre de permutations sur n éléments qui présentent k minima locaux. Montrez que :

un,0 = 0 un,n = 1

∀ k ∈ [[1, n[[ un,k = (n − 1)un−1,k + un−1,k−1

L. Albert Exos Complexité 9

c. On considère la famille de polynômes

∞
X
Pn (x) = un,k xk
k=1

Donnez une expression de Pn (x) comme un produit de monômes du premier degré. Montrez que la dérivée
Pn0 (x) satisfait µ ¶
0 1 1 1
Pn (x) = Pn (x) + + ... +
x x+1 x+n−1
d. Donnez une expression du nombre moyen Mn de minima locaux dans les permutations sur n éléments.
e. Quel est le comportement à l’infini du nombre moyen de comparaisons dans le programme de l’étudiant ;
le comparer à 3n
2 .

Solution proposée
1o On suggère
let minmax v =
let n = vect_length v in let mini = ref v.(0) and maxi = ref v.(0) in
for i = 1 to (n/2) do
if v.(2*i) <= v.(2*i-1) then begin
if v.(2*i) < !mini then mini := v.(2*i);
if v.(2*i-1) > !maxi then maxi := v.(2*i-1)
end else begin
if v.(2*i) > !maxi then maxi := v.(2*i);
if v.(2*i-1) < !mini then mini := v.(2*i-1)
end
done;
if (n mod 2)=1 then (min !mini v.(n-1),max !maxi v.(n-1))
else (!mini, !maxi);;
On vérifie ensuite par induction sur la longueur du vecteur que cette fonction est correcte.
On effectue 3E(n/2) comparaisons plus 1 éventuellement si v est de longueur impaire.
2o a. Pour chaque i entre 1 et n-1 il y a 2 comparaisons si i n’est pas un minimum local et une seule s’il en est
un. Comme le nombre de minimum locaux de la permutation qui appartiennent à 1,2, ... n-1 est k-1 le nombre
de comparaisons effectuées par l’algorithme vaut :

2(n − 1 − (k − 1)) + k − 1 = 2n − k − 1

b. Toute permutation admet au moins un minimum local ainsi un,0 = 0. Pour qu’une permutation a1 , a2 , ...
an présente n minima locaux il faut que a1 > a2 > . . . > an il n’y en a donc qu’une seule ainsi un,n = 1.
Soit α une permutation sur n éléments qui présente k minima locaux. En supprimant n de la suite, on obtient
une permutation β sur n − 1 éléments. Celle-ci présente k − 1 minima locaux si n se trouvait en tête et k
minima sinon. Réciproquement étant donnée β il y a n − 1 façons d’insérer n autrement qu’en tête et une
seule de l’insérer en tête pour obtenir α. Ainsi :

un,k = un−1,k−1 + (n − 1)un−1,k

c. On multiplie par xk l’égalité ci-dessus et on somme ces égalités pour k = 1, 2...n, on obtient

Pn = xPn−1 + (n − 1)Pn−1 = (x + n − 1)Pn−1

Qn−1
Comme P1 = x on obtient Pn = i=0 (x + i) d’où l’expression de la dérivée.
d. Le nombre moyen Mn de minima locaux dans l’ensemble des permutations sur n éléments vaut :
n n
1 X 1 n! X 1
Mn = kun,k = Pn0 (1) =
n! n! n! k
k=1 k=1
L. Albert Exos Complexité 10

e. Le nombre moyen de comparaisons de l’algorithme proposé est ainsi de 2n − ln(n) prépondérant devant
3n/2.

21. Soit x1 , x2 , . . ., xn une suite finie de nombre entiers non tous nécessairement distincts. La ”multiplicité” d’une
valeur x dans la suite est égale au nombre de fois où x apparaı̂t dans la suite. Un entier z est dit ”valeur majoritaire”
si sa multiplicité est supérieure ou égale à n/2 + 1.
1o Montrer que si xi est différent de xj et si l’on supprime xi et xj de la suite, la valeur majoritaire de la suite
initiale, s’il en existe une, est aussi valeur majoritaire de la suite obtenue après suppression.
2o Montrer qu’en examinant successivement les éléments de la suite dans l’ordre x1 , x2 , . . ., xn , on peut ”mettre
à jour” deux variables C et M ayant la propriété suivante :
lorsque l’on considère xi , C contient une valeur qui est la seule candidate possible à être valeur majoritaire parmi
x1 , x2 , . . ., xi−1 et M contient le nombre de fois où la valeur C est apparue jusqu’alors, si l’on exclue les fois où
C a été éliminé.
3o En déduire un algorithme qui, en deux ”parcours” de la suite x1 , x2 , . . ., xn détermine si la suite possède ou
non une valeur majoritaire et donne cette valeur majoritaire quand elle existe.

Solution proposée
1o On considère une liste d’entiers L de longueur n (implémentée par exemple sous la forme d’un vecteur) qui a
(ou non) une valeur majoritaire m.
Considérons les deux premiers éléments de la liste x1 et x2 et notons L0 la liste L privée de x1 et x2 (de longueur
n − 2). Dans cette question on traite le cas où x1 6= x2 .
Si x1 et x2 sont tous les deux différents de m, on peut les supprimer de la liste : la nouvelle liste L0 a toujours m
pour valeur majoritaire (m est même encore plus majoritaire !).
Si un des deux vaut m, le nombre d’occurrences de m dans L0 a diminué de 1 mais la nouvelle longueur est n − 2
donc m est encore majoritaire dans L0 .
Conclusion : en supprimant les deux éléments de tête d’une liste dans le cas ou ceux-ci sont différents, on ne
change pas la valeur majoritaire d’une liste, si elle existe. Remarquons (en prenant par exemple la liste [1 ;2 ;3])
que cette suppression peut conduire à l’apparition d’une valeur majoritaire dans L’ (ici 3) alors qu’il n’y en avait
pas dans L.
2o C est ainsi le candidat pour être une valeur majoritaire de la liste L dont on a lu les i premiers éléments. On
initialise C et M avec x0 et 1. On procède par examen successif des éléments de la suite. Quand on considère xi
on le compare à C et on ajoute ou on enlève 1 à M selon que xi est égal ou non à C. Lorsque M devient nul c’est
qu’il n’y avait pas de valeur majoritaire dans le début de la liste et on donne alors à C la valeur xi+1 et à M la
valeur 1.
À la fin du parcours, il ne reste qu’un candidat C. On fait alors un deuxième parcours de la suite pour déterminer
son nombre d’occurrences dans L et décider si oui ou non c’est bien une valeur majoritaire.
La complexité de notre algorithme est ainsi bien linéaire.
(* valeur majoritaire *)

let x=[|1;2;5;1;3;2;4;7;6;4;2;2;0|];;

let y=[|1;2;5;2;2;2;4;2;6;4;2;2;0|];;

let candidat_val_maj x =
let C= ref x.(0) and M = ref 1 in
for i =1 to (vect_length x) -1 do
if x.(i) = !C then M:=!M+ 1
else M:= !M-1;
if !M=0 then begin C:=x.(i) ; M:=1 end
done;
!C;;

let valmaj x =
L. Albert Exos Complexité 11

let C = candidat_val_maj x in
let M = ref 0 in
for i =0 to (vect_length x) -1 do
if x.(i) = C then M:= !M+1
done;
if !M>((vect_length x) / 2) then C else -1;;

valmaj x;;

valmaj y;;

22. Décomposition en tranches d’un ensemble de points.

On considère un ensemble E fini de points du plan qui n’ont jamais ni la même abscisse ni la même ordonnée.
On ordonne cet ensemble par une relation de domination (ordre partiel) : Pour deux points P et Q du plan de
coordonnées respectives (x, y) et (x0 , y 0 ), on dit que P domine Q et on note P Â Q si x > x0 et y > y 0 . On dit qu’un
point est maximal s’il n’est dominé par aucun point.
On considère une partition de E en des sous-ensembles T1 , T2 , . . . , Tk telle que :
– T1 est est l’ensemble des points maximaux de E,
– pour i > 1, Ti est l’ensemble des points maximaux de E \ {T1 , T2 , . . . , Ti−1 }.
On appelera une telle partition une décomposition en tranche.
On appelera pivot d’une tranche Ti , le point de Ti , dont l’abscisse est la plus petite.
1o Montrer que le pivot d’une tranche est aussi son point d’ordonnée la plus grande.
2o Soient y1 , y2 , . . . , yk les ordonnées des pivots des tranches T1 , T2 , . . . , Tk respectivement. Montrer que :

y1 > y2 > . . . > yk−1 > yk

Soit E un ensemble de points dont on a calculé la décomposition en tranches E = T1 ∪ T2 ∪ . . . ∪ Tk dont les pivots
ont pour ordonnées y1 , y2 , . . . , yk . Soit Q = (x, y) un point du plan dont l’abscisse est strictement plus petite que
les abscisses de tous les points de E et dont l’ordonnée n’est égale à aucune des ordonnées des points de E.
3o Montrez que si y > y1 alors Q est un point maximal de E 0 = E ∪ {Q}. Montrez qu’il existe un point de Tj qui
domine Q si et seulement si y < yj .
4o Dans quel cas E 0 a-t-il une tranche de plus que E ?
5o En déduire un algorithme qui détermine la décomposition en tranches de E 0 connaissant celle de E et les
ordonnées des pivots de E.
6o Comment réaliser alors la décomposition en tranches d’un ensemble E donné ?

23. Les deux points les plus proches

Le but de ce problème est d’identifier dans un ensemble de points quel est le couple de points les plus proches au
sens de la distance euclidienne. Ce type d’algorithme voit son utilité dans les transports aériens ou maritimes.
L’ensemble de points est vu comme un vecteur T de points de taille N. Un point T.(i) est identifié par ses coordonnées
dans le plan : fst T.(i) l’abscisse et snd T.(I) l’ordonnée.
Nous disposons d’une fonction sqrt(a) qui renvoie la racine carrée de a (a ** 0.5).
1o Donner un algorithme itératif qui détermine le couple de points les plus proches de l’ensemble T[0 ... N-1].
Prouver votre algorithme.
Évaluer le nombre d’additions, de multiplications et d’appels de la fonction sqrt.
L’ensemble de points est doorénavant stocké dans deux vecteurs de taille N : X où les points sont ordonnés suivant
les abscisses croissantes et Y où les points sont ordonnés suivant les ordonnées croissantes.
L. Albert Exos Complexité 12

2o Écrire une fonction decoupe X Y Yp deb fin qui place dans Yp[deb...med] les points de X[deb...med] classés
par ordonnées croissantes et dans Yp[med + 1...fin] les points de X[med + 1... fin] classés par ordonnées croissantes,
deb + f in
où med est la partie entière de . On a donc coupé suivant les abcisses notre ensemble de points en deux
2
moitiés où les points sont rangés suivant leur ordonnée.
Évaluer le nombre de transferts effectués lors de l’utilisation de cette fonction (il doit être linéaire !).
3o On suppose que A et B sont les points les plus proche de X[deb...med] et, C et D sont les points les plus
proches de X[med + 1 ... fin].
Ecrire un algorithme linéaire qui détermine les deux points les plus proches de l’ensemble X [deb ... fin] connaissant
A, B, C, D et Y[deb ... fin]. (on montrera que l’on peut se limiter à considérer les points d’une bande médiane,
où chaque point est considéré avec au plus 7 autres points de la bande).
4o En déduire une fonction cherche récursive qui répond à notre problème avec une complexité Θ(n ln n).

24. On considère le ”jeu des chiffres” dans lequel on donne une suite w[1], w[2], .... w[n] de
P n nombres entiers (int
de Caml) et un nombre s. On demande de trouver un sous-ensemble I des indices tel que i∈I w[i] = s.
Donner un algorithme résolvant ce problème. Quelle est sa complexité ?

Indications
Proposer une solution récursive utilisant le fait qu’un algorithme A(s, k) (qui résout le problème de somme s en
utilisant w[k], ..., w[n]) vérifie A(s, k) = A(s, k + 1) ou A(s − w[k], k + 1) suivant que dans la solution on utilise ou
non w[k].

Solution proposée
let w=[|2;4;8;12;25;7|];;

let rec chiffre s k w n=

if s=0 then true
else if (s<0) || (k>=n) then false
else if chiffre (s-w.(k)) (k+1) w n then begin print_int w.(k); true end
else chiffre s (k+1) w n;;

let jeu s w = chiffre s 0 w (vect_length w);;

Le cas le pire est obtenu lorsqu’il n’y a pas de solution ce qui entraine que tout l’arbre des possibilités est parcouru (rq. :
une branche de l’arbre conduit à une partie de w). Dans le programme ci-avant, chiffre (s-w.(k)) (k+1) w n re-
tourne false et on évalue forcément chiffre s (k+1) w n. Ainsi, en notant ck le nombre d’appels à chiffre s k w n,
on a :
ck 6 2ck+1 et cn = 1
D’où ck 6 2n−k et la complexité exponentielle dans le cas le pire attendue.
Voici une version plus claire pour utiliser trace sur chiffre.
let rec chiffre (s,l) =
try
if s=0 then true
else if (s<0) then false
else if chiffre ((s-(hd l)) , (tl l)) then begin print_int (hd l); true end
else chiffre (s,(tl l))
with Failure "tl" -> false;;

let jeu s l = chiffre (s,l);;

L. Albert Exos Complexité 13

25. À chaque exécution de la procédure Hanoı̈ on associe une chaı̂ne de caractères de la façon suivante :
– Un déplacement d’une rondelle du piquet 1 vers le piquet 3 est noté par le symbole a,
– du piquet 1 vers le piquet 2 par le symbole b
– et du piquet 2 vers le piquet 3 par c.
Les déplacements inverses sont notés par les mêmes lettres avec une barre dessus (ā, b̄, c̄). Ainsi la chaı̂ne de caractères
correspondant au déplacement de deux rondelles du piquet 1 vers le piquet 3 selon l’algorithme décrit en cours est :
h2 = bac. Celle correspondant au déplacement de trois rondelles du piquet 1 vers le piquet 3 est :

h3 = abc̄ab̄ca

1o Donner la chaı̂ne correspondant au déplacement de 4 rondelles.

2o Quelle est la longueur de la chaı̂ne h, correspondant au déplacement de n rondelles ?
3o En s’aidant des transformations suivantes sur les caractères donnez un procédé de calcul de la chaı̂ne hn+1 en
connaissant hn :
a b c ā b̄ c̄
Φ b a c̄ b̄ ā c
Ψ c b̄ a c̄ b ā

4o Montrez que lorsque l’on supprime les barres au dessus des caractères intervenant dans la chaı̂ne hn on obtient
une chaı̂ne très régulière.
5o En déduire une procédure itérative permettant de résoudre le problème des tours de Hanoı̈.

26. Soit P un polygône à n sommets notés dans l’ordre Ai , i = 0 . . . n − 1, leurs coordonnées étant (xi , yi ) (les
indices se comprennent modulo n).
Pn−1
On note p = i=1 d(Ai−1 , Ai ) le périmètre de P . Le but est de déterminer le couple (Ai0 , Aj0 ) découpant P en deux
parties de longueurs les plus semblables possibles. Ce couple est réalisé par :
¯ ¯
¯j−1 i+n−1 ¯
¯X X ¯
inf ¯¯ d(Ak , Ak+1 ) − d(Ak , Ak+1 )¯¯
(i,j) ¯ ¯
k=i k=j

On suppose donnés n: int et P : (int * int) vect tel que P.(i) contienne les coordonnées de Ai .
1o La force brute.
a. Écrire une fonction dist_plus renvoyant
j−1
X
dist plus(i, j) = d(Ak , Ak+1 )
k=i

et dist_moins renvoyant
i+n−1
X
dist moins(i, j) = d(Ak , Ak+1 )
k=j

en convenant que dist plus(Ai , Ai ) = 0.0 et dist moins(Ai , Ai ) = p.

b. Écrire un programme utilisant les fonctions précédentes et renvoyant une matrice M = [Mi,j ] de taille n × n
avec ¯ ¯
¯j−1 i+n−1 ¯
¯X X ¯
Mi,j = ¯¯ d(Ak , Ak+1 ) − d(Ak , Ak+1 )¯¯
¯ k=i k=j ¯

et conclure à un algorithme permettant de trouver la paire (i0 , j0 ). Quelle est l’ordre de grandeur de sa
complexité (en appels à d) ?
2o Amélioration de l’algorithme.
L. Albert Exos Complexité 14

a. Écrire une fonction qui à i donné renvoit Opposé(i), ce dernier étant le plus grand j > i tel que
j−1
X p
d(Ak , Ak+1 ) 6
2
k=i

Écrire un programme renvoyant un vecteur J et un vecteur D tel que J.(i) = Opposé(i) mod n et D.(i) =
d(Ai , AOpposé(i) ).
Quelle est sa complexité ? Peut-on s’arranger pour avoir une complexité en O(n) ? (remarquer que Opposé(i
+ 1) succède à Opposé(i) mod n).
b. Montrer que j0 = J.(i0 ) ou (J.(i0 ) + 1) mod n. Conclure à un nouvel algorithme permettant de trouver
(i0 , j0 ). Quelle est sa complexité ?

Solution proposée

(* COUPER LA POIRE EN DEUX *)

let n=6;;
let P=[|0.,2.; 0.,0.; 3.,1. ; 4.,3.; 4.,4. ; 2.,5.|];;

let ind i = i mod n;;

let point i = P.(ind i);;
let norme (x,y) = (sqrt ((x *. x) +. (y *. y)));;

let dist_suiv i =
let (x,y) = (point i) and (u,v) = (point (i+1)) in
norme ((x -. u),(y -. v));;

let distance i j =
let d = ref 0.0 in
if (i >= j) then 0.0 else
( for k = i to j-1 do d:= !d +. (dist_suiv k);done; !d; );;

let dist_plus i j =
if (j < i) then (distance i (j+n)) else (distance i j);;

let dist_moins i j = if (i <= j)

then (distance j (i+n)) else (distance j i);;

let M =
let m = (make_matrix n n 0.0) in
for i = 0 to (n-1) do
for j = 0 to (n-1) do
m.(i).(j) <- abs_float ((dist_plus i j) -. (dist_moins i j)); done; done;
m;;

let (i0,j0) =
let point = ref (1,1) and d = ref (dist_moins 1 1) (* soit p *) in
for i = 0 to (n-1) do
for j = i to (n-1) do
if (M.(i).(j) <. !d) then (d:=M.(i).(j); point:=(i,j))
done; done;
!point;;

(* calcul de p *)
let p = let d = ref 0.0 in for i = 0 to (n-1) do d:= !d +. (dist_suiv i);done; !d;;
L. Albert Exos Complexité 15

let oppose i =
let j = ref i and d = ref 0.0 and psur2 = (p /. 2.0) in while (!d <=. psur2) do
(d:= !d+.(dist_suiv !j);
j:= !j+1;) done; (* j vaut oppose(i) +1 *)
(!j - 1) mod n;;

(* calcul de D et J *)

let D = make_vect n 0.0 and J = make_vect n 0;;

let psur2 = (p /. 2.0) in

while ((D.(0) +. (dist_suiv J.(0)))<=. psur2) do
D.(0) <- D.(0) +. (dist_suiv J.(0));
J.(0) <- (J.(0)+1) mod n;done; (* J.(0) est calcul’e *)

for i = 1 to n-1 do
D.(i) <- D.(i-1) -. (dist_suiv (i-1));
J.(i) <- J.(i-1);
while ((D.(i) +. (dist_suiv J.(i)))<=. psur2) do
D.(i) <- D.(i) +. (dist_suiv J.(i));
J.(i) <- (J.(i)+1) mod n;done; (* J.(i) est calcul’e *)
done;;

D;;J;;

let res = ref (0,0) and d = ref p;;

(* choix de i0 et j0 *)
for i = 0 to n-1 do
let dd = (p -. 2.0*.D.(i)) in
( if (dd <. !d) then
(res := (i,J.(i)); d:= dd;);
if ((2.0 *. (dist_suiv J.(i)) -. dd) <. !d) then
(res := (i,(J.(i) +1) mod n); d := dd;); );
done;;

res;;

27. On peut programmer le tri fusion avec un nombre de comparaison qui vérifie la relation
CN = Cbn/2c + Cdn/2e + N
PN −1
A partir d’un calcul de CN +1 − CN , Montrer que CN = k=0 (bln2 k + 2c)
En déduire que CN = N dln2 N e + N − 2dln2 N e

28. Le tri des mécanographes.

Le but de cet exercice est d’implémenter en Caml l’algorithme des mécanographes pour trier les cartes perforées.
Une carte perforée est représentée par un mot de N lettres. Les lettres sont prises dans un alphabet de cardinal p.
L’ordre choisi est l’ordre lexicographique.
Soit S la séquence (de longueur n) des mots à trier suivant l’ordre croissant. L’algorithme consiste à effectuer sur
S successivement N tris partiels ; plus précisément à chaque étape on ne trie les mots que suivant leur i-ième lettre
sans modifier l’ordre relatif dans S des mots ayant la même i-ième lettre.
Prenons un exemple avec p = 3, N = 3 et la suite initiale S0 de 6 mots suivants : 112, 321, 113, 232, 233, 312.
L’algorithme procède comme suit :
– on emploie trois corbeilles auxiliaires (une par lettre de l’alphabet) initialement vides P1 , P2 , P3 ,
L. Albert Exos Complexité 16

– on place tour à tour chacun des 6 mots dans la corbeille correspondant à sa dernière lettre ; cela donne : P1 = {321},
P2 = {112, 232, 312} et P3 = {113, 233}.
On récupère ensuite, dans cet ordre, les mots et la nouvelle suite S1 de mots à traiter est ainsi : 321, 112, 232,
312,113, 233.
– on place ensuite chacun des 6 mots dans la corbeille suivant sa deuxième lettre ; cela donne : P1 = {112, 312, 113},
P2 = {321} et P3 = {232, 233} (l’ordre relatif dans S1 de deux mots ayant la même deuxième lettre n’a pas été
modidié).
La nouvelle suite S2 de mots à traiter est cette fois : 112, 312, 113, 321, 232, 233.
– Enfin on itère le procédé sur la première lettre ; on a : P1 = {112, 113}, P2 = {232, 233} et P3 = {312, 321}.
Et la suite finale triée est bien : 112, 113, 232, 233, 312, 321.
1o Justifier la validité de l’algorithme.
2o Proposez des structures de données ad hoc pour traiter le problème.
3o Donner une version Caml de l’algorithme (on pourra utiliser le type prédéfini queue).
4o Quel est sa complexité en fonction de N et n ? Ce résultat vous surprend-il ?

Solution proposée
1o On peut faire une récurrence sur N :
– Pour des mots d’une lettre, l’algorithme effectue un tri en une itération.
– On suppose qu’après la i-ième étape les mots sont correctement triés dans la suite Si suivant leurs i dernières
lettres. La (i+1)-ième étape classe alors les mots suivant la lettre suivante (la (N-i)-ième) et, puisqu’en cas
d’égalité elle ne modifie pas l’ordre des mots de Si , les mots sont correctement rangés suivant leur (i+1)
dernières lettres dans Si+1 .
2o On choisit par commodité de représenter chaque mot par un vecteur d’entiers. L’algorithme nécessite de
connaitre toute la suite de mots dès le départ : on choisit également une structure vectorielle pour S. Chaque
corbeille doit recevoir les mots en conservant leur ordre d’arrivée : on choisit donc une structure FIFO, les files
(queue en Caml).
3o Voici une solution Caml :
let L= [| [|1;1;2|] ; [| 3; 2; 1|] ; [|1;1;3|] ; [|2;3;2|] ; [|2;3;3|] ; [|3;1;2|] |];;

let N=3;;

#open "queue";;

let p1 = new ()
and p2 = new ()
and p3 = new ();;
(* les files de rangements *)

let ajoute i e =
match e.(i) with
| 1 -> add e p1
| 2 -> add e p2
| _ -> add e p3 ;;

let rec tri_indice i v =

for j= 0 to ((vect_length v) -1) do
ajoute i v.(j) done;;

let merge v =
L. Albert Exos Complexité 17

let lp1 = length p1 and lp2 = length p2 and lp3 = length p3 in

for i =0 to (lp1-1) do
v.(i) <- take p1 done;
for i=lp1 to (lp1 + lp2 -1) do
v.(i) <- take p2 done;
for i = (lp1 + lp2) to (lp1 + lp2 +lp3 -1) do
v.(i) <- take p3 done;;

let tri_mecano v =
for i=(N-1) downto 0 do
tri_indice i v; merge v
done; v;;
4o On a vu dans le cours que la complexité optimale en moyenne et dans le cas le pire d’un tri par comparaisons
d’une suite de n mots est en n log n. Ici l’exécution d’une passe de tri a un coût linéaire en n et l’on effectue N
itérations soit un coût total en nN . Ceci n’a rien de surprenant :
– d’une part on sait que si les données à trier ne sont pas quelconques (par exemple évoluant dans un ensemble
de cardinal fini connu d’avance), on peut les trier avec un coût linéaire en temps (mais linéaire en espace
également),
– d’autre part l’ordre lexicographique à ceci de particulier qu’il ne nécessite pas la connaissance de toutes les
lettres pour comparer deux mots.

29. Le tri selon les Pieds Nickelés.

Les célèbres professeurs Croquignol, Filochard et Ribouldingue ont inventé une toute nouvelle technique de tri, qu’ils
ont (subtilement) baptisée méthode CFR.
En voici une mise en œuvre en Caml :

let \’{e}change u i j = let x = u.(i) in u.(i)<-u.(j);u.(j)<-x;;

let CFR t =
let rec CFR_aux u i j =
if i=j then () else
if i+1=j then begin if u.(i)>u.(j) then \’{e}change u i j end else
let k=(j+1-i)/3 in
CFR_aux u i (j-k); CFR_aux u (i+k) j; CFR_aux u i (j-k)
in CFR_aux t 0 (vect_length t - 1);;

1o Montrer que le programme précédent est correct, id est : il trie bien le tableau transmis en argument, dans
l’ordre croissant de ses valeurs.
On se propose d’analyser cette méthode. Soit Cn le coût maximal exprimé en nombre de comparaisons d’éléments
du tableau, lorsque la taille de celui-ci est n.
2o Écrire des relations qui permettent de calculer, de proche en proche, les valeurs de Cn .
3o Compléter le tableau suivant des premières valeurs de Cn :
n 1 2 3 4 5 6 7 8 9 10
Cn 0 1 3 9 27 ? ? ? 81 243
4o Montrer qu’à partir d’un rang n0 que l’on précisera, on a Cn > n2 .
5o A-t-on ∀ n > 1, Cn 6 n3 ?
6o Justifier : il n’existe aucun exposant α tel que Cn soit équivalent à nα lorsque n tend vers l’infini.
L. Albert Exos Complexité 18

7o (difficile) exhiber un exposant β tel que Cn = o(nγ ) pour tout γ > β, et nγ = o(Cn ) pour tout γ < β.

Solution proposée
Le tri selon les Pieds Nickelés.
1o La fonction trie en place les deux premiers tiers du vecteur, puis les deux derniers et recommence le tri des
deux premiers tiers.
Prouvons sa validité par récurrence sur j − i > 1 : pour j − i = 1 et j − i = 2, c’est clair. Sinon, supposons la
fonction correcte pour j − i 6 n et prouvons qu’elle l’est encore pour j − i = n + 1. Notons k la partie entière de
n/3 ; on a 3k 6 n, donc n − 2k > k. Après le premier appel récursif, les k plus grand éléments sont dans t[i + k..j] ;
après le deuxième appel, ils sont à leur place dans t[j − k + 1..j]. Enfin, le troisième appel trie t[i..j − k].
2o C1 = 0, C2 = 1 et Cn = 3Cn−bn/3c pour n > 2.
3o À l’aide de la fonction Maple suivante (dopée par l’option remember) :
c := proc(n) option remember; 3*c(n-iquo(n,3)) end;
c(1) := 0; c(2) := 1;
on a déterminé les résultats :
n 1 2 3 4 5 6 7 8 9 10
Cn 0 1 3 9 27 27 81 81 81 243
4o En fait, Maple permet de constater que les seules valeurs de n 6 1000 telles que Cn < n2 sont 1, 2, 3, 4 et 6.
Soit p > 3 tel que Cn > n2 pour tout n ∈ [[2p, 3p − 1]]. Alors :

C3p = 3C2p > 12p2 > (3p)2

C3p+1 = 3C2p+1 > 3(2p + 1)2 = 12p2 + 12p + 3
> 9p2 + 6p + 1 = (3p + 1)2
C3p+2 = 3C2p+2 > 3(2p + 2)2 = 12p2 + 24p + 12
> 9p2 + 12p + 4 = (3p + 2)2
Donc Cn > n2 pour n ∈ [[2p, 3p + 2]], et à plus forte raison pour n ∈ [[2p + 2, 3p + 2]] = [[2(p + 1), 3(p + 1) − 1]].
Comme Cn > n2 pour n ∈ [[8, 11]] = [[2 × 4, 3 × 4 − 1]], on peut affirmer que Cn > n2 pour tout n > 8, et du coup
pour tout n > 7.
5o Oui ! (j’attends vos rédactions subtiles !).
6o On établit aisément par récurrence que Cn+1 est égal à Cn ou à 3Cn (ce qui nous assure que la suite est
croissante). Il existe une infinité d’indices n tels que Cn+1 = 3Cn (sinon la suite serait stationnaire, contredisant
sa minoration par n2 ). Ainsi, de la suite de terme général CCn+1 n
, on peut extraire une suite qui converge vers 3,
interdisant à Cn d’être équivalent à nα . Notons qu’il existe aussi une infinité d’indices n tels que Cn+1 = Cn (ne
serait-ce que n = 3p + 2).
7o Idée : si Cn était du même ordre de grandeur que nα , en faisant n = 3p on trouverait (3p)α du même ordre
que 3(2p)α , imposant 3α = 3 · 2α , soit α = lnln3/2 3
≈ 2.71 ; nous allons établir en toute rigueur que ln(Cn ) est
équivalent à α ln n lorsque n tend vers l’infini.
Un palier de la suite est un intervalle [[p, q −1]] sur lequel elle est constante, et maximal vis-à-vis de cette propriété.
Notons xn l’indice de début du nième palier : x1 = 1, x2 = 2, x3 = 3, x4 = 4, x5 = 5, x6 = 7, x7 = 10 et x8 = 14.
C C
Soient p = xn et q = xn+1 ; on a Cp = Cp+1 = · · · = Cq−1 = 3q , et Cp−1 = 3p . Distinguons deux cas selon la parité
0 0
de p : si p = 2p , alors C3p0 = 3C2p0 = 3Cp = Cq donc q 6 3p ; C3p0 −1 = C3(p0 −1)+2 = 3C2(p0 −1)+2 = 3C2p0 = 3Cp ,
donc q 6 3p0 − 1 ; C3p0 −2 = C3(p0 −1)+1 = 3C2(p0 −1)+1 = 3C2p0 −1 = 3Cp−1 = Cp , donc q = 3p0 − 1. Une discussion
analogue donne q = 3p0 + 1 si p = 2p0 + 1.
Dans les deux cas, on obtient q = p + b(p − 1)/2c = b(3p − 1)/2c ; ainsi xn+1 = b(3xn − 1)/2c pour n > 3. On en
déduit l’encadrement

3(xn − 1) 3xn − 1
< xn+1 6
2 2
3
On en déduit la majoration xn+1 − 1 6 2 (xn − 1) d’où
µ ¶n−3
3 3n−3 3n−3
xn − 1 6 (x3 − 1) = n−4 soit xn 6 1 + n−4
2 2 2
L. Albert Exos Complexité 19

De même, on a la minoration xn+1 − 2 > 32 (xn − 2), dont on déduit

µ ¶n−3 µ ¶n−3
3 3 3n−3
xn − 2 > (x3 − 2) = soit xn > 2 +
2 2 2n−3
On écrit l’encadrement :
µ ¶n µ ¶ µ ¶n µ ¶
3 8 2n−1 3 16 2n
+ n < xn 6 + n
2 27 3 2 27 3
dont on déduit, par passage au logarithme, que ln Cn est équivalent à n ln 32 . Or, pour n > 2, on a Cp = 3n−2
pour tout xn 6 p < xn+1 , soit ln xn 6 ln p < ln xn+1 . On en déduit que ln p est lui aussi équivalent à n ln 32 . Mais
ln Cp = (n − 2) ln 3 est équivalent à n ln 3. Finalement, ln Cp est équivalent à lnln3/2
3
ln p = α ln p. Le résultat de
l’énoncé s’en déduit sans peine.

30. Tri par distribution

Le tri par distribution sert à trier une suite (a1 , . . . , an ) d’entiers, lorsque l’on sait que 0 6 ai 6 m − 1 pour un entier
m ”petit”. Le principe est le suivant : on détermine le nombre d’éléments inférieurs à chaque valeur j par :

cj = #{i | ai 6 j} 06j 6m−1

puis, dans une deuxième passe, on s’en sert pour calculer la place finale de ai par :

si = cai − #{k > i | ak = ai }

La suite triée est (b1 , . . . , bn ) avec bk = ai si et seulement si k = si .

1o Écrire une fonction distribution a n m qui réalise ce tri. On peut utiliser un vecteur temporaire c pour
calculer les cj et un tableau b pour ranger la suite triée.
2o Donner le temps de calcul de votre algorithme en fonction de n et de m, ainsi que l’espace mémoire nécessaire.

Indications

let m = 6;;
(* les entiers \‘{a} trier sont < 6 *)

let distribution a =
let n = vect_length a in
let b = make_vect n 0 in
let c = make_vect m 0 in
for i=0 to (n-1) do c.(a.(i)) <- c.(a.(i)) + 1 done;
for j=1 to m-1 do c.(j) <- c.(j-1) + c.(j) done;
for i=(n-1) downto 0 do
b.(c.(a.(i))-1) <- a.(i);
c.(a.(i)) <- c.(a.(i)) -1
done;
b;;

31. Quelques compléments sur la fonction d’Ackermann (voir le polycop de cours pour sa définition).
Par commodité d’écriture nous noterons A(n, p) pour ackermann n p.
1o Donner les expressions explicites de A(1, p), A(2, p) et A(3, p).
2o Que vaut A(4, 4) ? Comparer cet entier avec 1080 (qui est une estimation du nombre d’atomes de l’univers !).
L. Albert Exos Complexité 20

3o Montrer que ∀ (n, p) ∈ N2 , A(n, p) > p.

4o Montrer que si q > p, alors ∀ n ∈ N, A(n, q) > A(n, p).
5o Montrer que A(n + 1, p) > A(n, p) pour tout couple (n, p) ∈ N2 .
6o On définit la fonction α de N dans N comme l’inverse fonctionnel de A : α(n) est le plus petit entier k tel que
A(k, k) > n. Montrer que la fonction α est bien définie sur N.
Que peut-on dire de la croissance de α ?

Solution proposée
La fonction d’Ackermann.
1o Calcul de A(1, p).
On a A(1, 0) = A(0, 1) = 2 et A(1, p + 1) = A(0, A(1, p)) = A(1, p) + 1 donc par récurrence A(1, p) = p + 2.
Calcul de A(2, p).
On a A(2, 0) = A(1, 1) = 3 et A(2, p + 1) = A(1, A(2, p)) = A(2, p) + 2 donc par récurrence A(2, p) = 2p + 3.
Calcul de A(3, p).
On a A(3, 0) = A(2, 1) = 5 et A(3, p + 1) = A(2, A(3, p)) = 2A(3, p) + 3 donc par récurrence A(3, p) = 2p+3 − 3.
2o On a A(4, 4) = 2A(4,3)+3 − 3 > 2A(4,3) d’où, comme A(4, 0) = 13 > 2, on a :
à ³ ¡ ¢´!
22
2
2
A(4, 4) À 2 = 265536 À 1080 !
ó¡ ¢´!
213
2
2
Exactement, A(4, 4) = 2 − 3.
3o On va montrer le résultat par induction dans (N2 , 4) suivant le théorème de correction. Soit pA le prédicat
défini pour tout (n, p) ∈ N2 par : pA (n, p) = ”A(n, p) > p”.
- Si n = 0, alors A(0, p) = p + 1 > p, soit pA (0, p).
- Par définition, A(n, 0) = A(n − 1, 1). Par hypothèse d’induction, on a A(n − 1, 1) > 1 donc on a bien A(n, 0) =
A(n − 1, 1) > 1 > 0.
- Par définition, A(n, p) = A(n−1, A(n, p)). Par hypothèse d’induction, A(n, p−1) > p−1 et A(n−1, A(n, p−1)) >
A(n, p − 1) donc A(n, p) = A(n − 1, A(n, p − 1)) > A(n, p − 1) > p − 1 d’où A(n, p) > p (on travaille dans N !).
On a donc bien montré pA pour tout (n, p) ∈ N2 .
4o Il suffit de montrer que ∀ (n, p) ∈ N2 , A(n, p + 1) > A(n, p). C’est clair si n = 0. Soit n ∈ N∗ , on a, pour tout
p, d’après la question précédente, A(n, p + 1) = A(n − 1, A(n, p)) > A(n, p) soit le résultat.
5o On va montrer le résultat à nouveau par induction. Soit pA le prédicat défini pour tout (n, p) ∈ N2 par :
pA (n, p) = ”A(n + 1, p) > A(n, p)”.
- Si n = 0, alors A(1, p) = p + 2 > A(0, p) = p + 1.
- Par définition, A(n + 1, 0) = A(n, 1). Par hypothèse d’induction, A(n, 1) > A(n − 1, 1) d’où A(n + 1, 0) =
A(n, 1) > A(n, 0) = A(n − 1, 1).
- Par définition, A(n, p) = A(n − 1, A(n, p)). Par hypothèse d’induction, A(n + 1, p − 1) > A(n, p − 1) d’où, d’après
la question précédente, A(n − 1, A(n + 1, p − 1)) > A(n − 1, A(n, p − 1)). Et, par induction on peut supposer
A(n, A(n + 1, p − 1)) > A(n − 1, A(n + 1, p − 1)) et on en déduit bien

A(n + 1, p) = A(n, A(n + 1, p − 1)) > A(n − 1, A(n, p − 1)) = A(n, p)

On a donc bien montré pA (n, p) pour tout (n, p) ∈ N2 .

L. Albert Exos Complexité 21

6o Pour vérifier la définition de α, il suffit de montrer que la suite (A(n, n))n∈N tend vers +∞. On a A(0, 0) = 1,
A(1, 1) = 3, A(2, 2) = 7, A(3, 3) = 61 et A(4, 4) = ... Pour n > 3, en utilisant les questions précédentes,
A(n + 1, n + 1) = A(n, A(n + 1, n)) > A(n + 1, n) > A(n, n), d’où la stricte croissance de la suite et le résultat
s’en déduit.
La fonction α est évidemment une fonction à la croissance très lente. Elle intervient notamment dans le calcul
de la complexité du problème Set-Union-Find (union et recherche dans les ensembles). On connaı̂t en effet un
algorithme d’union d’ensembles 3 ”quasi-linéaire” (de complexité O(n α(n))).
On pourra se reporter au problème de Mathématiques appliquées et Algorithmique posé en 1995 à l’ENS de Lyon
(attention, pour simplifier les calculs, l’auteur a choisi une définition de Ackermann légèrement différente de la
définition usuelle).

z| }|
{z }{

3 On emploie aussi le vocabulaire de ”fusion de classes d’équivalence”.