Encontrar taxis números en $O(n)$ tiempo

Question

Este es un examen de final de la pregunta en mi algoritmos de clase:

$k$ es de un taxi número si $k = a^3+b^3=c^3+d^3$, y $a,b,c,d$ son distintos números enteros positivos. Encontrar todos los números de taxis $k$ tal que $a,b,c,d < $ n $O(n)$ tiempo.

No sé si el problema tenía una errata o no, porque $O(n^3)$ me parece más razonable. La mejor que se me ocurre es $O(n^2 \log n)$, y que es el mejor que nadie que yo conozca puede venir para arriba con.

El $O(n^2 \log n)$ algoritmo:

1. Probar todas las posibles $a^3+b^3=k$ pares, por cada $k$, tienda $(k,1)$ en un árbol binario(indexados por $k$) si $(k,i)$ no existe, si $(k,i)$ existe, reemplazar $(k,i)$ con $(k,i+1)$

2. Transversal del árbol binario, la salida de todos $(k,i)$ donde $i\geq 2$

Hay métodos más rápidos? Este debe ser el mejor método posible sin el uso de cualquier número de resultado teórico debido a que el programa podría salida $O(n^2)$ taxi números.

Es $O(n)$ siquiera posible? Uno tiene que demostrar que no son sólo $O(n)$ taxi números de menor a $2n^3$ en el fin de demostrar que existe una $O(n)$ algoritmo.

Edit: El profesor admitir que era un error, que debería haber sido $O(n^3)$. Estoy feliz de haber hecho la errata, ya que la respuesta Tomer Vromen sugerido es increíble.

Answer 1

Yo no sé acerca de $O(n)$, pero puedo hacerlo en $O(n^2)$. La idea principal es utilizar la inicialización de un array en $O(1)$ (esta es la mejor referencia que he encontrado, se que es raro ya que esto parece un concepto muy importante). A continuación, se itera a través de todos los posibles $(a,\ b)$ pares y hacer lo mismo en el paso 1 en el algoritmo propuesto. Desde entonces $a^3+b^3 \leq 2n^3$, la matriz debe ser de tamaño $2n^3$, pero aún así es inicializado en $O(1)$. El acceso a un elemento de la matriz es $O(1)$ como en una matriz regular.

Answer 2

Al parecer este es un problema resuelto y cada solución racional a $x^3 + y^3 = z^3 + w^3$ es proporcional a

$x = 1 − (p − 3t)(p^2 + 3t^2)$

$ $ y = -1 + (p + 3q)(p^2 + 3t^2)$

$z = (p + 3q) − (p^2 + 3t^2)^2$

$w = −(p − 3t) + (p^2 + 3t^2)^2$

Ver: http://129.81.170.14/~erowland/papers/koyama.pdf, Página 2.

Vea también: http://sites.google.com/site/tpiezas/010 (búsqueda de J. Binet).

Por lo que parece una operación O(n^2) algoritmo puede ser posible. Tal vez el uso de este más hábilmente nos puede dar una O(n) tiempo de algoritmo.

Espero que ayude. Por favor nos informe con la solución dada por su profesor.

Answer 3

Por $O(n^2)$ (aleatoria) de tiempo, también puede utilizar una tabla hash de tamaño $\Theta(n^2)$. Buscando va a ser la constante de tiempo debido a que el número de taxis números de es $O(n^2)$.

Answer 4

Creo que se puede hacer mejor, imagínese el (a,b) pares como la formación de una matriz llena con a^3+b^3 en el triángulo superior derecho. por ejemplo, (para plazas debido a la limitación de la aritmética mental)

2, 5, 10, 17, 26
-  8, 13, 20, 29
-  -, 18, 25, 34
-  -   -  32, 41
-  -   -   -  50

Por lo que debe estar claro de esto lo que en realidad no es difícil generar los números casi en orden. Empiezo por la computación en la parte superior izquierda, y voy por las columnas hasta el final, a menos que la parte superior de la siguiente columna es mayor. Para una implementación sería algo como:

(1) el Trabajo de todos los elementos en la fila superior y la puso en la fila inferior de [N][2], Así que tendría la primera fila

[1,1,1,1,1]
[2,5,10,17,26]

Así que trato de ir "hacia abajo" de la primera fila, pero su agotado, así que me puse 2 en un int que almacena mi último valor. y yo reemplazarlo con un 0 para indicar que la columna está agotado.

[0,1,1,1,1]
[0,5,10,17,26]
lastVal=2

Así que ahora veo que el 5 es el valor más pequeño, así que creo que el 5 y el incremento de la columna. mientras que es menor que la cabeza de la columna siguiente de su todo bien, así que el primer caso interesante es

[0,0,2,1,1]
[0,0,13,17,26]

Así que cuando me tomo 13 para mi último valor, me parece que el siguiente valor es de 18 años que es mayor de 17, por lo que deben próximo 17 y el incremento de la columna. Y sigo avanzando a lo largo de incremento hasta que la lista es, una vez más, ordenados de izquierda a derecha.

Ya estoy generando en fin, yo encontrar todos los pares de inmediato (valor=último valor), y no tengo la necesidad de tener más de N valores en la memoria. En la práctica, esto es, probablemente, muy cerca de la n^2 en el tiempo, ya que no suelen tener que tomar más de una comparación por número, ya que en el final de cada paso de su ordenan de izquierda a derecha. Su complejidad actual es demasiado duro para mí, sin embargo. :)