algorithm - ¿Por qué el algoritmo de mediana de medianas se describe como un espacio auxiliar O(1)?

recursion space-complexity

Question

Wikipedia enumera el algoritmo de mediana de medianas que requiere espacio auxiliar O(1) .

Sin embargo, en medio del algoritmo, hacemos una llamada recursiva en un subarreglo de tamaño n/5 para encontrar la mediana de las medianas. Cuando esta llamada recursiva regresa, usamos la mediana devuelta de las medianas como un pivote para particionar la matriz.

¿Este algoritmo no empuja los registros de activación O(lg n) en la pila de tiempo de ejecución como parte de la recursión? Por lo que puedo ver, estas llamadas recursivas para encontrar medianas sucesivas de medianas no pueden ser optimizadas para llamadas de cola porque hacemos un trabajo extra después del retorno de las llamadas recursivas. Por lo tanto, parece que este algoritmo requiere espacio auxiliar O(lg n) (al igual que Quicksort, que Wikipedia considera como espacio auxiliar O(lg n) debido al espacio utilizado por la pila de tiempo de ejecución).

¿Me estoy perdiendo algo, o está mal el artículo de Wikipedia?

(Nota: la llamada recursiva a la que me estoy refiriendo es return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) en la página de Wikipedia).

Answer 1

Es O (1).

Digamos que comenzamos con una matriz de longitud n, y pretendemos encontrar el elemento kth de la lista ordenada.

Después de la primera llamada, la mediana de medianas emitirá una matriz más pequeña, ahora debemos evaluar el elemento i de esta matriz más pequeña. Tenga en cuenta que el resultado es el elemento i de esta matriz más pequeña, por lo que no necesito devolver ninguna información a la llamada anterior.

En la clasificación rápida, necesito volver a colocar los arreglos pequeños ordenados en la posición correcta para que se produzca la recursión. Con la mediana de las medianas, después del bucle (recursión de la cola), me quedará con la respuesta.

Profundidad de recursión = O (1)

Answer 2

Si bien no puedo descartar que O (1) sea posible, la información de Wikipedia parece ser un error.

• La implementación que se muestra allí toma O (log n) y no solo O (1).
• No es absolutamente obvio cómo implementarlo con O (1) y no hay explicación / referencia para ello.
• Le pregunté al autor que originalmente agregó esa información y él respondió que no recuerda y que probablemente sea un error.
• Un documento del 2005 dedicado a resolver el problema de selección con O (n) tiempo y O (1) espacio adicional dice que BFPRT (también conocida como Mediana de Medianas) usa space (log n) espacio adicional. Por otro lado, el resultado principal del documento es que O (n) tiempo y O (1) espacio adicional es posible, y uno de los dos algoritmos presentados como prueba es alguna "emulación" de BFPRT. Entonces, en ese sentido, es posible, pero creo que la emulación lo convierte en un algoritmo diferente y el O (1) no debe atribuirse al BFPRT "regular". Al menos no sin explicación.
  (Gracias a Yu-HanLyu por mostrar ese documento y más en los comentarios)