Algorithme pour trouver la plus petite différence dans le tableau

Nous voulons un algorithme qui, étant donné un tableau de longueur d'entiers, trouve la différence minimale entre deux entiers dans le tableau. $n$

Un tel algorithme consiste à trier le tableau et à vérifier les paires de nombres adjacentes. Cela prend du temps . $O(n\log n)$

Existe-t-il un moyen plus rapide, par exemple, un algorithme ? $O(n)$

algorithms arrays bateau
la source

O (n)

$O(n)$ n'est pas plus rapide que

O (n \log n)

$O(n\log n)$

David Merinos

Réponses:

Cela dépend de votre modèle de calcul. Si vous autorisez uniquement l'arithmétique et les comparaisons (le modèle d'arbre de décision algébrique), $\Omega(n\log n)$ borne inférieure pour la distinction des éléments , le problème de décider si tous les éléments sont distincts. Votre problème est bien sûr encore plus difficile, donc la même borne inférieure s'applique.

(Il y a des petits caractères: la limite inférieure ne tient que si le degré des polynômes comparés est limité. Si tout ce que vous faites est de comparer différentes différences $x_i - x_j$ , alors vous êtes prêt à partir. Le modèle d'arbre de décision algébrique vous permet également de comparer des polynômes plus généraux dans les entrées, tant qu'ils ont un degré borné.)

Il existe d'autres modèles qui pourraient mieux fonctionner - par exemple, dans certains modèles, vous pouvez trier les entiers dans $o(n\log n)$ . Mais j'imagine que vous ne voulez pas autoriser le genre de ruse utilisé dans de tels algorithmes.

Yuval Filmus
la source

Merci. Qu'entendez-vous par "comparer diverses différences

x_{i} - x_{j}

$x_i-x_j$ "? Puisqu'il y a

Θ (n^{2})

$\Theta(n^2)$ de telles paires, cela ne prendrait-il pas du temps

Ω (n^{2})

$\Omega(n^2)$ ?

bateau

Pas nécessairement. Les algorithmes basés sur la comparaison ne sont autorisés qu'à comparer des paires d'éléments. Ici, je vous permet de faire des requêtes plus compliquées telles que

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

$x_1 - x_2 > x_3 - x_4$ , ou même

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

$x_1 + 5x_8 - 17x_3 < -5$ . Nous savons qu'il existe une solution qui utilise

O (n \log n)

$O(n\log n)$ comparaisons du type

x_{i} > x_{j}

$x_i > x_j$ , et

O (n)

$O(n)$ comparaisons du type

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

$x_i - x_j > x_k - x_\ell$ . La question est, pouvez-vous faire mieux, et la réponse est non, si vous n'êtes limité qu'à faire des requêtes linéaires (ou, plus généralement, des requêtes de degrés bornés).

Yuval Filmus

Je ne suis pas sûr de comprendre la signification pratique de cette distinction d'élément liée. N'auriez-vous pas un O (n) attendu avec une table de hachage?

jkff

Une table de hachage ne peut pas être implémentée à l'aide de ce modèle de calcul. En général, les limites inférieures sont difficiles à prouver. Le modèle d'arbre de décision algébrique est un modèle dans lequel des limites inférieures non triviales sont prouvables. Je ne vois pas comment prouver

ω (n)

$\omega(n)$ borne inférieure dans tout autre modèle - en effet, ces bornes inférieures ne sont généralement connues que pour les fonctions aléatoires. Tu as raison qu'il pourrait y avoir un truc

o (n \log n)

$o(n\log n)$ algorithme qui va au-delà de ce modèle, mais je ne peux penser à aucun.

Yuval Filmus

-1

Si les entiers dans le tableau ont un nombre limité de chiffres, vous pouvez trier un tableau avec l' algorithme de tri radix , c'est-à-dire O (kN) et ensuite vérifier les paires de nombres adjacentes (O (N))? La complexité résultante sera O ((k + 1) N), linéaire.

Pavel Davydov
la source

Gardez à l'esprit les conditions dans lesquelles le temps d'exécution du tri Radix est réellement bon.

Raphael

@Raphael Eh bien, la question d'origine était de savoir si l'algorithme linéaire existe, alors j'y ai pensé. Vous voulez dire que k sera plus grand que log (N) pour un petit N?

Pavel Davydov

k

$k$ et

N

$N$ sont des paramètres indépendants, c'est pourquoi le tri radix n'est pas un algorithme à temps linéaire pour toutes les entrées, et ne contredit donc pas le

Ω (n \log n)

$\Omega(n \log n)$ lié au tri (de comparaison). (L'article Wikipédia l'explique aussi.)

Raphael

@Raphael Oui, mais pour un tableau d'entiers inférieurs à 64 bits (ce qui est assez courant), il sera linéaire. Je vais modifier ma réponse. Merci pour vos commentaires.

Pavel Davydov