Algorithme de temps linéaire déterministe pour vérifier si un tableau est une version triée de l'autre

Considérez le problème suivant:

Entrée: deux tableaux et de longueur , où est trié. $A$ $B$ $n$ $B$

Question: ne et contiennent les mêmes éléments (avec leur multiplicité)? $A$ $B$

Quel est l' algorithme déterministe le plus rapide pour ce problème?
Peut-il être résolu plus rapidement que de les trier? Ce problème peut-il être résolu en temps linéaire déterministe?

algorithms reference-request sorting Albert Hendriks
la source

FWIW l'approche probabiliste est le hachage avec une fonction de hachage indépendante de l'ordre. Carter et Wegman ont écrit l'un des articles originaux à ce sujet ( sciencedirect.com/science/article/pii/0022000081900337 ), mais je n'ai rien vu dans les citations de cet article qui suggère un algorithme déterministe (jusqu'à présent).

KWillets

La déclaration que vous citez concerne le modèle de machine de Turing, qui n'a qu'un intérêt théorique. Les algorithmes sont généralement analysés par rapport au modèle RAM.

Yuval Filmus

ah, c'est le modèle que je recherche. J'ai ajusté la question.

Albert Hendriks

Pourquoi ne pas simplement additionner les éléments du tableau et comparer ensuite la somme? Concernant votre titre, il est linéaire et répond à la question «un tableau est-il la version triée d'un autre? '. Je sais que ce n'est pas le modèle de la machine Turing, mais une solution pratique.

atayenel

@AlbertHendriks Vous (très probablement) ne pouvez pas trier un tableau en sur une machine Turing. Certaines limites inférieures sur SAT (par exemple cs.cmu.edu/~ryanw/automated-lbs.pdf ) sont en fait pour la machine RAM, désolé pour mon commentaire précédent trompeur.

O (n \log n)

$O(n\log n)$

Yuval Filmus

Réponses:

Vous n'avez pas spécifié votre modèle de calcul, je vais donc supposer le modèle de comparaison.

Considérez le cas particulier dans lequel le tableau est extrait de la liste En mots, le ème élément est soit soit . $B$

{1, 2} \times {3, 4} \times \dots \times {2 n - 1, 2 n} .

$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$

i

$i$

2 i - 1

$2i-1$

2 i

$2i$

Je revendique que si l'algorithme conclut que et contiennent les mêmes éléments que l'algorithme a par rapport à chaque élément à son homologue . En effet, supposons que l'algorithme conclut que et contiennent les mêmes éléments, mais compare jamais le premier élément de à son homologue . Si nous commutons le premier élément, l'algorithme procéderait exactement de la même manière, même si la réponse est différente. Cela montre que l'algorithme doit comparer le premier élément (et tout autre élément) à son homologue . $A$ $B$ $B$ $A$ $A$ $B$ $B$ $A$ $A$

Cela signifie que si et contiennent les mêmes éléments, puis après avoir vérifié ce l'algorithme connaît l'ordre de tri de . Il doit donc avoir au moinsdifférentes feuilles, et cela prend donc du temps . $A$ $B$ $A$ $n!$ $\Omega(n\log n)$

Yuval Filmus
la source

J'aurais pensé que cela impliquerait que en général, mais apparemment le modèle de comparaison est différent de cela.

P = Ω (n \log n)

$P = \Omega(n\log n)$

Albert Hendriks

@AlbertHendriks, c'est le même modèle utilisé pour montrer n lg n borne inférieure pour le tri. Cela signifie que la seule opération que vous pouvez effectuer est la comparaison, alors vous ne pouvez pas faire mieux. Je pense que cela répond à votre question.

Kaveh

[CNDT] nous n'avons pas de limites plus strictes même pour le tri! et si vous pouvez trier plus rapidement que n lg n, vous pouvez l'utiliser pour résoudre le problème plus rapidement que n lg n.

Kaveh

@AlbertHendriks, connaissez-vous les algorithmes de temps linéaire pour trier les entiers? Cherchez dans CLRS. Votre cas peut être l'un des cas où nous pouvons trier en temps linéaire.

Kaveh

Les entiers peuvent être triés dans (voir nada.kth.se/~snilsson/fast-sorting ), ou dans le temps prévu (voir ieeexplore .ieee.org / stamp / stamp.jsp? arnumber = 1181890 ), ou même en temps linéaire si la taille du mot est suffisamment grande (voir LNCS 8503, p. 26ff).

O (n \log \log n)

$O(n\log\log n)$

O (n \sqrt{\log \log n})

$O(n\sqrt{\log\log n})$

Yuval Filmus

Cette réponse considère un modèle de calcul différent: le modèle RAM à coût unitaire. Dans ce modèle, les mots machine ont la taille et les opérations sur eux prennent . Nous supposons également par souci de simplicité que chaque élément du tableau tient dans un seul mot machine (et est donc au plus en magnitude). $O(\log n)$ $O(1)$ $n^{O(1)}$

Nous allons construire un algorithme aléatoire temporel linéaire avec une erreur unilatérale (l'algorithme peut déclarer que les deux tableaux contiennent les mêmes éléments même si ce n'est pas le cas) pour le problème plus difficile de déterminer si deux tableaux et contiennent les mêmes éléments. (Nous n'avons besoin d'aucun d'entre eux pour être triés.) Notre algorithme fera une erreur avec une probabilité au plus . $a_1,\ldots,a_n$ $b_1,\ldots,b_n$ $1/n$

L'idée est que l'identité suivante est valable si les tableaux contiennent les mêmes éléments: Le calcul exact de ces polynômes prendra trop de temps. Au lieu de cela, nous choisissons un nombre premier aléatoire et un aléatoire et testons si Si les tableaux sont égaux, le test réussira toujours, alors concentrons-nous sur les cas où les tableaux sont différents. En particulier, un certain coefficient de est non nul. Puisque ont une magnitude , ce coefficient a une magnitude

\prod_{i = 1}^{n} (x - a_{i}) = \prod_{i = 1}^{n} (x - b_{i}) .

$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$

p

$p$

x_{0}

$x_0$

\prod_{i = 1}^{n} (x_{0} - a_{i}) \equiv \prod_{i = 1}^{n} (x_{0} - b_{i}) (\mod p) .

$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i})

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$

a_{i}, b_{i}

$a_i,b_i$

n^{O (1)}

$n^{O(1)}$

2^{n} n^{O (n)} = n^{O (n)}

$2^n n^{O(n)} = n^{O(n)}$ , et donc il a au plus facteurs premiers de taille . Cela signifie que si nous choisissons un ensemble d'au moins nombres premiers de taille au moins (disons), alors pour un nombre premier aléatoire de cet ensemble, il tiendra avec probabilité au moins que Un modulo aléatoire en sera témoin avec une probabilité de (puisqu'un polynôme de degré au plus a au plus racines).

O (n)

$O(n)$

Ω (n)

$\Omega(n)$

n^{2}

$n^2$

p

$p$

n^{2}

$n^2$

p

$p$

1 - 1 / n

$1-1/n$

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i}) ≢ 0 (\mod p) .

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$

x_{0}

$x_0$

p

$p$

1 - n / p \geq 1 - 1 / n

$1-n/p \geq 1-1/n$

n

$n$

n

$n$

En conclusion, si nous choisissons un aléatoire de taille à peu près parmi un ensemble d'au moins nombres premiers différents, et un modulo aléatoire , alors lorsque les tableaux ne contiennent pas les mêmes éléments, notre test échouera avec probabilité . L'exécution du test prend du temps car s'inscrit dans un nombre constant de mots machine. $p$ $n^2$ $n^2$ $x_0$ $p$ $1-O(1/n)$ $O(n)$ $p$

En utilisant le test de primalité temporelle polynomiale et comme la densité des nombres premiers de taille à peu près est , nous pouvons choisir un nombre premier aléatoire dans le temps . Le choix d'un modulo aléatoire peut être implémenté de différentes manières, et est facilité car dans notre cas, nous n'avons pas besoin d'un aléatoire complètement uniforme . $n^2$ $\Omega(1/\log n)$ $p$ $(\log n)^{O(1)}$ $x_0$ $p$ $x_0$

En conclusion, notre algorithme s'exécute dans le temps , génère toujours OUI si les tableaux contiennent les mêmes éléments et génère NON avec la probabilité si les tableaux ne contiennent pas les mêmes éléments. On peut améliorer la probabilité d'erreur de pour toute constante . $O(n)$ $1-O(1/n)$ $1-O(1/n^C)$ $C$

Yuval Filmus
la source

Bien que cet algorithme soit aléatoire, il explique comment implémenter les idées dans certaines des autres réponses afin qu'elles fonctionnent réellement. Il a également un avantage sur l'approche de la table de hachage: il est en place.

Yuval Filmus

Je pense que l'OP n'aime pas les algorithmes probabilistes car il n'a pas aimé l'algorithme de temps linéaire attendu utilisant une table de hachage.

Kaveh

Kaveh tu as raison. Mais bien sûr, cette solution est également intéressante et doit être conservée, elle résout le cas des algorithmes probabilistes. De plus, je pense qu'il utilise le modèle que je recherche.

Albert Hendriks

Je me demande simplement si la notation O (1 / n) est correcte. Bien sûr, je sais ce que vous voulez dire, mais je pense que la définition de big-O équivaut à O (1).

Albert Hendriks

Pas du tout. C'est une quantité limitée par pour un assez grand . C'est une meilleure garantie que .

C / n

$C/n$

n

$n$

O (1)

$O(1)$

Yuval Filmus

-3

je proposerai un autre algorithme (ou au moins un schéma d'un tel algorithme)

Le schéma suppose que les valeurs (supposées " entiers ") se situent dans une plage (étroite?) Entre $[min,max]$

En temps balayant les deux tableaux, nous pouvons trouver les valeurs et pour les deux et leur multiplicité, si elles diffèrent, les tableaux ne sont pas des permutations l'un de l'autre $O(n)$ minmax
Soustrayez les minde toutes les valeurs des deux tableaux (ici le fait qu'un tableau est déjà dans l'ordre trié n'est pas pris en compte, cela peut probablement être amélioré)
Supposons que les valeurs dans les tableaux représentent des masses et nous appliquons une accélération / vitesse à chacune de magnitude (cela peut être amélioré à une magnitude de dans certains cas) $1$ $c > 1$
déplacer les masses jusqu'à ce qu'elles atteignent la valeur maximale max-min, cela a une complexité de . Cela permet de retrouver à la fois les mêmes valeurs et leur multiplicité, si celles-ci diffèrent, les tableaux ne sont pas des permutations les uns des autres. Sinon, les tableaux sont des permutations les uns des autres. $O((max-min)n)$

notez que le schéma d'algorithme ci-dessus peut être (déterministe) assez rapide dans de nombreuses situations pratiques.

Le schéma d'algorithme ci-dessus est une variation d'un algorithme de tri à temps linéaire utilisant des " masses mobiles ". L'intuition physique derrière l' algorithme de tri des " masses mobiles " est la suivante:

Supposons que la valeur de chaque élément représente réellement sa magnitude de masse et imaginez organiser tous les éléments sur une ligne et appliquer la même force d'accélération.

Ensuite, chaque élément se déplacera jusqu'à une distance liée à sa masse, plus massive moins de distance et vice-versa. Ensuite, pour récupérer les articles triés, collectez simplement les articles dans l'ordre inverse en fonction de la distance parcourue.

Cet algorithme est linéaire et déterministe , mais il y a une mise en garde en ce que la quantité de force d'accélération initiale et la distance à parcourir (ou le temps d'attente) sont liées à la distribution des valeurs (c'est-à-dire les " masses ", le ci-dessus). On peut également essayer de discrétiser l'espace pour que les articles voyagent dans une grille et gagner un facteur constant dans la vitesse de l'algorithme (et utiliser une routine de tri rapide pour trier différents articles dans la même cellule ). $max-min$

À cet égard, l'algorithme ci-dessus est similaire aux algorithmes de tri basés sur le numérique (par exemple , tri-radix , tri - comptage )

On peut penser que cet algorithme ne signifie pas grand-chose, mais il montre au moins une chose. Que, " fondamentalement ", au niveau physique, le tri de nombres arbitraires est une opération en temps linéaire dans le nombre d'articles.

Nikos M.
la source

En termes de collecte des articles dans l'ordre inverse de la distance parcourue, cela ne se traduirait-il pas par des comparaisons au niveau de la mise en œuvre, et à ce stade, n'avez-vous pas à trier les "distances"?

JustAnotherSoul