example - quicksort java netbeans

¿Por qué QuickSort utiliza espacio adicional O(log(n))?

Question

He implementado el siguiente algoritmo de ordenación rápida. En línea he leído que tiene un requisito de espacio de O (log (n)). ¿Por qué es este el caso? No estoy creando ninguna estructura de datos extra.

¿Es porque mi recursión usará un poco de espacio extra en la pila? Si este es el caso, ¿es posible hacerlo con menos memoria al no tener que ser recursivo (en lugar de hacerlo iterativo)?

private static void quickSort (int[] array, int left, int right) {
    int index = partition(array, left, right);

    //Sort left half
    if (left < index - 1)
        quickSort(array, left, index - 1);

    //Sort right half
    if (index < right)
        quickSort(array, index , right);
}

private static int partition (int array[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on right
        while (array[left] < pivot)
            left++;

        //Find element on right that should be on left
        while (array[right] > pivot)
            right--;

        //Swap elements and move left and right indices
        if (left <= right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}

Answer 1

Correcto, el espacio extra son los marcos de la pila de registro (n). Del artículo de Wikipedia de Quicksort :

Hay una versión más compleja que utiliza un algoritmo de partición en el lugar y puede lograr la clasificación completa utilizando el espacio O (log n) (sin contar la entrada) en promedio (para la pila de llamadas) .

Si bien puede implementar iterativamente quicksort (es decir, usar un bucle en lugar de recursión), entonces necesitará mantener una pila auxiliar, porque Quicksort tiene dos llamadas recursivas y no solo una.

Finalmente, como han señalado otras respuestas, O (log (n)) es para casi todas las aplicaciones prácticas muy, muy pequeño. Cada factor constante, como la sobrecarga de su estructura de datos, tendrá un mayor impacto en el uso de la memoria.

Answer 2

Para deshacerse de la llamada recursiva, tendría que usar una pila en su código, y aún así ocuparía espacio de log(n) .

Answer 3

Perdón por revivir esta vieja pregunta, pero acabo de encontrar una respuesta completamente diferente (pero un poco tonta) a tu pregunta, en planetmath.org :

Cualquier algoritmo de clasificación que opere en una matriz contigua requiere O ⁢ (log ⁡n ) espacio adicional, ya que este es el número de bites [ sic ] requerido para representar un índice en la matriz.

Answer 4

Sí, es debido a los marcos de pila, y sí, puede ser posible convertirlo en un algoritmo iterativo haciendo algo muy inteligente (aunque nada me viene de inmediato). ¿Pero por qué? El espacio O (log (n)) es casi nada. Para referencia, incluso si tiene una matriz del tamaño máximo permitido por Java, eso es 2 ^ 31 elementos, que es aproximadamente 8 GB. Quicksort requeriría 31 marcos de pila. ¿Estadio de béisbol, tal vez 100 bytes por cuadro? Por lo tanto, un total de 3 KB, que no es nada en comparación con la memoria de la matriz real.

En realidad, casi siempre que algo es O (log (n)), es casi lo mismo que constante.

Answer 5

Si sigue leyendo en el artículo de Wikipedia, encontrará una discusión más detallada sobre la complejidad del espacio . En particular, escriben:

La ordenación rápida con partición inestable e in situ utiliza solo un espacio adicional constante antes de realizar una llamada recursiva. Quicksort debe almacenar una cantidad constante de información para cada llamada recursiva anidada. Dado que el mejor de los casos hace un máximo de O (registro n) llamadas recursivas anidadas, utiliza el espacio O (registro n). Sin embargo, sin el truco de Sedgewick para limitar las llamadas recursivas, en el peor de los casos, quicksort podría hacer O (n) llamadas recursivas anidadas y necesitar espacio auxiliar O (n).

En la práctica, la memoria O (log n) no es nada. Por ejemplo, si tuviera que ordenar 1 mil millones de ints, almacenarlos requeriría 4 GB, pero la pila solo requeriría unos 30 cuadros de pila, en algo así como 40 bytes, así que aproximadamente 1200 bytes en total.