Recherche d’un élément majoritaire

Recherche d’un élément majoritaire

Etant donnée une liste L de n éléments (avec répétitions), le problème de l’élément majoritaire consiste à déterminer si il existe un élément dont le nombre d’occurences est plus grand que n/2.

Algorithme Naïf

Décrire un algorithme qui recense les éléments distincts et qui calcule pour chacun d’eux son nombre d’occurences.

Quelle est la complexité de cet algorithme ?

Diviser pour régner

On divise la liste L en deux sous-listes L1 et L2 de même taille (à une unité près).

Montrer qu’un élément qui n’est majoritaire ni dans L1 ni dans L2 ne peut pas être majoritaire dans L.

En déduire un algorithme pour le calcul d’un élément majoritaire.

Montrer que la complexité de cet algorithme est O(n log n).

Algorithme optimal

Nous allons montrer que l’algorithme suivant permet de résoudre le problème avec une complexité optimale.

Pour mieux voir les choses, supposons que l’on ait à déterminer s’il existe une couleur majoritaire parmi n balles colorées contenues dans un sac.

On dispose d’une étagère pour poser les balles les unes à côté des autres et d’une corbeille pouvant contenir autant de balles que nécessaire.

Description de l’algorithme

L’algorithme se décompose en deux phases :

  1. Prendre une balle b dans le sac. Si la dernière balle posée sur l’étagère est de la même couleur que b, placer b dans la corbeille. Sinon, placer b sur l’étagère. Dans ce dernier cas, si la corbeille est non-vide, prendre une balle dans la corbeille et la placer à côté de b sur l’étagère. Répéter cette opération tant que le sac est non vide.

  2. Soit c la couleur de la dernière balle poséee sur l’étagère. Remettre toutes les balles dans le sac tout en calculant le nombre m de balles de couleur c. Si m > n/2 alors c est majoritaire sinon il n’y a aucun élément majoritaire.

Preuve de correction

Montrer par récurrence sur le nombre d’itérations de la phase 1, qu’à la fin de chacune des itérations, toutes les balles de la corbeille sont de la même couleur que la dernière balle posée sur l’étagère.

Observer que deux balles placées consécutivement sur l’étagère n’ont pas la même couleur.

En déduire que seule la couleur de la dernière balle posée sur l’étagère peut être majoritaire.

Complexité

Analyser la complexité de cet algorithme.