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

Considere o seguinte problema:

Entrada: duas matrizes e de comprimento , onde está na ordem de classificação.$A$$B$$n$$B$

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

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?

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\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$$ $i$$2i-1$$2i$

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 .$A$$B$$B$$A$$A$$B$$B$$A$$A$

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 ) .$A$$B$$A$$n!$$\Omega(n\log n)$

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(\log n)$$O(1)$$n^{O(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 .$a_1,\ldots,a_n$$b_1,\ldots,b_n$$1/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

$$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$$ $p$$x_0$ 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 de ∏ n 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 $$\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)$$a_i,b_i$$n^{O(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$2^n n^{O(n)} = n^{O(n)}$$O(n)$$\Omega(n)$$n^2$$p$$n^2$$p$$1-1/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). $$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$$ $x_0$$p$$1-n/p \geq 1-1/n$$n$$n$

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.$p$$n^2$$n^2$$x_0$$p$$1-O(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 .$n^2$$\Omega(1/\log n)$$p$$(\log n)^{O(1)}$$x_0$$p$$x_0$

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)$$1-O(1/n)$$1-O(1/n^C)$$C$

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

$[min,max]$

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. $1$$c > 1$

4. max-min$O((max-min)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.

$max-min$

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.