¿Cómo puede la construcción de un montón tener una complejidad de tiempo O (n)?
¿Alguien puede ayudar a explicar cómo la construcción de un montón puede tener una complejidad O (n) ?
Insertar un elemento en un montón es O(log n) y la inserción se repite n/2 veces (el resto son hojas y no pueden violar la propiedad del montón). Entonces, esto significa que la complejidad debería ser O(n log n) , creo.
En otras palabras, para cada elemento que "acumulamos", tiene el potencial de tener que filtrar hacia abajo (es decir, tamizar) una vez para cada nivel del montón hasta el momento (que es log n niveles).
¿Qué me estoy perdiendo?
Creo que hay varias preguntas enterradas en este tema:
- ¿ Cómo se implementa
buildHeappara que se ejecute en tiempo O(n) ? - ¿Cómo se muestra que
buildHeapse ejecuta en tiempo O(n) cuando se implementa correctamente? - ¿Por qué esa misma lógica no funciona para hacer que la clasificación del montón se ejecute en tiempo O(n) en lugar de O(n log n) ?
¿ Cómo se implementa buildHeappara que se ejecute en tiempo O(n) ?
A menudo, las respuestas a estas preguntas se centran en la diferencia entre siftUpy siftDown. Hacer la elección correcta entre siftUpy siftDownes fundamental para obtener el rendimiento O(n) para buildHeap, pero no ayuda a comprender la diferencia entre buildHeapy heapSorten general. De hecho , las implementaciones adecuadas de ambos buildHeapy soloheapSort utilizarán . La operación solo es necesaria para realizar inserciones en un montón existente, por lo que se usaría para implementar una cola de prioridad usando un montón binario, por ejemplo.siftDownsiftUp
Escribí esto para describir cómo funciona un montón máximo. Este es el tipo de montón que normalmente se utiliza para la clasificación del montón o para una cola de prioridad donde los valores más altos indican una prioridad más alta. Un montón mínimo también es útil; por ejemplo, al recuperar elementos con claves enteras en orden ascendente o cadenas en orden alfabético. Los principios son exactamente los mismos; simplemente cambie el orden de clasificación.
La propiedad del montón especifica que cada nodo en un montón binario debe ser al menos tan grande como sus dos hijos. En particular, esto implica que el elemento más grande del montón está en la raíz. Examinar hacia abajo y hacia arriba son esencialmente la misma operación en direcciones opuestas: mover un nodo infractor hasta que satisfaga la propiedad del montón:
siftDownintercambia un nodo que es demasiado pequeño con su hijo más grande (moviéndolo así hacia abajo) hasta que sea al menos tan grande como los dos nodos debajo de él.siftUpintercambia un nodo que es demasiado grande con su padre (moviéndolo así hacia arriba) hasta que no sea más grande que el nodo que está encima de él.
El número de operaciones requeridas para siftDowny siftUpes proporcional a la distancia que el nodo puede tener que moverse. Para siftDown, es la distancia hasta la parte inferior del árbol, por lo que siftDownes costoso para los nodos en la parte superior del árbol. Con siftUp, el trabajo es proporcional a la distancia hasta la cima del árbol, por lo que siftUpes costoso para los nodos en la parte inferior del árbol. Aunque ambas operaciones son O (log n) en el peor de los casos, en un montón, solo un nodo está en la parte superior, mientras que la mitad de los nodos se encuentran en la capa inferior. Por lo tanto, no debería sorprendernos que si tenemos que aplicar una operación a cada nodo, prefiramos siftDownhacerlo en lugar de siftUp.
La buildHeapfunción toma una serie de elementos sin clasificar y los mueve hasta que todos satisfacen la propiedad del montón, produciendo así un montón válido. Hay dos enfoques que se pueden adoptar para buildHeaputilizar las operaciones siftUpy siftDownque hemos descrito.
Comience en la parte superior del montón (el comienzo de la matriz) y llame
siftUpa cada elemento. En cada paso, los elementos previamente tamizados (los elementos anteriores al elemento actual en la matriz) forman un montón válido, y al tamizar el siguiente elemento se coloca en una posición válida en el montón. Después de examinar cada nodo, todos los elementos satisfacen la propiedad del montón.O vaya en la dirección opuesta: comience en el final de la matriz y avance hacia el frente. En cada iteración, tamizas un elemento hasta que esté en la ubicación correcta.
¿ Qué implementación buildHeapes más eficiente?
Ambas soluciones producirán un montón válido. Como era de esperar, la más eficiente es la segunda operación que utiliza siftDown.
Sea h = log n la altura del montón. El trabajo requerido para el siftDownenfoque está dado por la suma
(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).
Cada término de la suma tiene la distancia máxima que tendrá que moverse un nodo en la altura dada (cero para la capa inferior, h para la raíz) multiplicada por el número de nodos en esa altura. Por el contrario, la suma para llamar siftUpa cada nodo es
(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).
Debe quedar claro que la segunda suma es mayor. El primer término por sí solo es hn/2 = 1/2 n log n , por lo que este enfoque tiene, en el mejor de los casos, una complejidad O(n log n) .
¿Cómo demostramos que la suma del siftDownenfoque es efectivamente O(n) ?
Un método (hay otros análisis que también funcionan) es convertir la suma finita en una serie infinita y luego usar la serie de Taylor. Podemos ignorar el primer término, que es cero:
Si no está seguro de por qué funciona cada uno de esos pasos, aquí tiene una justificación del proceso en palabras:
- Todos los términos son positivos, por lo que la suma finita debe ser menor que la suma infinita.
- La serie es igual a una serie de potencias evaluada en x=1/2 .
- Esa serie de potencias es igual a (una constante multiplicada por) la derivada de la serie de Taylor para f(x)=1/(1-x) .
- x=1/2 está dentro del intervalo de convergencia de esa serie de Taylor.
- Por lo tanto, podemos reemplazar la serie de Taylor con 1/(1-x) , derivar y evaluar para encontrar el valor de la serie infinita.
Dado que la suma infinita es exactamente n , concluimos que la suma finita no es mayor y, por lo tanto, es O(n) .
¿ Por qué la clasificación del montón requiere tiempo O (n log n) ?
Si es posible ejecutar buildHeapen tiempo lineal, ¿por qué la clasificación en montón requiere un tiempo O (n log n) ? Bueno, la clasificación en montón consta de dos etapas. Primero, invocamos buildHeapla matriz, que requiere O(n) tiempo si se implementa de manera óptima. El siguiente paso es eliminar repetidamente el elemento más grande del montón y colocarlo al final de la matriz. Debido a que eliminamos un elemento del montón, siempre hay un lugar abierto justo después del final del montón donde podemos almacenar el elemento. Por lo tanto, la clasificación en montón logra un orden de clasificación eliminando sucesivamente el siguiente elemento más grande y colocándolo en la matriz comenzando en la última posición y moviéndose hacia el frente. Es la complejidad de esta última parte la que domina en la clasificación en montón. El bucle se ve así:
for (i = n - 1; i > 0; i--) {
arr[i] = deleteMax();
}
Claramente, el bucle se ejecuta O(n) veces ( n - 1 para ser precisos, el último elemento ya está en su lugar). La complejidad de deleteMaxun montón es O(log n) . Por lo general, se implementa eliminando la raíz (el elemento más grande que queda en el montón) y reemplazándolo con el último elemento del montón, que es una hoja y, por lo tanto, uno de los elementos más pequeños. Es casi seguro que esta nueva raíz violará la propiedad del montón, por lo que debe llamar siftDownhasta que la mueva nuevamente a una posición aceptable. Esto también tiene el efecto de mover el siguiente elemento más grande hasta la raíz. Observe que, a diferencia de buildHeapdonde llamamos para la mayoría de los nodos siftDowndesde la parte inferior del árbol, ahora llamamos siftDowndesde la parte superior del árbol en cada iteración. Aunque el árbol se está reduciendo, no lo hace lo suficientemente rápido : la altura del árbol permanece constante hasta que haya eliminado la primera mitad de los nodos (cuando limpie la capa inferior por completo). Luego, para el siguiente trimestre, la altura es h - 1 . Entonces el trabajo total para esta segunda etapa es
h*n/2 + (h-1)*n/4 + ... + 0 * 1.
Observe el cambio: ahora el caso de trabajo cero corresponde a un solo nodo y el caso de trabajo h corresponde a la mitad de los nodos. Esta suma es O (n log n) al igual que la versión ineficiente buildHeapque se implementa usando siftUp. Pero en este caso, no tenemos otra opción ya que estamos intentando ordenar y requerimos que se elimine el siguiente elemento más grande.
En resumen, el trabajo para la clasificación del montón es la suma de las dos etapas: O(n) tiempo para buildHeap y O(n log n) para eliminar cada nodo en orden , por lo que la complejidad es O(n log n) . Puede demostrar (utilizando algunas ideas de la teoría de la información) que para una clasificación basada en comparación, O(n log n) es lo mejor que podría esperar de todos modos, por lo que no hay razón para sentirse decepcionado por esto o esperar que la clasificación en montón logre el objetivo. O (n) con límite de tiempo, eso buildHeapsí.
Tu análisis es correcto. Sin embargo, no es ajustado.
No es realmente fácil explicar por qué construir un montón es una operación lineal; será mejor que lo leas.
Se puede ver un gran análisis del algoritmo aquí .
La idea principal es que en el build_heapalgoritmo el coste real heapifyno es O(log n)para todos los elementos.
Cuando heapifyse llama, el tiempo de ejecución depende de qué tan lejos podría descender un elemento en el árbol antes de que finalice el proceso. En otras palabras, depende de la altura del elemento en el montón. En el peor de los casos, el elemento podría descender hasta el nivel de la hoja.
Contemos el trabajo realizado nivel por nivel.
En el nivel más bajo, hay 2^(h)nodos, pero no invocamos heapifyninguno de ellos, por lo que el trabajo es 0. En el siguiente nivel hay 2^(h − 1)nodos, y cada uno puede bajar 1 nivel. En el tercer nivel desde abajo, hay 2^(h − 2)nodos, y cada uno puede bajar 2 niveles.
Como puede ver, no todas las operaciones de heapify lo son O(log n), es por eso que obtiene O(n).
Intuitivamente:
"La complejidad debe ser O(nLog n)... para cada elemento que "acumulamos", tiene el potencial de tener que filtrarse hacia abajo una vez para cada nivel del montón hasta el momento (que es log n niveles)".
No exactamente. Su lógica no produce un límite estricto: sobreestima la complejidad de cada montón. Si se construye de abajo hacia arriba, la inserción (heapify) puede ser mucho menor que O(log(n)). El proceso es el siguiente:
(Paso 1) Los primeros n/2elementos van en la fila inferior del montón. h=0, por lo que no es necesario heapify.
(Paso 2) Los siguientes elementos van en la fila 1 desde abajo. , amontonar filtros 1 nivel hacia abajo.n/22h=1
( Paso i )
Los siguientes elementos van en fila desde abajo. , apila los niveles de los filtros hacia abajo.n/2iih=ii
( Paso log(n) ) El último elemento va en fila desde abajo. , apila los niveles de los filtros hacia abajo.n/2log2(n) = 1log(n)h=log(n)log(n)
AVISO: que después del paso uno, 1/2algunos de los elementos (n/2)ya están en el montón y ni siquiera necesitamos llamar a heapify una vez. Además, observe que solo un elemento, la raíz, en realidad adquiere toda la log(n)complejidad.
Teóricamente:
El total de pasos Npara construir un montón de tamaño nse puede escribir matemáticamente.
En altura i, hemos mostrado (arriba) que habrá elementos que deberán llamar a heapify, y sabemos que heapify en altura es . Esto da:n/2i+1iO(i)
La solución a la última suma se puede encontrar tomando la derivada de ambos lados de la conocida ecuación en serie geométrica:
Finalmente, al introducir x = 1/2la ecuación anterior se obtiene 2. Introduciendo esto en la primera ecuación se obtiene:
Por tanto, el número total de pasos es del tamañoO(n)
Ya hay algunas respuestas excelentes, pero me gustaría agregar una pequeña explicación visual.
Ahora, fíjate en la imagen, hay
n/2^1 nodos verdes con altura 0 (aquí 23/2 = 12)
n/2^2 nodos rojos con altura 1 (aquí 23/4 = 6)
n/2^3 nodos azules con altura 2 (aquí 23/8 = 3)
n/2^4 nodos morados con altura 3 (aquí 23/16 = 2)
, por lo que hay n/2^(h+1)nodos para altura h
. Para encontrar la complejidad del tiempo, cuentemos la cantidad de trabajo realizado o el número máximo de iteraciones realizadas por cada nodo
. Ahora se puede notar que cada nodo puede realizar (como máximo) iteraciones == altura del nodo
Green = n/2^1 * 0 (no iterations since no children)
red = n/2^2 * 1 (heapify will perform atmost one swap for each red node)
blue = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)
entonces, para cualquier nodo con altura h, el trabajo máximo realizado es n/2^(h+1) * h
Ahora el trabajo total realizado es
->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )
ahora para cualquier valor de h , la secuencia
-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )
nunca excederá 1.
Por lo tanto, la complejidad del tiempo nunca excederá O(n) para construir el montón.
