Algoritmo de tempo linear determinístico para verificar se um array é uma versão classificada do outro

19

Considere o seguinte problema:

Entrada: duas matrizes e de comprimento , onde está na ordem de classificação.ABnB

Consulta: se e contêm os mesmos itens (com sua multiplicidade)?AB

Qual é o algoritmo determinístico mais rápido para esse problema?
Pode ser resolvido mais rapidamente do que ordená-los? Esse problema pode ser resolvido em tempo linear determinístico?

Albert Hendriks
fonte
1
FWIW, a abordagem probabilística é o hash com uma função de hash independente da ordem. Carter e Wegman escreveram um dos artigos originais sobre isso ( sciencedirect.com/science/article/pii/0022000081900337 ), mas não vi nada nas citações desse artigo que sugerisse um algoritmo determinístico (até agora).
KWillets
1
A afirmação que você cita é sobre o modelo de máquina de Turing, que é apenas de interesse teórico. Os algoritmos são geralmente analisados ​​com relação ao modelo de RAM.
Yuval Filmus
ah, então esse é o modelo que estou procurando. Eu ajustei a pergunta.
Albert Hendriks
Por que você não soma os itens da matriz e compara o somatório? Em relação ao seu título, ele é linear e responde à pergunta 'uma matriz é a versão classificada de outra? ' Estou ciente de que não é o modelo da máquina de Turing, mas uma solução prática.
Atayenel
1
@AlbertHendriks Você (provavelmente) não pode classificar uma matriz emO(nlogn) em uma máquina de Turing. Alguns limites mais baixos no SAT (por exemplo,cs.cmu.edu/~ryanw/automated-lbs.pdf) são realmente para a máquina RAM, desculpe pelo meu comentário enganoso anterior.
Yuval Filmus

Respostas:

14

Você não especificou seu modelo de computação, então assumirei o modelo de comparação.

Considere o caso especial em que a matriz é obtida da lista { 1 , 2 } × { 3 , 4 } × × { 2 n - 1 , 2 n } . Em palavras, o i- ésimo elemento é 2 i - 1 ou 2 i .B

{1,2}×{3,4}××{2n1,2n}.
i2i12i

Eu afirmo que, se o algoritmo conclui que e B contêm os mesmos elementos, que o algoritmo comparou cada elemento B com o seu homólogo em A . De fato, suponha que o algoritmo conclui que A e B contêm os mesmos elementos, mas nunca compara o primeiro elemento do B à sua contraparte em A . Se mudarmos o primeiro elemento, o algoritmo continuará exatamente da mesma maneira, mesmo que a resposta seja diferente. Isso mostra que o algoritmo deve comparar o primeiro elemento (e qualquer outro elemento) à sua contraparte em A .ABBAABBAA

Isto significa que se e B contêm os mesmos elementos, em seguida, depois de verificar isso o algoritmo sabe a ordem de classificação de A . Por isso, deve ter pelo menos n ! folhas diferentes e, portanto, leva tempo Ω ( n log n ) .ABAn!Ω(nlogn)

Yuval Filmus
fonte
Eu teria pensado que isso implicaria que em geral, mas aparentemente o modelo de comparação é diferente disso. P=Ω(nlogn)
Albert Hendriks
@AlbertHendriks, é o mesmo modelo usado para mostrar o limite inferior da classificação. Isso significa que a única operação que você pode executar é a comparação e não pode fazer melhor. Eu acho que isso responde à sua pergunta.
Kaveh
[Cntd] não temos limites mais fortes nem para a triagem! e se você puder classificar mais rápido que n lg n, poderá usá-lo para resolver o problema mais rapidamente que n lg n.
Kaveh
1
@AlbertHendriks, você conhece algoritmos de tempo linear para classificar números inteiros? Procure no CLRS. Seu caso pode ser um dos casos em que podemos classificar em tempo linear.
Kaveh
6
Inteiros podem ser classificados em (consulte nada.kth.se/~snilsson/fast-sorting ) ou no tempo esperado O ( n O(nloglogn)(consulteieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1181890), ou mesmo em tempo linear, se o tamanho da palavra for grande o suficiente (consulte LNCS 8503, p. 26ff). O(nloglogn)
Yuval Filmus
10

Esta resposta considera um modelo diferente de computação: o modelo de RAM de custo unitário. Nesse modelo, as palavras de máquina têm o tamanho e as operações nelas levam tempo O ( 1 ) . Também assumimos por simplicidade que cada elemento da matriz se encaixa em uma palavra de máquina (e, portanto, é no máximo n O ( 1 ) em magnitude).O(logn)O(1)nO(1)

Vamos construir um tempo linear randomizados algoritmo com unilateral de erro (o algoritmo pode declarar as duas matrizes para conter os mesmos elementos, mesmo que este não é o caso) para o problema mais difícil de determinar se duas matrizes e b 1 , , b n contêm os mesmos elementos. (Não exigimos que nenhuma delas seja classificada.) Nosso algoritmo cometerá um erro com probabilidade no máximo 1 / n .a1,,anb1,,bn1/n

A ideia é que o seguinte identidade prende sse as matrizes contêm os mesmos elementos: A computação desses polinômios exatamente levará muito tempo. Em vez disso, escolhemos um primo aleatório p e um x 0 aleatório e testamos se n i = 1 ( x 0 - a i ) n

i=1n(xai)=i=1n(xbi).
px0 Se as matrizes forem iguais, o teste sempre será aprovado, então vamos nos concentrar nos casos em que as matrizes são diferentes. Em particular, algum coeficiente den i = 1 ( x - a i ) - n i = 1 ( x - b i ) é diferente de zero. Como a i , b i tem magnitude n O ( 1 ) , esse coeficiente tem magnitude 2 n n O (
i=1n(x0ai)i=1n(x0bi)(modp).
i=1n(xai)i=1n(xbi)ai,binO(1) e, portanto, possui no máximoO(n)fatores primos de tamanhoΩ(n). Isso significa que, se escolhermos um conjunto de pelo menos n 2 primospde tamanho pelo menos n 2 (digamos), então, para um primo aleatóriopdesse conjunto, ele manterá com probabilidade pelo menos1-1 / nque n i = 1 (x- a i )2nnO(n)=nO(n)O(n)Ω(n)n2pn2p11/n Ummódulo p aleatório x 0 p testemunhará isso com probabilidade 1 - n / p 1 - 1 / n (uma vez que um polinômio de grau no máximo n tem no máximo n raízes).
i=1n(xai)i=1n(xbi)0(modp).
x0p1n/p11/nnn

Em conclusão, se escolhermos um aleatório de tamanho aproximadamente n 2 entre um conjunto de pelo menos n 2 números primos diferentes e um módulo aleatório x 0 p , quando as matrizes não contiverem os mesmos elementos, nosso teste falhará com probabilidade 1 - O ( 1 / n ) . A execução do teste leva tempo O ( n ), pois p se encaixa em um número constante de palavras de máquina.pn2n2x0p1O(1/n)O(n)p

Usando o teste de primalidade no tempo polinomial e como a densidade de primos de tamanho aproximadamente é Ω ( 1 / log n ) , podemos escolher um primo aleatório p no tempo ( log n ) O ( 1 ) . Escolhendo um aleatória x 0 modulo p pode ser implementado de várias maneiras, e é mais fácil uma vez que no nosso caso, não precisa de um completamente uniforme aleatória x 0 .n2Ω(1/logn)p(logn)O(1)x0px0

Em conclusão, nosso algoritmo é executado no tempo , sempre gera YES se as matrizes contiverem os mesmos elementos e gera NO com probabilidade 1 - O ( 1 / n ) se as matrizes não contiverem os mesmos elementos. Podemos melhorar a probabilidade de erro para 1 - O ( 1 / n C ) para qualquer C constante .O(n)1O(1/n)1O(1/nC)C

Yuval Filmus
fonte
1
Embora esse algoritmo seja randomizado, ele explica como implementar as idéias em algumas das outras respostas para que elas realmente funcionem. Ele também tem uma vantagem sobre a abordagem de hashtable: está no local.
Yuval Filmus
Eu acho que o OP não gosta de algoritmos probabilísticos, pois ele não gostou do algoritmo de tempo linear esperado usando uma tabela de hash.
Kaveh
Kaveh, você está certo. Mas é claro que essa solução também é interessante e deve ser mantida, pois resolve o caso dos algoritmos probabilísticos. Além disso, acho que ele usa o modelo que estou procurando.
Albert Hendriks
1
Eu só estou querendo saber se a notação O (1 / n) está correta. Claro que sei o que você quer dizer, mas acho que, pela definição de big-O, isso é equivalente a O (1).
Albert Hendriks
2
De modo nenhum. É uma quantidade limitada de para suficientemente grande n . Essa é uma garantia melhor que O ( 1 ) . C/nnO(1)
Yuval Filmus
-3

vou propor outro algoritmo (ou pelo menos um esquema desse algoritmo)

[mEun,mumax]

  1. O(n)minmax

  2. Subtraia o valor minde todos os valores de ambas as matrizes (aqui o fato de uma matriz já estar na ordem de classificação não é levado em consideração, presumivelmente isso pode ser melhorado)

  3. 1c>1

  4. max-minO((mumax-mEun)n)

observe que o esquema do algoritmo acima pode ser (deterministicamente) bastante rápido em muitas situações práticas.

O esquema de algoritmo acima é uma variação de um algoritmo de classificação em tempo linear que emprega " massas móveis ". A intuição física por trás do algoritmo de classificação de " massas móveis " é esta:

Suponha que o valor de cada item realmente represente sua magnitude de massa e imagine organizar todos os itens em uma linha e aplicar a mesma força de aceleração.

Então, cada item se moverá para uma distância relacionada à sua massa, mais massiva, menos distância e vice-versa. Para recuperar os itens classificados, basta coletar os itens na ordem inversa pela distância percorrida.

mumax-mEun

A este respeito, o algoritmo acima é similar aos algoritmos numéricos à base de triagem (por exemplo radix-tipo , contando-tipo )

Pode-se pensar que esse algoritmo pode não significar muito, mas mostra pelo menos uma coisa. Que " fundamentalmente ", no nível físico, classificar números arbitrários é uma operação de tempo linear no número de itens.

Nikos M.
fonte
Em termos de coleta dos itens na ordem inversa da distância percorrida, isso não se traduz em comparações no nível de implementação e nesse ponto você não precisa classificar as "distâncias"?
JustAnotherSoul