TD d’algorithmique avanc´ee
Corrig´e du TD 4 : recherche de l’´el´ement majoritaire
Jean-Michel Dischler et Fr´ed´eric Vivien
Nous nous int´eressons `a un tableau A de n ´el´ements, n ´etant suppos´e ˆetre une puissance de deux. Nous
supposons ´egalement que la seule op´eration `a notre disposition nous permet de v´erifier si deux ´el´ements sont
ou non ´egaux. Un ´el´ement x de A est dit majoritaire si et seulement si A contient strictement plus de n/2
occurrences de x. Nous nous int´eresserons `a la complexit´e au pire.
Algorithme na¨ıf
1. ´Ecrivez un algorithme qui calcule le nombre d’occurrences d’une valeur x pr´esentes entre les indices i
et j d’un tableau A.
Occurrences(x, A, i, j)
compteur ← 0
pour k ← i `a j faire
si A[k] = x alors compteur ← compteur + 1
renvoyer compteur
2. Quelle est la complexit´e de cet algorithme ?
La boucle ex´ecute j − i + 1 it´erations. La complexit´e de cet algorithme est donc en Θ(j − i).
3. Au moyen de l’algorithme pr´ec´edent, ´ecrivez un algorithme Majoritaire qui v´erifie si un tableau A
contient un ´el´ement majoritaire.
Majoritaire(A)
pour i ← 1 `a longueur (A)/2 faire
si Occurrences(A[i], A, i, longueur (A)) > longueur (A)/2 alors renvoyer Vrai
renvoyer Faux
4. Quelle est la complexit´e de cet algorithme ?
Dans le pire cas, la boucle effectue n/2 it´erations, chacune de ces it´erations effectuant un appel `a
Occurrences sur un tableau de taille n − i (i variant de 1 `a n) donc de coˆut Θ(n − i). Le coˆut total
de l’algorithme est donc en Θ(n2).
Premier algorithme « diviser pour r´egner »
1. Proposez un algorithme Majoritaire construit suivant le paradigme « diviser pour r´egner ». Cet
algorithme divisera en deux le tableau A sur lequel il travaille. Il renverra le couple (Vrai, x) si le
tableau A contient un ´el´ement majoritaire (x ´etant cet ´el´ement) et renverra le couple (Faux, 0) si le
tableau A ne contient pas d’´el´ement majoritaire.
Majoritaire(A, i, j)
si i = j alors renvoyer (Vrai, A[i])
(rx, x) ← Majoritaire(A, i, i+j−1
)
2
(ry, y) ← Majoritaire(A, i+j+1
, j)
si rx = Faux et ry = Faux alors renvoyer (Faux, 0)
2
1
si rx = Vrai et ry = Vrai
alors si x = y
alors renvoyer (Vrai, x)
sinon
cx ← Occurrences(x, A, i, j)
Publicité
cy ← Occurrences(y, A, i, j)
si cx > j−i+1
2
alors renvoyer (Vrai, x)
sinon si cy > j−i+1
2
alors renvoyer (Vrai, y)
sinon renvoyer (Faux, 0)
sinon si rx = Vrai
alors si Occurrences(x, A, i, j) > j−i+1
alors renvoyer (Vrai, x)
sinon renvoyer (Faux, 0)
sinon si Occurrences(y, A, i, j) > j−i+1
2
2
alors renvoyer (Vrai, y)
sinon renvoyer (Faux, 0)
Justifications
Les deux seuls cas qui ne sont peut-ˆetre pas imm´ediats sont les suivants :
(a) rx = Faux et ry = Faux : dans ce cas il n’y a pas d’´el´ement qui soit majoritaire dans la premi`ere
moiti´e du tableau, ni d’´el´ement qui soit majoritaire dans la deuxi`eme moiti´e du tableau. Si le table
contient n ´el´ements, le nombre d’occurrences d’un ´el´ement quelconque dans la premi`ere moiti´e
du tableau est donc inf´erieur ou ´egal `a
2 ´el´ements— et il en va
de mˆeme pour le deuxi`eme moiti´e. Donc le nombre d’occurences d’un ´el´ement quelconque dans le
tableau est inf´erieur `a n
2 et le tableau ne contient pas d’´el´ement majoritaire.
2 —la premi`ere moiti´e ayant n
n
2
(b) rx = Vrai et ry = Vrai avec x = y : dans ce cas x est pr´esent au moins 1 + n
4 fois dans chacune
2 — et donc au moins 2 + n
2 fois dans le tableau.
des deux parties —qui sont de taille n
2. Quelle est la complexit´e de cet algorithme ?
La complexit´e de cet algorithme est d´efinie par la relation de r´ecurrence :
T (n) = 2T (cid:16)
n
2 (cid:17) + Θ(n).
En effet, la phase de combinaison n´ecessite, dans le pire des cas, la recherche du nombre d’occurences
de deux ´el´ements dans le tableau, ce qui a un coˆut de n, toutes les autres op´erations ´etant de coˆut
constant (Θ(1)).
Nous avons donc ici : a = 2, b = 2 et f (n) = Θ(n) == Θ(nlog2 2). Nous sommes donc dans le cas 2 du
th´eor`eme et donc :
T (n) = Θ(n log n).
Deuxi`eme algorithme « diviser pour r´egner »
Publicité
1. ´Ecrivez un algorithme construit suivant le paradigme « diviser pour r´egner », prenant en entr´ee un
tableau A —qu’il divisera en deux— et poss´edant la propri´et´e suivante :
– soit cet algorithme nous garantit que le tableau A ne contient pas d’´el´ement majoritaire ;
– soit cet algorithme nous renvoie un ´el´ement x et un entier cx > n/2 tels que x apparaisse au plus cx
fois dans A et que tout autre ´el´ement de A apparaisse au plus n − cx fois dans A.
PseudoMajoritaire(A, i, j)
si i = j alors renvoyer (Vrai, A[i], 1)
2
(rx, x, cx) ← Majoritaire(A, i, i+j−1
)
2
(ry, y, cy) ← Majoritaire(A, i+j+1
, j)
si rx = Faux et ry = Faux alors renvoyer (Faux, 0, 0)
si rx = Vrai et ry = Faux alors renvoyer (Vrai, x, cx + j−i+1
si rx = Faux et ry = Vrai alors renvoyer (Vrai, y, cy + j−i+1
si rx = Vrai et ry = Vrai
4
2
4
)
)
alors si x = y
alors renvoyer (Vrai, x, cx + cy)
sinon si cx = cy
alors renvoyer (Faux, 0, 0)
sinon si cx > cy
alors renvoyer (Vrai, x, j−i+1
sinon renvoyer (Vrai, y, j−i+1
2 + cx − cy)
2 + cy − cx)
Justifications
Nous consid´erons un par un les diff´erents cas de figure :
– rx = Faux et ry = Faux. Aucun ´el´ement n’apparaˆıt strictement plus de n
(resp. la deuxi`eme) moiti´e du tableau A. Donc un ´el´ement quelconque de A apparaˆıt au plus n
dans chacune des deux moiti´es, et donc n
majoritaire.
4 fois dans la premi`ere
4 fois
2 fois en tout dans A. Donc A ne contient pas d’´el´ement
– rx = Vrai et ry = Faux. Un ´el´ement quelconque de A apparaˆıt donc au plus n
4 fois dans la deuxi`eme
moiti´e de A. Nous avons deux cas `a consid´erer :
– x apparaˆıt donc au plus cx + n
– Un ´el´ement autre que x apparaˆıt au plus n
2
+ n
Publicité
un tel ´el´ement apparaˆıt au plus
4 fois dans A.
− cx
D’o`u le r´esultat.
− cx fois dans la premi`ere moiti´e de A. Par cons´equent
4 = 3n
− cx = n −
fois dans A.
4
cx + n
4 (cid:1)
(cid:0)
(cid:1)
n
2
(cid:0)
– ry = Vrai et rx = Faux : ce cas est sym´etrique du pr´ec´edent.
– rx = Vrai et ry = Vrai :
– x = y. x est pr´esent au plus cx + cy fois dans A. De plus, tout autre ´el´ement est pr´esent au plus
− cy fois dans la deuxi`eme moiti´e, soit en tout au
− cx fois dans la premi`ere moiti´e de A et n
2
n
2
plus n − (cx + cy) fois dans A.
– x (cid:54)= y et cx = cy. x est pr´esent au plus cx fois dans la premi`ere moiti´e et n
2
− cx
fois dans la deuxi`eme moiti´e, soit n
2 fois en tout et x n’est pas un ´el´ement majoritaire de A.
Sym´etriquement, il en va de mˆeme de y. Tout autre ´el´ement ne peut ˆetre un ´el´ement majoritaire
(voir le tout premier cas).
− cy = n
2
– x (cid:54)= y et cx > cy. Alors x est pr´esent au plus cx fois dans la premi`ere moiti´e de A et n
2
− cy
2 + cx − cy fois dans A, et ce nombre est strictement
fois dans la deuxi`eme moiti´e, soit au plus n
sup´erieur `a n
Tout autre ´el´ement est pr´esent au plus
n
2
2 + cy − cx = n − ( n
2 car cx > cy. y est pr´esent au plus n
+
(cid:1)
Publicité
− cx + cy (car cy > n
(cid:0)
2 + cx − cy
4 ) = n −
− cx
.
− cy
n
2
n
2
(cid:1)
(cid:0)
n
2 + cx − cy) fois dans A.
= n − cx − cy = n
2
− cx + n
2
− cy ≤
(cid:0)
(cid:1)
2. Quelle est la complexit´e de cet algorithme ?
En dehors des appels r´ecursifs, tous les traitements ont un coˆut constant : Θ(1). La complexit´e de
l’algorithme est donc donn´ee par la relation de r´ecurrence :
T (n) = 2T (cid:16)
n
2 (cid:17) + Θ(1).
Nous nous trouvons donc ici dans le cas 1) du th´eor`eme (avec (cid:15) = 1) et la complexit´e de l’algorithme
est donc :
T (n) = Θ(n).
3
3. `A partir de l’algorithme pr´ec´edent, ´ecrivez un algorithme Majoritaire qui v´erifie si un tableau A
contient un ´el´ement majoritaire.
Majoritaire(A)
(r´eponse, x, cx) ← PseudoMajoritaire(A, 1, longueur (A))
si r´eponse = Faux
alors renvoyer Faux
sinon si Occurrences(x, A, 1, longueur (A)) > longueur (A)
2
alors renvoyer Vrai
sinon renvoyer Faux
4. Quelle est la complexit´e de cet algorithme ?
La complexit´e de cet algorithme est en Θ(n) car c’est la complexit´e de l’appel `a l’algorithme Pseudo-
Majoritaire et celle de l’appel `a l’algorithme Occurrences.
4