TD d’algorithmique avancée

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-être pas immédiats sont les suivants :

(a) rx = Faux et ry = Faux : dans ce cas il n’y a pas d’élément qui soit majoritaire dans la première

moitié du tableau, ni d’élément qui soit majoritaire dans la deuxième moitié du tableau. Si le table

contient n éléments, le nombre d’occurrences d’un élément quelconque dans la première moitié

du tableau est donc inférieur ou égal à

2 éléments— et il en va

de même pour le deuxième moitié. Donc le nombre d’occurences d’un élément quelconque dans le

tableau est inférieur à n

2 et le tableau ne contient pas d’élément majoritaire.

2 —la première moitié ayant n

n

2

(b) rx = Vrai et ry = Vrai avec x = y : dans ce cas x est présent 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é de cet algorithme ?

La complexité de cet algorithme est définie par la relation de récurrence :

T (n) = 2T (cid:16)

n

2 (cid:17) + Θ(n).

En effet, la phase de combinaison nécessite, dans le pire des cas, la recherche du nombre d’occurences

de deux éléments dans le tableau, ce qui a un coût de n, toutes les autres opérations étant de coût

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éorème et donc :

T (n) = Θ(n log n).

Deuxième algorithme « diviser pour régner »

1. Écrivez un algorithme construit suivant le paradigme « diviser pour régner », prenant en entrée un

tableau A —qu’il divisera en deux— et possédant la propriété suivante :

– soit cet algorithme nous garantit que le tableau A ne contient pas d’élément majoritaire ;

– soit cet algorithme nous renvoie un élément x et un entier cx > n/2 tels que x apparaisse au plus cx

fois dans A et que tout autre élément 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érons un par un les différents cas de figure :

– rx = Faux et ry = Faux. Aucun élément n’apparaˆıt strictement plus de n

(resp. la deuxième) moitié du tableau A. Donc un élément quelconque de A apparaˆıt au plus n

dans chacune des deux moitiés, et donc n

majoritaire.

4 fois dans la première

4 fois

2 fois en tout dans A. Donc A ne contient pas d’élément

– rx = Vrai et ry = Faux. Un élément quelconque de A apparaˆıt donc au plus n

4 fois dans la deuxième

moitié de A. Nous avons deux cas à considérer :

– x apparaˆıt donc au plus cx + n

– Un élément autre que x apparaˆıt au plus n

2

+ n

un tel élément apparaˆıt au plus

4 fois dans A.

− cx

D’où le résultat.

− cx fois dans la première moitié de A. Par conséquent

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étrique du précédent.

– rx = Vrai et ry = Vrai :

– x = y. x est présent au plus cx + cy fois dans A. De plus, tout autre élément est présent au plus

− cy fois dans la deuxième moitié, soit en tout au

− cx fois dans la première moitié de A et n

2

n

2

plus n − (cx + cy) fois dans A.

– x (cid:54)= y et cx = cy. x est présent au plus cx fois dans la première moitié et n

2

− cx

fois dans la deuxième moitié, soit n

2 fois en tout et x n’est pas un élément majoritaire de A.

Symétriquement, il en va de même de y. Tout autre élément ne peut être un élément majoritaire

(voir le tout premier cas).

− cy = n

2

– x (cid:54)= y et cx > cy. Alors x est présent au plus cx fois dans la première moitié de A et n

2

− cy

2 + cx − cy fois dans A, et ce nombre est strictement

fois dans la deuxième moitié, soit au plus n

supérieur à n

Tout autre élément est présent au plus

n

2

2 + cy − cx = n − ( n

2 car cx > cy. y est présent au plus n

+

(cid:1)

− 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é de cet algorithme ?

En dehors des appels récursifs, tous les traitements ont un coût constant : Θ(1). La complexité de

l’algorithme est donc donnée par la relation de récurrence :

T (n) = 2T (cid:16)

n

2 (cid:17) + Θ(1).

Nous nous trouvons donc ici dans le cas 1) du théorème (avec (cid:15) = 1) et la complexité de l’algorithme

est donc :

T (n) = Θ(n).

3

3. À partir de l’algorithme précédent, écrivez un algorithme Majoritaire qui vérifie si un tableau A

contient un élément majoritaire.

Majoritaire(A)

(réponse, x, cx) ← PseudoMajoritaire(A, 1, longueur (A))

si réponse = 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é de cet algorithme ?

La complexité de cet algorithme est en Θ(n) car c’est la complexité de l’appel à l’algorithme Pseudo-

Majoritaire et celle de l’appel à l’algorithme Occurrences.

4