¿Mejores y peores entradas para la clasificación de montón y clasificación rápida?

montón- Dado que el mejor y el peor caso son iguales ¿No importa el orden de entrada? ¿El número de comparaciones y asignaciones siempre será el mismo? Me imagino que en una clasificación de montón puede ser el mismo ya que el trabajo real se realiza en la inserción, pero la clasificación solo utiliza la eliminación de la max / min heap? ¿Es por eso?

El número de comparaciones realizadas realmente puede depender de el orden en el que se dan los valores. El hecho de que el mejor y el peor de los casos sean Θ (n log n), suponiendo que todos los elementos sean distintos, solo significa que asintóticamente no hay diferencia entre los dos, aunque pueden diferir por un factor constante. No tengo ningún ejemplo simple de esto en mi cabeza, pero creo que puede construir entradas donde el número de comparaciones difiera por un factor constante entre el dos enfoques. Sin embargo, dado que la notación O grande ignora las constantes, esto no se refleja en el análisis del mejor y del peor caso.

clasificación rápida- Este No lo sé con certeza. No estoy seguro de cuál es el mejor y el peor de los casos para esto. Si, por ejemplo, es una lista ya ordenada de 10 cadenas, ¿no tendremos que elegir siempre la misma cantidad de pivotes para completar el algoritmo recursivo? Cualquier ayuda sobre esta explicación sería de gran ayuda.

El número de pivotes elegidos es de hecho el mismo independientemente de la ejecución del algoritmo. Sin embargo, el trabajo realizado por pivote puede variar según el tipo de divisiones que obtenga. En el mejor de los casos, el pivote elegido en cada paso termina siendo el elemento mediano de la matriz. Cuando esto sucede, se hacen (aproximadamente) n comparaciones en la capa superior de la recursividad, luego (aproximadamente) n en la siguiente capa porque hay dos subarreglos de tamaño n / 2, luego hay (aproximadamente) n en la siguiente capa porque hay cuatro subarreglos de tamaño n / 4, etc. Dado que hay Θ (log n) capas y cada capa tiene Θ (n) trabajo, el trabajo total realizado es Θ (n log n). Por otro lado, considere elegir el mínimo absoluto de cada matriz como pivote. Luego (aproximadamente) n comparaciones se hacen en la capa superior, luego (aproximadamente) n – 1 en la siguiente capa, luego (aproximadamente) n – 2 en la siguiente, etc. La suma 1 + 2 + 3 + … + n es Θ (n ² ), de ahí el peor de los casos.

¡Espero que esto ayude!

Comentarios

• Señor, ¿cuál es el mejor caso de heapsort nlogn? Si consideramos que todos los elementos son idénticos, entonces el costo sería simplemente iterar a través de todos los elementos de la matriz y no subir hasta la raíz. Por lo tanto, debería ser omega (n) en mi opinión.
• Ese es un buen punto. Estaba asumiendo elementos distintos, así que actualizaré esta respuesta.

Ya que nadie «s realmente abordó heapSort todavía:

Suponiendo que está usando un montón máximo representado como una matriz e insertando sus elementos máximos al revés en su matriz de salida / en la parte posterior de su matriz si lo está haciendo en el lugar , la entrada del peor de los casos para heapSort es cualquier entrada que te obligue a «burbujear» o volver a acumular cada vez que eliminas un elemento. Esto sucede cada vez que intentas ordenar un conjunto sin duplicados. Seguirá siendo Θ (n log n), como dijo templatetypedef.

Esta propiedad implica que el mejor caso de heapSort es cuando todos los elementos son iguales (Θ (n), ya que no tiene que volver a procesar después de cada eliminación, lo que lleva log (n) tiempo desde que la altura máxima del montón es log (n)). Sin embargo, es un caso pésimo / poco práctico, por lo que el mejor caso real para heapsort es Θ (n log n).

Comentarios

• Su punto sobre el pésimo caso poco práctico fue recién formulado en mi clase de algoritmos. (cuidado con las preguntas capciosas). Por supuesto, ‘ todavía estoy de acuerdo con su punto. ( y obtuve mi respuesta incorrecta como resultado XD)

• Clasificación rápida

  Peor caso: $ \ mathcal {O} (n ^ 2) $ . Supongamos que el elemento pivote es siempre el elemento más a la derecha: ingrese un ya lista ordenada con elementos $ n $ . Por lo tanto, cada partición conduce a una lista con elementos $ n-1 $ y una lista con elementos $ 0 $ . Incluso si elige el elemento dinámico al azar , aún puede tener mala suerte y elegir siempre el valor máximo en la lista.

  Sea $ T (n) $ el número de comparaciones quicksort requiere ordenar una lista con elementos $ n $ . En el peor de los casos: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ recursivo, $ n $ a partición)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Mejor caso: $ \ mathcal {O} (n \ log n) $ . Si el elemento pivote se elige de tal manera que divide la lista de manera uniforme:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 veces $ \ frac {n} { 2} $ recursivo, $ n $ a la partición)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {teorema maestro}) \ end {align}

• Ordenar montón

  El peor de los casos y el mejor de los casos de complejidad para la ordenación del montón son ambos $ \ mathcal {O} (n \ log n) $ . Por lo tanto, la ordenación del montón necesita comparaciones $ \ mathcal {O} (n \ log n) $ para cualquier matriz de entrada. Complejidad de la clasificación del montón:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ text {regla del cociente de logaritmos}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {align }

Comentarios

• No tiene ‘ Respondí todas las preguntas del OP ‘, así que responderé una que te perdiste; La clasificación de montón no ‘ t siempre usa el mismo número de comparaciones para un número dado de elementos. El peor caso es $ a \, n \ log n $ y el mejor caso es $ b \, n \ log n $, donde $ a > b $.
• También tenga en cuenta que la variante de tres vías tiene el mejor caso lineal para la entrada de un solo elemento.