Le tri entier est-il possible dans O (n) dans le modèle transdichotomique?

À ma connaissance, il n'existe pas d' algorithme pire des cas qui résout le problème suivant: $O(n)$

Étant donné une séquence de longueur composée d'entiers finis, trouvez la permutation où chaque élément est inférieur ou égal à son successeur. $n$

Mais existe-t-il une preuve de son inexistence dans le modèle transdichotomique de calcul ?

Notez que je ne limite pas la plage des entiers. Je ne limite pas non plus les solutions aux types de comparaison.

complexity-theory sorting computation-models lower-bounds orlp
la source

Autant que je sache, il pourrait y avoir un algorithme de temps pour SAT! Donc la réponse est non.

O (n)

$O(n)$

Lembik

AFAIK, c'est toujours un problème ouvert.

Juho

Je ne sais pas s'il peut y avoir une réponse significative jusqu'à ce que vous spécifiez le modèle de calcul que vous utilisez, étant donné que vous ne limitez pas votre ordinateur aux comparaisons et aux échanges. Avec seulement des comparaisons RAM et deux nombres, un argument de l'entropie donne une limite de temps

, même pour les ordinateurs transdichotomiques. Trivialement, si au lieu des swaps et des comparaisons, le tri est une opération élémentaire, il peut être fait en

. Si insérer un entier au bon endroit est une opération élémentaire,

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$ . Aviez-vous en tête un modèle d'échange au-delà de la comparaison spécifique?

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen Ma question précise le modèle transdichotomique de calcul. En anglais simple: un modèle de calcul où la taille des mots de la machine est suffisamment grande pour contenir n'importe quel entier du problème. Donc, comparer deux entiers est O (1), mais il en est de même de les additionner, de les multiplier, etc. Dans ce modèle de calcul, la borne entropique a déjà été dépassée, voir Han, Yijie (2004), «Tri déterministe dans le temps O (n log log n) et l'espace linéaire» .

orlp

@orlp je vois; si vous profitez de la structure des entiers, vous pouvez battre la limite entropique. Je ne connaissais pas le tri entier; Je serai sûr de lire sur ce sujet!

Lieuwe Vinkhuijzen

Réponses:

Les entiers peuvent être triés de manière stable en temps avec espace supplémentaire. $O(n)$ $O(1)$ Plus précisément, si vous avez entiers dans l'intervalle , le peut être trié en temps O (n). $n$ $[1, n^c]$

Cela n'a été montré il y a que deux ans par une équipe comprenant feu Mihai Pătrașcu (ce qui ne devrait surprendre personne qui connaît son travail). C'est un résultat remarquable que je suis surpris que plus de gens ne connaissent pas, car cela signifie que le problème du tri des entiers est (théoriquement) résolu.

Il existe un algorithme pratique (donné dans le document ci-dessus) si vous êtes autorisé à modifier les clés. Fondamentalement, vous pouvez compresser les entiers triés plus que vous ne pouvez compresser les entiers non triés, et l'espace supplémentaire que vous gagnez est exactement égal à la mémoire supplémentaire nécessaire pour effectuer le tri radix. Ils fournissent également un algorithme peu pratique qui prend en charge les clés en lecture seule.

Pseudonyme
la source

D'après ce que je peux comprendre de l'abstrait, ce n'est pas général - il ne peut trier les mots que jusqu'à en . Ma question mentionne explicitement des nombres entiers illimités.

\log n

$\log n$

O (n)

$O(n)$

orlp

@orlp Le troisième algorithme de l'article parle d'entiers de longueur illimitée.

Pseudonyme du

Je le lis peut-être mal, mais je ne peux voir qu'une description d'une méthode pour réduire l' utilisation de la mémoire des algorithmes de tri d'entiers non bornés. Citant de l'abstrait (soulignement le mien): "Une autre question intéressante est le cas de l'arbitraire . Ici, nous présentons une transformation de boîte noire de tout algorithme de tri RAM à un algorithme de tri qui utilise uniquement O (1) d'espace supplémentaire et a le même temps d'exécution . " $c$

orlp

Pardonnez-moi, mais dans son état actuel, cette réponse ne répond pas du tout à la question . J'ai explicitement mentionné que les entiers ne sont pas limités . Cette réponse résout un problème entièrement différent.

orlp

Le dernier point n'est plus dans une petite police :)

orlp

-1

$O(bn)$ $b$ $n$

S'il n'y a pas de limite supérieure sur la taille de vos entiers, alors je ne crois pas qu'il existe un algorithme de tri en temps linéaire connu.

RFC 2549
la source

Bienvenue! Ce que vous dites est tout à fait vrai, mais je ne pense pas que cela réponde à la question. La question demande spécifiquement une preuve que l'algorithme requis n'existe pas dans un modèle particulier de calcul; dire simplement qu'aucun algorithme de ce type n'est connu ne prouve pas qu'il n'en existe pas.

David Richerby

En fait, b étant une constante dans notre problème, je considère que cet algorithme est en o (n)

RFC 2549

b

$b$

n

$n$

O (n)

$O(n)$

o (n)

$o(n)$

Oui, certainement une faute de frappe;) dans sa question, comme vous supposez un nombre correspondant à un mot de longueur b, cela devient une constante.

RFC 2549

Cela ne fait pas de la longueur des mots une constante. ( Dans le cas contraire, il n'y aurait aucune raison de supposer explicitement « que les opérations sur les mots simples prennent le temps constant par opération ».