Entiers «presque triés» en temps linéaire

16

Je souhaite trier un tableau de valeurs entières positives L=v1,,vn en temps linéaire (dans le modèle RAM avec mesure de coût uniforme, c'est-à-dire que les entiers peuvent avoir jusqu'à la taille logarithmique mais les opérations arithmétiques sur eux sont supposées prendre le temps unitaire). Bien sûr, cela est impossible avec des algorithmes de tri basés sur la comparaison, donc je suis intéressé par le calcul d'un tri "approximatif", c'est-à-dire le calcul d'une permutation vσ(1),,vσ(n) de Lqui est pas vraiment triés en général , mais une « bonne approximation » de la version triée de L . Je suppose que nous trions les entiers par ordre décroissant car cela rend la suite un peu plus agréable à énoncer, mais bien sûr, on pourrait formuler le problème dans l'autre sens.

Un critère possible pour un tri approximatif est le suivant (*): laisser N soit ivi , pour chaque 1in , nous exigeons que vσ(i)N/i (c. -à- la « quasi-triai "La liste est délimitée par le haut par la fonction décroissante iN/i ). Il est facile de voir que le tri réel satisfait à ceci: vσ(2) doit pas être supérieur à vσ(1)c'est donc au plus (vσ(1)+vσ(2))/2 qui est N/2 , et en général vσ(i) doit pas être supérieur à (jivσ(i))/i qui est N/i .

Par exemple, l'exigence (*) peut être obtenue par l'algorithme ci-dessous (suggéré par @Louis). Ma question est la suivante: existe-t-il un travail sur cette tâche de "tri presque" des entiers en temps linéaire, en imposant une exigence comme (*) que le tri réel satisferait? L'algorithme ci-dessous, ou une variante de celui-ci, a-t-il un nom établi?

Edit: correction de l'algorithme et ajout de plus d'explications


Algorithme:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

Cet algorithme fonctionne comme prévu pour les raisons suivantes:

  1. Si un élément v est dans le seau j alors vN/j .

    vj=min(N/v,n)jN/vN/v

  2. Si un élément est dans le seau alors ou . vjN/(j+1)<vj=n

    vj = min ( N / v , n ) j = N / est placé dans le seau , donc ou . Dans le premier cas qui signifie et donc .j=min(N/v,n)j=N/vj=nj=N/vjN/v<j+1N/(j+1)<v

  3. Pour , il y a, au plus, éléments dans les godets de 1 à .j<njj

    Soit j<n et soit k le nombre total d'éléments dans l'un des compartiments 1..j. Par 2. nous avons que chaque élément v dans un seau i (avec ij ) est tel que N/(j+1)N/(i+1)<v . Par conséquent, la somme K de tous les éléments dans les godets de 1 à j est supérieure à k×N/(J+1) . Mais cette sommeK est également inférieure àN donck×N/(j+1)<KN et donc k/(j+1)<1 ce qui nous donnek<j+1 oukj .

  4. T vérifie (*)dire laj -ième élément deT est telle queT[j]N/j

    Par 3. nous avons que T[j] , le j ème élément de T , provient d'un seau i avec ij donc T[j]N/iN/j .

  5. Cet algorithme prend du temps linéaire.

    Le calcul de N prend un temps linéaire. Les compartiments peuvent être implémentés avec une liste chaînée qui a une insertion et une itération O(1) . La boucle imbriquée s'exécute autant de fois qu'il y a d'éléments (c'est-à-dire n fois).

a3nm
la source
1
Ne pas rejeter la question (+1, c'est une bonne question) mais le tri Radix ne ferait-il pas plus que ce dont vous avez besoin?
user541686
@Mehrdad: Merci pour votre commentaire! Le tri Radix trierait les entiers, mais cela prendrait du temps . O(nlog(maxivi))
a3nm
Pourriez-vous nous dire ce qui est exactement indésirable dans cette complexité temporelle? Avez-vous un très grand entier et tout le reste est petit, par exemple?
user541686
1
@ a3nm radix sort n'est pas O (n log n) mais O (n) donc linéaire si la taille des entiers est fixe, par exemple des nombres de 32 bits ou des nombres de 64 bits. Les nombres que vous triez ont-ils une taille variable?
Xavier Combelle
1
@XavierCombelle: Oui, je travaille dans le modèle RAM et je ne peux pas supposer que les entiers d'entrée sont délimités par une constante.
a3nm

Réponses:

8

Cela ressemble beaucoup à l'algorithme ASort. Voir cet article de Giesen et. Al.:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

Malheureusement, le temps de course n'est pas tout à fait linéaire. L'article ci-dessus prouve que tout algorithme randomisé basé sur une comparaison classant éléments dans n 2 / ν ( n ) a une borne inférieure de n l o g ( ν ( n ) ) (en supposant ν ( n ) < n ).nn2/ν(n)nlog(ν(n))ν(n)<n


EDIT , en réponse aux clarifications de la question:

Ce que vous faites est simplement une sorte de seau . Cependant, l'algorithme de tri par compartiment n'est pas linéaire dans ce cas. Le problème: vous devez additionner les nombres naturels puis effectuer la division sur chacun d'eux. Comme les nombres n'ont pas de taille illimitée, n'est plus une opération à temps constant. Il faudra plus de temps pour effectuer le plus de nombres que vous devez additionner.N/V[i]

Encore combien de temps? La division dépend du nombre de chiffres, c'est donc , fois n opérations de division. Cela semble probablement familier. :)lg(n)n

Trixie Wolf
la source
1
O(n)
@ a3nm La clarification de ce que vous avez publié ci-dessus suggère que vous utilisez un tri par compartiment , qui est linéaire (et non basé sur une comparaison, ce qui signifie tester deux éléments l'un par rapport à l'autre). Le problème est qu'il ne fonctionne pas pour tous les entiers mathématiques. Cela ne fonctionne que si la taille entière est limitée.
Trixie Wolf
Lorsque vous dites "Cela ne fonctionne que si la taille de l'entier est limitée", je pense que cela n'est vrai que si je triais réellement les entiers. Mais en général, l'algorithme que j'ai publié ne les trie pas réellement, il applique uniquement le critère le plus faible (*). Je pense donc que cela fonctionne en temps linéaire même lorsque la taille entière n'est pas limitée.
a3nm le
2
@ a3nm Ce n'est pas linéaire. Voir ma réponse étendue ci-dessus.
Trixie Wolf
nlogn
2

Il s'avère que ma question est tout à fait hors de propos après tout. En effet, je travaille sur la machine RAM avec une mesure de coût uniforme (c'est-à-dire que nous avons des registres dont les registres ne sont pas nécessairement de taille constante mais peuvent stocker des entiers de taille logarithmique au plus en entrée, et les opérations sur ces registres prennent un temps constant, y compris au moins addition). Et en fait, dans ce modèle, le tri des entiers (en effectuant essentiellement un tri radix) peut être effectué en temps linéaire. Ceci est expliqué dans l'article de 1996 de Grandjean, Sorting, temps linéaire et problème de satisfiabilité .

(Cela ne répond pas à ma question de savoir s'il existe des notions bien étudiées de "presque trier" un ensemble d'entiers, mais pour qu'elles soient intéressantes, il faudrait probablement que ces notions plus faibles soient plus faciles à appliquer, c'est-à-dire, travailler sur un plus faible modèle ou en quelque sorte exécuté en temps sublinéaire. Cependant, je ne suis actuellement pas au courant d'un sens dans lequel ce serait le cas.)

a3nm
la source