disyuntiva tiempo-espacio para el problema elemento que falta

Question

Aquí es un problema bien conocido.

Dado un array $ A [1 \ dots n] $ de enteros positivos, la salida el número entero positivo más pequeño no en la matriz.

El problema puede ser resuelto en $ O (n) $ espacio y el tiempo: leer la matriz, no perder en $ O (n) $ espacio si $ 1,2, \ dots, n + 1 $ se produjo, de exploración para los más pequeños elemento.

Me di cuenta de que usted puede negociar el espacio de tiempo. Si usted tiene $ O (\ frac {n} {k}) sólo $ memoria, puede hacerlo en $ $ k rondas y obtener el tiempo $ O (k N) $. En un caso especial, es evidente que existe constante en el espacio algoritmo de tiempo cuadrática.

Mi pregunta es:

Es este el equilibrio óptimo, es decir, hace $ \ operatorname {hora} \ cdot \ operatorname {espacio} = \ Omega (n ^ 2) $? En general, ¿cómo se puede probar este tipo de límites?

Supongamos modelo RAM, con la aritmética acotado y de acceso aleatorio a las matrices en O (1).

Inspiración para este problema: compensación de tiempo-espacio para palíndromos en el modelo de una sola cinta (véase, por ejemplo, aquí ).

Answer 1

Esto se puede hacer en $ O (n \ log n) $ operaciones de palabras y $ O (1) $ palabras de memoria (respectivamente $ O (n \ log ^ 2 n) $ tiempo y $ O (\ log n) $ memoria RAM en el modelo a nivel de bit). De hecho, la solución se basa en la siguiente observación.

dicen que hay $ n_0 $ uniforme y $ n_1 $ los números impares en el rango $ [1, n + 1] $ (de modo $ n_0 \ aprox n_1 $ y $ n_0 + n_1 = n + 1 $ ). Luego está $ b \ in \ {0, 1 \} $ tal que hay a lo sumo $ n_b - 1 $ valores con la paridad $ b $ en la entrada. De hecho, si no hay al menos $ n_0 $ uniforme y al menos $ n_1 $ valores impares en la entrada , lo que significa que hay por lo menos $ n_0 + n_1 = n + 1 $ valores en la entrada, la contradicción (sólo hay $ n $ de ellos). Esto significa que podemos continuar la búsqueda de desaparecidos número sólo entre sólo los números pares o impares. El mismo algoritmo se puede aplicar a los bits más altos de notación binaria también.

Así que nuestro algoritmo se parecerá a lo siguiente:

1. Supongamos que ya ahora que sólo hay $ x $ valores en la entrada con el resto de módulo $ 2 ^ b $ siendo igual a $ r \ in [0, 2 ^ b) $ pero hay al menos $ x + 1 $ números en el rango de $ [1, n + 1] $ que tienen clase resto $ r $ módulo $ 2 ^ $ b (en el inicio sabemos que de seguro para $ b = 0, r = 0 $ ).

2. dicen que hay $ x 0 $ valores en la entrada con el resto $ r $ módulo $ 2 ^ {b + 1} $ y $ x_1 $ valores en la entrada con resto <= span class "matemáticas-contenedor"> $ r + 2 ^ b $ módulo $ 2 ^ {b + 1} $ (podemos encontrar estos números en una sola pasada a través de la entrada). Claramente, $ x 0 + x 1 = x $ . Además, dado que hay al menos $ x + 1 $ números en la entrada con resto $ r $ modulo $ 2 ^ b $ , al menos uno de los pares $ (r, b + 1), (r + 2 ^ b , b + 1) $ satisface los requisitos de la etapa $ 1 $ .

3. Hemos encontrado el número que falta al $ 2 ^ b \ geqslant n + 1 $ : sólo hay un número en el rango $ [1, n + 1] $ que puede tener resto $ r $ módulo $ 2 ^ b $ ( $ r $ a sí mismo si está en el rango), por lo que hay a lo sumo valores cero en la entrada que tienen tales resto. Así $ r $ falta de hecho.

Claramente, se detiene la algoritmo en el $ O (\ log n) $ pasos, cada uno de ellos necesita $ O ( n) $ tiempo (de una sola pasada sobre la matriz de entrada). Además, sólo $ O (1) $ se requieren palabras de memoria.

Answer 2

Si entiendo sus definiciones, esto se puede hacer en un tiempo lineal con un espacio constante. Esto es obviamente la más baja obligada, porque necesitamos al menos leer la entrada completa.

La respuesta dada en satisface esta pregunta .

Es imposible ejecutar esta con menos tiempo o en el espacio, y la adición de más tiempo o espacio no sirve para nada, así que no hay espacio-tiempo desventaja aquí. (Observe que $ n = O (n / k) $, por lo que la solución de compromiso que ha observado no se sostiene asintóticamente, en cualquier caso.)

En cuanto a su pregunta en general, no sé de ningún teoremas agradables improvisada que le ayudará a probar soluciones de compromiso espacio-tiempo. Esta pregunta parece indicar que no hay una ( conoce) una respuesta fácil. Básicamente:

Supongamos que un lenguaje es decidible en el tiempo t $ $ (con una cierta cantidad de espacio) y $ s $ espacio (utilizando una cierta cantidad de tiempo). Podemos encontrar $ f, g $ tal que $ L $ es decidible por $ M $ que se ejecuta en $ f (t, s) $ $ y el tiempo g (t, s) $ espacial?

es desconocido, y una respuesta fuerte resolvería muchos problemas abiertos (sobre todo acerca SC), lo que implica que no existe una solución fácil.

---

EDIT: Ok, con la repetición (pero todavía estoy suponiendo que con una entrada de tamaño n $ $ el número máximo posible es $ n + 1 $).

Tenga en cuenta que nuestras necesidades algoritmo para poder diferenciar entre, al menos, $ n $ posibles respuestas. Supongamos que en cada paso por los datos que podemos conseguir en la mayoría de los $ k $ piezas de datos. Entonces necesitaremos $ n / k $ pasa a diferenciar todas las respuestas. Suponiendo $ k = N / S $ corremos en $ \ frac {n} {N / S} n = sn $ tiempo. Así que creo que esto demuestra lo que quiere.

La dificultad está en que muestra que cada vez que a través de obtener sólo $ k bits de $. Si se supone que nuestra única operación legal es =, entonces estamos bien. Sin embargo, si se permite que las operaciones más complejas, entonces usted será capaz de obtener más información.