Sélectionnez deux nombres qui totalisent

9

Voici un problème de voisin le plus proche.

Étant donné les réels (très grand !), Plus le réel cible , trouver et dont la somme est la plus proche de . Nous autorisons un prétraitement / indexation raisonnable de (jusqu'à ), mais au moment de la requête (étant donné ), le résultat doit être renvoyé très rapidement (par exemple, heure). $a_1, \ldots, a_n$ $n$ $p$ $a_i$ $a_j$ $p$ $a_1, \ldots, a_n$ $O(n \log n)$ $p$ $O(\log n)$

(Exemple plus simple: si nous voulions uniquement le SINGLE plus proche de , nous hors ligne, , puis ferions une recherche binaire au moment de la requête, ). $a_i$ $p$ $a_1, \ldots, a_n$ $O(n \log n)$ $O(\log n)$

Solutions qui ne fonctionnent pas:

1) Triez hors ligne, puis au moment de la requête, commencez par les deux extrémités et déplacez deux pointeurs vers l'intérieur ( http://bit.ly/1eKHHDy ). Pas bon, en raison du temps de requête . $a_1, \ldots, a_n$ $O(n)$

2) Triez hors ligne, puis au moment de la requête, prenez chaque et effectuez une recherche binaire pour un "copain" qui l'aide à additionner quelque chose proche de . Pas bon, en raison du temps de requête . $a_1, \ldots, a_n$ $a_i$ $p$ $O(n \log n)$

3) Triez toutes les paires hors ligne, puis effectuez une recherche binaire. Pas bon, à cause du prétraitement . $(a_{1}, \ldots, a_{n})$ $O(n^2)$

Merci!

ps. Autres généralisations nécessaires pour la pratique: (1) et pour être des vecteurs à 50 dimensions, (2) "close" pour être la distance du cosinus du vecteur, et (3) -les meilleures paires les plus proches-cette somme, pas seulement 1-meilleur. $a_1, \ldots, a_n$ $p$ $k$

ds.algorithms cg.comp-geom ds.data-structures Kevin
la source

Y a-t-il une limite au temps de prétraitement ou à la quantité d'espace que nous pouvons utiliser après le prétraitement? Si nous sommes limités à l' espace

, avez-vous des raisons de croire qu'il peut être résolu, disons, en temps

? Cela me semble terriblement improbable.

O (n)

$O(n)$

O (\lg n)

$O(\lg n)$

DW

Le prétraitement est limité à O (

log

). J'ai mis à jour l'énoncé du problème.

n

$n$

n

$n$

Kevin

Je n'ai aucune raison de croire que l'interrogation peut être rapide, mais de nombreux résultats utiles pour les voisins les plus proches (arbres kd, hachage sensible à la localité, etc.) me semblent contre-intuitivement bons. Une solution approximative utilisant un hachage sensible à la localité conviendrait parfaitement à une utilisation pratique.

Kevin

17

C'est presque certainement impossible.

$P(n)$ $Q(n)$ $n$ $P(n)+n\cdot Q(n)$ $a_k$ $a_i+a_j$ $-a_k$ $-a_k$

$O(n^2)$ $\Omega(n^2)$ $\Omega(n^2/\text{polylog}\,n)$

En supposant donc que la conjecture est correcte, votre problème nécessite soit un temps de prétraitement (presque) quadratique, soit un temps de requête (presque) linéaire.

Jeffε
la source

2

Si vous pouvez utiliser un espace et un temps illimités pendant le prétraitement, la solution suivante répond à vos besoins:

$\{a_i+a_j:1\le i\le j\le n\}$ $O(n^2)$ $O(n^2)$
$a_i,a_j$ $a_i+a_j$ $p$ $O(\lg n)$

Si cette solution n'est pas acceptable, vous devez réfléchir plus attentivement à vos besoins et modifier la question en conséquence.

DW
la source

Salut et merci! Mais votre solution est la même que ma solution n ° 3, ce qui est problématique en raison du temps de prétraitement O (n ^ 2). Dans mon cas, n est très grand (par exemple, 1 m) et je dois éviter les opérations O (n ^ 2).

Kevin

Sélectionnez deux nombres qui totalisent

Réponses: