Algoritmo para encontrar a menor diferença na matriz

Queremos um algoritmo que, considerando uma matriz de comprimento de números inteiros, encontre a diferença mínima entre dois números inteiros na matriz. $n$

Um desses algoritmos é classificar a matriz e verificar pares de números adjacentes. Isso leva tempo . $O(n\log n)$

Existe uma maneira mais rápida, por exemplo, um algoritmo ? $O(n)$

algorithms arrays boaten
fonte

O (n)

$O(n)$ não é mais rápido do que

O (n \log n)

$O(n\log n)$

David Merinos

Respostas:

Isso depende do seu modelo de computação. Se você permitir apenas aritmética e comparações (o modelo de árvore de decisão algébrica), haverá um limite inferior para a distinção de elementos , o problema de decidir se todos os elementos são distintos. Seu problema é obviamente ainda mais difícil, portanto o mesmo limite inferior se aplica. $\Omega(n\log n)$

(Há algumas letras miúdas: o limite inferior só é válido se o grau dos polinômios comparados estiver limitado. Se tudo o que você está fazendo é comparar várias diferenças , então está . O modelo de árvore de decisão algébrica também permite comparar polinômios mais gerais nas entradas, desde que tenham graus limitados.) $x_i - x_j$

Existem outros modelos que podem ter um desempenho melhor - por exemplo, em alguns modelos, você pode classificar números inteiros em . Mas imagino que você não queira permitir o tipo de truque usado em tais algoritmos. $o(n\log n)$

Yuval Filmus
fonte

Obrigado. O que você quer dizer com "comparar várias diferenças "? Como existem esses pares, isso não levaria tempo ?

x_{i} - x_{j}

$x_i-x_j$

Θ (n^{2})

$\Theta(n^2)$

Ω (n^{2})

$\Omega(n^2)$

boaten

Não necessariamente. Os algoritmos baseados em comparação são permitidos apenas para comparar pares de elementos. Aqui, estou permitindo que você faça consultas mais complicadas, como ou até . Sabemos que existe uma solução que usa comparações do tipo e comparações do tipo . A questão é: você pode fazer melhor, e a resposta é não, se você estiver restrito a fazer consultas lineares (ou, em geral, consultas com graus limitados).

x_{1} - x_{2} > x_{3} - x_{4}

$x_1 - x_2 > x_3 - x_4$

x_{1} + 5 x_{8} - 17 x_{3} < - 5

$x_1 + 5x_8 - 17x_3 < -5$

O (n \log n)

$O(n\log n)$

x_{i} > x_{j}

$x_i > x_j$

O (n)

$O(n)$

x_{i} - x_{j} > x_{k} - x_{ℓ}

$x_i - x_j > x_k - x_\ell$

Yuval Filmus

Não tenho certeza se entendi o significado prático desse limite para a distinção de elementos. Você não teria um O (n) esperado com uma tabela de hash?

Jkff #

Uma tabela de hash não pode ser implementada usando esse modelo de computação. Em geral, limites mais baixos são difíceis de provar. O modelo de árvore de decisão algébrica é aquele em que limites inferiores não triviais são prováveis. Não vejo como provar um limite inferior em nenhum outro modelo - na verdade, esses limites inferiores são normalmente conhecidos apenas por funções aleatórias. Você está certo de que pode haver um truque que vai além desse modelo, mas não consigo pensar em nenhum.

ω (n)

$\omega(n)$

o (n \log n)

$o(n\log n)$

Yuval Filmus

-1

Se os números inteiros na matriz tiverem um número limitado de dígitos, você poderá classificar uma matriz com o algoritmo de classificação radix , que é O (kN) e verificar os pares adjacentes de números (O (N))? A complexidade resultante será O ((k + 1) N), linear.

Pavel Davydov
fonte

Lembre-se das condições sob as quais o tempo de execução da classificação de base é realmente bom.

Raphael

@ Rafael Bem, a pergunta original era se o algoritmo linear existe, então pensei nisso. Você quer dizer que k será maior que log (N) para N pequeno?

Pavel Davydov

k

$k$ e são parâmetros independentes, razão pela qual a classificação radix não é um algoritmo de tempo linear para todas as entradas e, portanto, não contradiz o associado à classificação (comparação). (O artigo da Wikipedia explica isso também.)

N

$N$

Ω (n \log n)

$\Omega(n \log n)$

Raphael

@ Rafael Sim, mas para uma matriz de números inteiros com menos de 64 bits (isso é um caso bastante comum), será linear. Vou editar minha resposta. Obrigado por seus comentários.

Pavel Davydov