Aller au contenu

TD d’algorithmique avancée

Élément majoritaire algorithme Dans cet article, nous allons explorer l'algorithme pour déterminer si un tableau contient un élément majoritaire. Un élément majoritaire est défini comme un élément qui apparaît strictement plus de n/2 fois dans un tableau de n éléments.

D'après le document TD d’algorithmique avancée

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

TD d’algorithmique avancée

Programming, Math · PDF · 4 pages

Afficher l'aperçu du document

Consulter le document original →

Élément majoritaire algorithme

Dans cet article, nous allons explorer l'algorithme pour déterminer si un tableau contient un élément majoritaire. Un élément majoritaire est défini comme un élément qui apparaît strictement plus de n/2 fois dans un tableau de n éléments. Nous examinerons la complexité des algorithmes naïfs et ceux basés sur le paradigme « diviser pour régner », en fournissant des exemples concrets et des justifications pour chaque méthode.

Algorithme naïf pour trouver l'élément majoritaire

Le premier algorithme que nous allons examiner est un algorithme naïf. Cet algorithme calcule le nombre d'occurrences d'une valeur x dans un tableau A entre les indices i et j. Voici le pseudocode de cet algorithme :

Occurrences(x, A, i, j)
  compteur ← 0
  pour k ← i à j faire
    si A[k] = x alors compteur ← compteur + 1
  renvoyer compteur

La complexité de cet algorithme est en Θ(j - i). En utilisant cet algorithme, nous pouvons écrire un algorithme Majoritaire qui vérifie si un tableau A contient un élément majoritaire :

Majoritaire(A)
  pour i ← 1 à longueur(A)/2 faire
    si Occurrences(A[i], A, i, longueur(A)) > longueur(A)/2 alors renvoyer Vrai
  renvoyer Faux

La complexité de cet algorithme est en Θ(n²), car dans le pire des cas, la boucle effectue n/2 itérations, chacune appelant Occurrences sur un tableau de taille n - i.

Algorithme diviser pour régner pour trouver l'élément majoritaire

Le deuxième algorithme que nous allons examiner utilise le paradigme « diviser pour régner ». Cet algorithme divise le tableau A en deux et renvoie un couple (Vrai, x) si le tableau A contient un élément majoritaire, ou (Faux, 0) s'il n'en contient pas. Voici le pseudocode :

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)/2, j)
  si rx = Faux et ry = Faux alors renvoyer (Faux, 0)
  si rx = Vrai et ry = Vrai alors
    si x = y alors renvoyer (Vrai, x)
    sinon
      cx ← Occurrences(x, A, i, j)
      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)/2 alors renvoyer (Vrai, x)
    sinon renvoyer (Faux, 0)
  sinon si Occurrences(y, A, i, j) > (j - i + 1)/2 alors renvoyer (Vrai, y)
  sinon renvoyer (Faux, 0)

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

T(n) = 2T(n/2) + Θ(n)

La phase de combinaison nécessite, dans le pire des cas, la recherche du nombre d'occurrences de deux éléments dans le tableau, ce qui a un coût de n. En appliquant le théorème maître, nous obtenons :

T(n) = Θ(n log n)

Points clés à retenir

Voici les points essentiels à retenir concernant l'algorithme pour trouver un élément majoritaire :

  • Un élément majoritaire est celui qui apparaît plus de n/2 fois dans un tableau.
  • L'algorithme naïf a une complexité de Θ(n²).
  • L'algorithme diviser pour régner a une complexité de Θ(n log n).
  • Les algorithmes utilisent la fonction Occurrences pour compter les éléments.

Questions fréquentes

Qu'est-ce qu'un élément majoritaire ?

Un élément majoritaire est un élément d'un tableau qui apparaît strictement plus de n/2 fois, où n est le nombre total d'éléments dans le tableau.

Quelle est la complexité de l'algorithme naïf pour trouver un élément majoritaire ?

La complexité de l'algorithme naïf est en Θ(n²), car il nécessite de parcourir le tableau plusieurs fois pour compter les occurrences de chaque élément.

Comment fonctionne l'algorithme diviser pour régner ?

L'algorithme diviser pour régner divise le tableau en deux parties, vérifie chaque partie pour un élément majoritaire, puis combine les résultats pour déterminer s'il existe un élément majoritaire dans l'ensemble du tableau.

Quelle est la différence entre l'algorithme naïf et l'algorithme diviser pour régner ?

L'algorithme naïf a une complexité quadratique, tandis que l'algorithme diviser pour régner est plus efficace avec une complexité logarithmique, ce qui le rend plus adapté pour de grands tableaux.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions