Cómo calcular la complejidad algorítmica espacio

Question

Estoy revisando mis estructuras de datos y algoritmos de análisis lección, y me sale una pregunta que cómo determinar la complejidad del espacio combinación de tipo y rápida tipo algoritmos?

  

La profundidad de recursión sólo es O (LGN) para vinculado lista de combinación-sort

     

La cantidad de espacio de almacenamiento adicional necesario para ordenar rápida contiguos es O (n).

Mis pensamientos:

Los dos tanto para uso estrategia de divide y vencerás, así que supongo que la complejidad del espacio de lista enlazada de combinación de tipo debe ser igual a la rápida contigua sort.Actually opto por O (LGN) porque antes de cada iteración o una llamada recursividad, la lista se divide mitad.

Gracias por cualquier punteros.

Answer 1

El peor de los casos la profundidad de recursión para quicksort no es (necesariamente) O (log n), porque quicksort no divide los datos "en medio", se divide alrededor de un pivote que puede o no puede ser la mediana. Es posible llevar a cabo la clasificación rápida para hacer frente a esta [*], pero se supone que el O (n) el análisis fue de una implementación básica ordenación rápida recursiva, no una versión mejorada. Eso explicaría la discrepancia entre lo que se dice en el blockquote, y lo que se dice en "mis pensamientos".

Aparte de eso creo que su análisis es sonido -. Ni algoritmo utiliza ninguna memoria adicional que no sea una cantidad fija por cada nivel de recursividad, por lo que la profundidad de los dictados de recursión la respuesta

Otra posible manera de explicar la discrepancia, supongo, es que el O (n) análisis está mal. O bien, "ordenación rápida contigua" no es un término que he oído antes, así que si eso no quiere decir lo que yo creo que sí ( "quicksorting una matriz"), que podría implicar una clasificación rápida de que es necesariamente ineficiente espacio en algún sentido , como devuelve una matriz asignado en lugar de clasificación en el lugar. Pero sería tonto para comparar la clasificación rápida y mergesort sobre la base de la profundidad de la recursividad de la mergesort vs el tamaño de una copia de la entrada para la clasificación rápida.

[*] En concreto, en lugar de llamar a la función recursiva en ambas partes, lo pones en un bucle. Hacer una llamada recursiva en la parte más pequeña, y el lazo alrededor de hacer la parte más grande, o lo que es equivalente a empujar (punteros a) la mayor parte en una pila de trabajo que hacer después, y el lazo en torno a hacer la parte más pequeña. De cualquier manera, se asegura que la profundidad de la pila no supera nunca log n, debido a que cada trozo de trabajo no a la pila es como máximo la mitad del tamaño de la porción antes de que, a un mínimo fijo (1 o 2 si está la clasificación puramente con la clasificación rápida).

Answer 2

No estoy muy familiarizado con el término "ordenación rápida contigua". Sin embargo, la clasificación rápida puede tener ya sea O (n) u O (log n) la complejidad del espacio en función de cómo se implementa.

Si se implementa de la siguiente manera:

quicksort(start,stop) {
    m=partition(start,stop);
    quicksort(start,m-1);
    quicksort(m+1,stop);
}

A continuación, la complejidad espacio es O (n) , no O (log n) como se cree comúnmente. Esto se debe a que está empujando a la pila dos veces en cada nivel, por lo que el espacio se determina la complejidad de la recurrencia:

T(n) = 2*T(n/2)

Suponiendo que la partición divide la matriz en 2 partes iguales (mejor caso). La solución a este de acuerdo con la Maestro Teorema es T (n) = O (n).

Si reemplazamos la segunda llamada clasificación rápida con la recursión de cola en el fragmento de código anterior, entonces se obtiene T (n) = T (n / 2) y por lo tanto T (n) = O (log n) (por el caso 2 de el teorema del Maestro).

Tal vez el "quicksort contiguo" se refiere a la primera implementación porque las dos llamadas quicksort están uno junto al otro, en cuyo caso la complejidad espacio es O (n) .