¿Atado al espacio para el algoritmo de selección?

Existe un algoritmo bien conocido de selección de peor de los casos para encontrar el elemento más grande 'ésimo en una matriz de enteros. Se utiliza un medio-de-medianas enfoque para encontrar un buen pivote suficiente, particiones la matriz de entrada en su lugar y luego continúa de forma recursiva en ella de búsqueda del elemento más grande 'th. $O(n)$ $k$ $k$

¿Qué pasa si no se nos permitió tocar la matriz de entrada, la cantidad de espacio adicional sería necesaria con el fin de encontrar el -ésimo elemento más grande de tiempo? ¿Podríamos encontrar el 'ésimo elemento más grande en espacio extra y aún así mantener el tiempo de ejecución ? Por ejemplo, encontrar el elemento máximo o mínimo requiere tiempo y espacio. $k$ $O(n)$ $k$ $O(1)$ $O(n)$ $O(n)$ $O(1)$

Intuitivamente, no puedo imaginar que podríamos hacerlo mejor que el espacio , pero ¿hay alguna prueba de esto? $O(n)$

¿Puede alguien punto de referencia o llegar a un argumento por qué el -ésimo elemento requeriría el espacio que se encuentra en tiempo? $\lfloor n/2 \rfloor$ $O(n)$ $O(n)$

algorithms algorithm-analysis space-complexity lower-bounds usuario834
fuente

No soy un experto, pero tal vez estos documentos sean útiles: límites más bajos de tiempo-espacio basados en comparación para la selección y las compensaciones de espacio-tiempo y problemas de primer orden en un modelo de programas

Vor

Respuestas:

Es un problema abierto si puede hacer la selección con tiempo y celdas de memoria adicionales sin cambiar la entrada (ver aquí ). Pero puedes acercarte bastante a esto. $O(n)$ $O(1)$

Munro y Raman propusieron un algoritmo de selección que se ejecuta en tiempo mientras se usa solo almacenamiento adicional (celdas) ). Este algoritmo deja la entrada sin cambios. Puede elegir cualquier pequeño . $O(n^{1+\varepsilon})$ $O(1/\varepsilon)$ $\varepsilon>0$

En esencia, el algoritmo de Munro y Raman funciona como el algoritmo clásico : mantiene un límite izquierdo y derecho (llamado filtro ), que son dos elementos con rango conocido. El elemento solicitado está contenido entre los dos filtros (por rango). Al elegir un buen elemento de pivote podemos verificar todos los números contra los filtros y . Esto hace posible actualizar los filtros y disminuye el número de elementos que quedan por comprobar (en cuanto a rango). Repetimos hasta que hayamos encontrado el elemento de solicitud. $O(n)$ $p$ $p$

Lo que es diferente al algoritmo clásico es la elección de . Sea el algoritmo que resuelve la selección para . El algoritmo divide la matriz en bloques de igual tamaño e identifica un bloque donde hay muchos elementos, cuyos rangos se encuentran entre los filtros (existencia por principio de agujero de paloma). Este bloque será escaneado en busca de un buen elemento pivote con la ayuda del algoritmo . El ancla de recursión es el algoritmo trivial . El tamaño de bloque correcto (y hacer los cálculos) le da tiempo de ejecución y requisitos de espacio como se indicó anteriormente. $p$ $A(k)$ $\varepsilon=1/k$ $A(k)$ $A(k-1)$ $A(1)$

Por cierto, los algoritmos que estás buscando fueron recientemente nombrados algoritmos de espacio de trabajo constante .

No conozco ningún límite inferior.

A.Schulz
fuente