Modèle d’Ewens

Algorithme de tri optimal pour la mesure mrec

Pour motiver le choix de ces distributions, nous allons nous intéresser à un algorithme de tri qui s’adapte au nombre de records. Pour rappel, si une séquence X a rec(X) max-records, alors sa mesure est donnée par mrec(X) = |X| − rec(X). Nous pouvons également démontrer qu’il existe une borne inférieure pour les algorithmes de tri par comparaisons. Cette borne est donnée dans la Proposition 22. Proposition 22. Le problème du tri d’une séquence X, de taille n, telle que mrec(X) = k admet une borne inférieure de Ω(n + k log k) comparaisons.

Démonstration. Il suffit d’appliquer le théorème 7 qui, pour rappel, nous dit dans le cas de mrec que le problème du tri admet une borne inférieure de la forme Ω(max(n, log|below(X, mrec))|) avec below(X, mrec) qui sont les permutations σ de taille n telles que mrec(σ) ≤ k. Pour obtenir le résultat, il ne nous reste donc qu’à déterminer ce qu’est le cardinal de cet ensemble. En particulier, nous allons démontrer l’inégalité |below(X, mrec)| ≥ k!

Construisons l’ensemble Λ = {σ ∈ Sn |σ(1) = 1, σ(2) = 2, . . . , σ(n−k) = n−k} qui est l’ensemble des permutations pour lesquelles les n − k premiers éléments sont des points fixes. Observons que ces points fixes sont également des maxrecords dans ce cas et donc mrec(σ) ≤ k pour σ ∈ Λ. Ainsi, nous avons la relation Λ ⊂ below(X, mrec). Comme les k derniers éléments peuvent être fixés indépendamment pour toute permutation de Λ, nous avons que son cardinal est égal à k!. Cette égalité nous permet de démontrer l’inéquation. En utilisant cette inéquation nous prouvons le résultat annoncé

Un algorithme adaptatif qui atteint cette borne est alors considéré comme optimal pour cette mesure d’après les travaux de Mannila. L’algorithme 18 tri une séquence en s’adaptant à cette mesure de désordre. Cette algorithme fonctionne en plusieurs étapes. La première étape est l’extraction des max-records qui sont stockés dans l’ordre dans une sous-séquence temporaire que nous nommons ici Y . Comme ils sont dans l’ordre et par définition de ce qu’est un max-records, la séquence Y est donc triée. La deuxième étape est l’utilisation d’une fonction de 163 tri auxiliaire pour trier les éléments restants dans X qui ne sont pas des records. La troisième étape est la fusion des deux séquences triées X et Y qui permet d’obtenir la sortie.

La proposition qui suit montre que l’algorithme est optimal pour la mesure mrec. Proposition 23. L’algorithme 18 peut trier une séquence X de taille n, tel que mrec(X) = k en O(n + k log k) comparaisons. Démonstration. Pour la première étape, il est suffisant de faire un balayage de la séquence en retenant le dernier max-record qui a été rencontré. Cet étape est donc équivalent à la recherche du maximum de X et nécessite n − 1 comparaisons. Pour la deuxième étape, le nombre d’éléments à trier restant dans X est exactement mrec(X) = k. Si l’algorithme de tri auxiliaire utilisé est en O(k log k), comme par exemple le tri fusion, alors cet étape nécessite O(k log k) comparaisons.

La troisième étape est une fusion de X et Y ce qui demande n − 1 comparaisons dans le pire des cas. En combinant la contribution de ces trois étapes, nous obtenons le résultat annoncé. L’étude d’une distribution qui favorise l’apparition de records dans une permutation est en partie motivée par le souhait de pouvoir analyser en moyenne l’Algorithme 18 qui joue le rôle d’exemple jouet. 

Distribution d’Ewens

Nous allons dès à présent donner une définition d’une distribution connue dans la littérature par les probabilistes, à savoir la distribution d’Ewens. Il s’agit d’une distribution non-uniforme qui a l’avantage de favoriser les permutations qui ont un petit ou un grand nombre de cycles. Concrètement, cette distribution est paramétrée par une valeur réelle positive que nous noterons par la suite θ. Ce paramètre va favoriser l’apparition de cycles si θ > 1 et va, au contraire, favoriser les permutations qui présentent peu de cycles si θ < 1. Le cas où θ = 1 donne la distribution uniforme. Voyons maintenant comment est définie la probabilité d’avoir une permutation σ ∈ Sn sous cette distribution.