Quicksort a menudo se describe como in situ (in situ) algoritmo, a pesar de que requiere O (log n) espacio de pila. Entonces, ¿in situ significa "requiere menos de O (n) espacio adicional", o el espacio de pila generalmente no cuenta como complejidad de espacio (pero ¿por qué sería ese el caso?) O no es in situ ¿algoritmo?Es imprescindible Quicksort in situ (en el lugar) o no?
¿Quicksort realmente no es un algoritmo in situ?
La implementación estándar de ella es no in situ. Es un concepto erróneo terriblemente común, pero usted nota correctamente debido al consumo de espacio en la pila, esa concepción es incorrecta.
Digo "implementación estándar" porque la gente ha modificado el algoritmo para convertirlo en un algoritmo de espacio O(1). Aquí hay un ejemplo: Quicksort without a stack.
Por supuesto, en consonancia con el clásico space-time tradeoff, dichas versiones de quicksort son menos efectivas que la implementación estándar.
Wikipedia ofrece la siguiente definition:
En informática, un algoritmo en el lugar (o en América in situ) es un algoritmo que transforma entrada utilizando una estructura de datos con una cantidad pequeña, constante de espacio de almacenamiento adicional.
Por esta definición, el quicksort típico basado en la pila no es claramente un in situ algoritmo.
De hecho, el artículo de Wikipedia discute explícitamente:
Un algoritmo es a veces llamado informalmente en el lugar con tal de que sobrescribe su entrada con su salida. En realidad, esto no es suficiente (como demuestra el caso del quicksort) ni es necesario; el espacio de salida puede ser constante o incluso no contabilizarse, por ejemplo, si la salida es para una transmisión.
y
Quicksort se describe comúnmente como un algoritmo en el lugar, pero no es de hecho uno. La mayoría de las implementaciones requieren espacio O (log n) para soportar su división y conquistar la recursión.
Sin embargo, como señaló @Jason en su excelente respuesta, parece que existen variantes de quicksort que solo requieren O (1) espacio extra. Cualquiera de tales aloritmos se consideraría in situ.
Esta pregunta se ha realizado antes: http://cstheory.stackexchange.com/q/9563/6586. Básicamente, es más bien un cebo de fuego con muchos argumentos contradictorios. – jpalecek
Tenga en cuenta que esto realmente depende de cómo desee * in-situ * para ser definido.Si solo comparas los algoritmos de clasificación, sería muy quisquilloso no considerar el quicksort en su lugar, pero si tienes en mente una definición más formal (con suerte con una razón), entonces tiene sentido dejar de ignorar el pequeño detalle O (log n) . – hugomg
Este es solo un caso especial de "O (log n) bien podría ser una constante más bien grande", ¿no es así? En principio, Quicksort usa O (log n) espacio adicional. En la práctica, generalmente lo implementa para tomar algo como una matriz como parámetro. Las matrices en la mayoría de los lenguajes tienen un límite de tamaño natural natural en función del tipo de ancho fijo utilizado para la dirección y/o los índices, y Quicksort solo necesita almacenar un par de direcciones en cada una de las profundidades de 'log n'. Así que el uso de la pila está limitado de forma constante para casi cualquier implementación de Quicksort que alguna vez escribas y uses, aunque no sea para la versión "ideal". –