¿Cuál es un ejemplo de un montón que requiere exactamente n * log (n) pasos? Sé que el límite superior de un montón es O (n log n), pero ¿cómo hago para mostrar un ejemplo donde requiera exactamente n * log (n) pasos?

En realidad, no sabía mucho sobre el montón en particular antes de leer esta pregunta, pero creo que puedo dar una respuesta.

Si está solicitando una entrada específica que le dé O (nlogn), normalmente se le puede dar una lista ordenada inversa, ya que esto garantiza que cada elemento se tocará durante la ordenación.

En cuanto a por qué el tiempo de ejecución es O (nlogn): heapsort es una ordenación de inserción mejorada y, como tal, mantiene una lista ordenada y no ordenada a medida que avanza. Su mejora proviene del hecho de que mantiene todos los elementos no ordenados en un montón (qué tipo de montón depende de cómo desea ordenar). Suponiendo que desea ordenar en orden ascendente, puede comenzar en el último elemento de la lista y llamar a delete-max desde un montón máximo, dándole el último elemento de la lista. Luego puede repetir, moviendo el puntero hacia adelante y disminuyendo el tamaño del montón, hasta que se ordene la lista.

Si luego comprende el algoritmo, el tiempo de ejecución se vuelve obvio. Para ordenar la lista completa, debe iterar sobre cada elemento de la lista: O (n) donde n es el tamaño de la lista. Para eliminar un elemento del montón, debe llamar a delete-max (o min) en el montón, que al usar un montón de Fibonacci [1] da como resultado O (logn).

Dado que está eliminando un elemento del montón durante el proceso de iteración sobre cada elemento, debe multiplicar los tiempos de ejecución, lo que le proporciona su tiempo de ejecución final de O (nlogn).

Notas al pie

[1] Montón de Fibonacci – Wikipedia

Su pregunta es problemática en varios aspectos:

• dices * pasos * sin especificar cuáles. Estos podrían ser comparaciones, movimientos u operaciones auxiliares (cálculos de índice).
• O (n log n) no significa que el número de operaciones puede ser exactamente n log n. Simplemente significa que no supera algunos múltiplos de n log n.
• en particular, si cuenta las comparaciones más los movimientos más las operaciones auxiliares, el total siempre es mayor que n log n.
• no hay un solo Heapsort, hay variantes que difieren en detalles pequeños, pero de tal manera que el recuento de operaciones también difiere. Por lo tanto, debe proporcionar el código (pseudo) del algoritmo.
• finalmente, Heapsort tiene dos fases, y establecer los recuentos exactos es técnicamente bastante arduo. Entonces, para el n general, supongo que encontrar configuraciones adecuadas es una tarea terrible. El enfoque de “fuerza bruta” de Mark Gritter es agradable, pero solo proporciona configuraciones para n particular, no una regla general, y no es aplicable para n grande (digamos n> 20).

O (NLogN) excluye algunas cosas que afectan el tiempo de ejecución. Es una generalización del aumento del tiempo de ejecución frente al cambio de la longitud de entrada. Existen varios algoritmos O (NLogN) que no exhiben el mismo tiempo de ejecución. MergeSort y QuickSort se consideran algoritmos de esta clase, pero tienen tiempos de ejecución marcadamente diferentes para N. grande, pero cuando el tiempo frente a N se muestran en un gráfico, sus tasas de tiempo de ejecución aumentan de manera similar, de forma logarítmica. Espero que esto ayude a aclarar las cosas. Hay muy pocos arreglos de datos y usos útiles de algoritmos que resultan en pasos EXACTAMENTE NLogN.

No puede tener el caso en el que toma exactamente [matemática] n \ log n [/ matemática] pasos, mire este código simple de montón:

void max_heapify (heap * A, int index) {
int izquierda = IZQUIERDA (índice);
int right = RIGHT (índice);
int más grande = índice;

if (left heap_size && A-> v [left]> A-> v [index])
mayor = izquierda;
if (derecha heap_size && A-> v [derecha]> A-> v [más grande])
mayor = derecha;
if (mayor! = índice) {
swap (A-> v [índice], A-> v [mayor]);
max_heapify (A, mayor);
}
}
vacío buil_max_heap (montón * A) {
A-> heap_size = A-> longitud;
para (int i = A-> heap_size / 2; i> -1; –i)
max_heapify (A, i);
}
int heap_extract_max (montón * A) {
valor int = A-> v [0];
A-> v [0] = A-> v [A-> heap_size-1];
–A-> heap_size;
max_heapify (A, 0);
valor de retorno;
}
nulo heap_sort (montón * A) {
buil_max_heap (A);
para (int i = A-> length-1; i> -1; –i) {
int x = heap_extract_max (A);
A-> v [i] = x;
}
}

Como puede ver en las líneas 29–32, en realidad hay iteración [matemática] n [/ matemática], por lo que la complejidad sería exactamente [matemática] n * (extracto \ _max () + 1) [/ matemática] pero si observa en la línea 23, verá que en cada llamada el tamaño del almacenamiento dinámico se reduce en uno.

Un número de pasos más preciso sería [math] \ sum_ {i = 0} ^ {n-1} \ lfloor {\ log (ni) + 1} \ rfloor [/ math]. Es fácil entender que el límite superior de esta suma es [matemática] n \ log n [/ matemática] pero en la práctica no hay casos en que esto suceda exactamente.

No es de extrañar que esto suceda, a menudo la notación big-O no es muy exacta en términos de pasos (por ejemplo selection_sort () y otras toneladas de algoritmos), pero eso es porque no tiene que ser tan preciso.

Heapsort es un algoritmo muy eficiente si se le proporciona una matriz en la que se mantiene la propiedad del montón para cada uno de sus elementos. De lo contrario, se volvió menos eficiente porque necesita construir el montón desde cero.