Seleccione dos números que sumen

Aquí hay un problema vecino más cercano.

Dados los reales (¡muy grande !), Más el objetivo real , encuentre y cuyo SUM sea más cercano a . Permitimos un preprocesamiento / indexación razonable de (hasta$a_1, \ldots, a_n$p a i a j p a 1 , … , a n O ( n log n ) p O ( log n $n$$p$$a_i$$a_j$$p$$a_1, \ldots, a_n$$O(n \log n)$ ), pero en el momento de la consulta (dado ), el resultado debe devolverse muy rápido (por ejemplo, tiempo).$p$$O(\log n)$

(Ejemplo más simple: si solo quisiéramos el SINGLE que está más cerca de , clasificaríamos fuera de línea, p a 1 , … , a n O ( n log n ) O ( log n $a_i$$p$$a_1, \ldots, a_n$$O(n \log n)$ , luego haría una búsqueda binaria en el momento de la consulta, )$O(\log n)$

Soluciones que no funcionan:

1) Ordene fuera de línea, luego en el momento de la consulta, comience desde ambos extremos y mueva dos punteros hacia adentro ( http://bit.ly/1eKHHDy O ( n $a_1, \ldots, a_n$ ). No es bueno, debido al tiempo de consulta .$O(n)$

2) Ordene fuera de línea, luego en el momento de la consulta, tome cada y realice una búsqueda binaria para un "amigo" que lo ayude a sumar algo cercano aa i p O ( n log n $a_1, \ldots, a_n$$a_i$$p$ . No es bueno, debido al tiempo de consulta .$O(n \log n)$

3) Ordenar todos los paresO ( n 2$(a_{1}, \ldots, a_{n})$ sin conexión, luego realice una búsqueda binaria. No es bueno, debido al preprocesamiento de .$O(n^2)$

¡Gracias!

PD. Otras generalizaciones necesarios para la práctica: (1) y para ser 50-dimensionales vectores, (2) "cerca" de ser vector de distancia coseno, y (3) -mejor más cercano pares-que-suma, no solo 1 mejor. p $a_1, \ldots, a_n$$p$$k$

Esto es casi ciertamente imposible.

Suponga que puede resolver su problema con el tiempo de preprocesamiento y el tiempo de consulta Q ( n ) . Luego hay un algoritmo simple para resolver el problema de 3SUM: dado un conjunto de n números reales, ¿tres elementos suman cero? En tiempo P ( n ) + n ⋅ Q ( n ) . Preprocesamos todos los números, luego para cada número a k , encontramos el valor de a i + a j más cercano a - a $P(n)$$Q(n)$$n$$P(n)+n\cdot Q(n)$$a_k$$a_i+a_j$$-a_k$; si coincide $-a_k$ exactamente, hemos encontrado una solución al problema 3SUM.

Sin embargo, el algoritmo más rápido conocido para 3SUM se ejecuta en el tiempo , y se conjetura ampliamente que este algoritmo es óptimo. Además, hay un límite inferior Ω ( n 2 ) correspondiente en un modelo de cálculo de árbol de decisión restringido pero natural. Para conjuntos de enteros , existen algoritmos de tiempo ligeramente subcuadrático que "juegan juegos con bits", pero incluso en el modelo de RAM entera, se conjetura que 3SUM requiere Ω ( n 2 $O(n^2)$$\Omega(n^2)$$\Omega(n^2/\text{polylog}\,n)$ tiempo.

Asumiendo que la conjetura es correcta, su problema requiere tiempo de preprocesamiento (casi) cuadrático o tiempo de consulta (casi) lineal.

Si puede usar espacio ilimitado y tiempo ilimitado durante el preprocesamiento, la siguiente solución cumple con sus requisitos:

• $\{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 esta solución no es aceptable, debe analizar detenidamente sus requisitos y editar la pregunta en consecuencia.