algorithm - explicacion - ¿Quicksort está en el lugar o no?
quicksort explicacion (4)
Esta pregunta ya tiene una respuesta aquí:
- ¿Es imperativo Quicksort in situ (in situ) o no? 2 respuestas
Entonces, la eficiencia de espacio de Quicksort es O (log (n)). Este es el espacio requerido para mantener la pila de llamadas.
Ahora, de acuerdo con la página de Wikipedia en Quicksort , esto califica como un algoritmo in situ, ya que el algoritmo simplemente está intercambiando elementos dentro de la estructura de datos de entrada.
Sin embargo, de acuerdo con esta página , la eficiencia de espacio de O (log n) descalifica a Quicksort de estar en su lugar, ya que la eficiencia de espacio es mayor que O (1). De acuerdo con esta definición, cualquier algoritmo con una eficiencia de espacio mayor que O (1) no está en su lugar. ¿Supongo que esto significa que todos los algoritmos recursivos no están, por definición, en su lugar?
Así que obviamente hay dos definiciones diferentes de in situ aquí. Wikipedia no siempre es una fuente totalmente confiable, por lo que consulté con uno de mis profesores.
Mi profesor estuvo de acuerdo con la segunda definición. Dijo que Quicksort no está en el lugar. Aunque los datos permanecen en la matriz de entrada, el espacio adicional necesario para la pila lo descalifica. Mi profesor escribió un libro popular sobre Algoritmos, así que respeto mucho su opinión, pero esta respuesta no me parece correcta.
Veo la propiedad de en el lugar como bastante literal. Los datos se mantienen en su lugar. No se mueve desde su estructura de datos original. Para mí, esta definición es más útil, porque significa que puede realizar su algoritmo con punteros en lugar de requerir que copie datos. Esto parece una propiedad valiosa de un algoritmo y es digna del nombre "en el lugar".
Hablando estrictamente, Quicksort tiene una eficiencia de espacio de O (n) ya que el caso degenerado requeriría un índice en la pila para cada elemento de la matriz. Aunque en promedio será O (log (n)). Dado que no creo que exista alguna forma de que pueda llamarlo un algoritmo "en el lugar", a menos que vaya con una definición degenerada de "en el lugar", lo que significa que los datos originales no se almacenan fuera de los límites de la matriz original (excluyendo operaciones de copia / intercambio).
Esta definición de "en el lugar" sería degenerada porque usted podría tomar cualquier algoritmo "fuera de lugar" y hacerlo cumplir con el requisito "en su lugar" haciendo que todos los punteros de uso de almacenamiento de datos adicionales a la matriz original. Luego, cuando se encuentra la respuesta, puede reordenar la matriz original "en su lugar" utilizando los datos del puntero.
Todo depende de la definición del algoritmo "in situ".
Si define "en el lugar" como que requiere una cantidad constante de memoria, quicksort no es "en el lugar", ya que requiere memoria de registro (N) para la recursión.
Si define "en el lugar" como más amigable para el ser humano "no mueve los datos fuera de la estructura de entrada", entonces Quicksort de nuevo no es "en el lugar". Los datos se filtran a la memoria en forma de índices con los que se invoca el método quicksort, que son necesarios para que funcione el algoritmo. El contenido de esta memoria adicional depende directamente de la entrada, ¿cómo no tiene fugas?
Si define "in situ" como no copia, entonces, ¿qué pasa con un algoritmo estúpido para encontrar una suma de una matriz: cree otra matriz de longitud (n - 1) con elementos como b [i] = a [i + 1 ] + a [0] / n. Esto es un poco de copia, aunque el contenido es diferente, pero el contenido de esta memoria adicional es una función de los datos de entrada, al igual que los índices mantenidos en la pila en el algoritmo de ordenación rápida.
Creo que la definición de wikipedia de "en el lugar" es la más útil, y de acuerdo con esto, la ordenación rápida no es "en el lugar", ya que utiliza una cantidad de memoria no constante.
qsort de hecho intercambia datos en su lugar, pero el espacio de pila utilizado para la recursión está en el registro 2 (N).
Estas dos propiedades no son contradictorias. Por lo general, "en su lugar" se refiere a la memoria del montón, es decir, lo que debe asignar explícitamente para que el algoritmo funcione.
Sin embargo, la complejidad de un espacio logarítmico es básicamente despreciable, excepto en casos patológicos (supongamos que desea hacer una ordenación rápida en un microcontrolador de 8 bits con 512 bytes de pila :)).
Intro to Algorithms from MIT Press califica a QuickSort como in situ : ordena los elementos dentro de la matriz con una cantidad constante de ellos fuera de la matriz en un momento dado.
Al final del día, las personas siempre tendrán opiniones diferentes (¿se considera la Memoria de arriba hacia abajo como Programación dinámica? No para algunas personas "clásicas"), del lado de quien más confías. Confío en los editores y los autores de MIT Press (junto con mi profesor, que lo califica como "en el lugar").
Por lo general, el problema con QuickSort no es que no se clasifique en el lugar, sino que no es estable : los datos de satélite no se mantienen en orden.
Editar
El punto de Kuroi resalta parte de este argumento, creo que es muy importante.
Muchos argumentan que requiere O (log (n)) memoria adicional para llamadas recursivas y que los datos se filtran en forma de los índices en la pila, sin embargo, esto es insignificante para tamaños muy grandes de N (log (1,000,000,000) = ~ 30 ) e ignora el hecho de que, por lo general, mover datos en el montón lleva mucho, mucho más tiempo, cuando tamaño (datos) >> tamaño (índice).
Los índices de los datos no son los elementos en sí mismos, por lo que los elementos de los datos no se almacenan fuera de la matriz, excepto una cantidad constante de ellos (en cada llamada).