Complejidades de las operaciones básicas de algoritmos de búsqueda y clasificación [cerrado]

Wiki tiene una buena hoja de trucos, pero no implica que no. de comparaciones o permutas. (aunque el número de intercambios generalmente decide su complejidad). Entonces creé lo siguiente. ¿La siguiente información es correcta? Avíseme si hay algún error, lo corregiré.

Tipo de inserción:

• Caso promedio / Peor caso: ; sucede cuando la entrada ya está ordenada en orden descendente$\Theta(n^2)$
• Mejor caso: $\Theta(n)$ ; cuando la entrada ya está ordenada
• Número de comparaciones: $\Theta(n^2)$ en el peor de los casos y $\Theta(n)$ en el mejor de los casos
• No. de intercambios: $\Theta(n^2)$ en el peor / promedio caso y $0$ en el mejor caso

Selección de selección:

• Caso promedio / Peor caso / Mejor caso: $\Theta(n^2)$
• No. de comparaciones: $\Theta(n^2)$
• No. de intercambios: $\Theta(n)$ en el peor / promedio caso y $0$ en el mejor de los casos. A lo sumo, el algoritmo requiere N intercambios, una vez que intercambias un elemento en su lugar, nunca lo vuelves a tocar.

Ordenar fusión:

• Caso promedio / Peor caso / Mejor caso: ; no importa en absoluto si la entrada está ordenada o no$\Theta(nlgn)$
• No. de comparaciones: en el peor de los casos y en el mejor de los casos; suponiendo que estamos fusionando dos conjuntos de tamaño n & m donde$\Theta(n+m)$$\Theta(n)$$n<m$
• No. de intercambios: ¡No intercambios! [pero requiere memoria adicional, no ordenación in situ]

Ordenación rápida:

• Peor caso: ; sucede que la entrada ya está ordenada$\Theta(n^2)$
• Mejor caso: ; cuando pivote divide la matriz exactamente en la mitad$\Theta(nlogn)$
• Número de comparaciones: en el peor de los casos y en el mejor de los casos$\Theta(n^2)$$\Theta(nlogn)$
• No. de intercambios: en el peor de los casos y en el mejor de los casos$\Theta(n^2)$$0$

Ordenamiento de burbuja:

• Peor caso:$\Theta(n^2)$
• Mejor caso: ; en ya ordenado$\Theta(n)$
• No. de comparaciones: en el peor de los casos y el mejor de los casos$\Theta(n^2)$
• No. de intercambios: en el peor de los casos y en el mejor de los casos$\Theta(n^2)$$0$

Búsqueda lineal:

• Peor caso: ; clave de búsqueda no presente o último elemento$\Theta(n)$
• Mejor caso: ; primer elemento$\Theta(1)$
• No. de comparaciones: en el peor de los casos y en el mejor de los casos$\Theta(n)$$1$

Búsqueda binaria:

• Peor caso / Caso promedio:$\Theta(logn)$
• Mejor caso: ; cuando la clave es el elemento medio$\Theta(1)$
• No. de comparaciones: en el peor / promedio caso y en el mejor caso$\Theta(logn)$$1$

1. Solo he considerado algoritmos básicos de búsqueda y clasificación.
2. Se supone anteriormente que los algoritmos de clasificación producen resultados en orden ascendente
3. Fuentes: El impresionante CLRS y este Wiki

Para el algoritmo general de burbuja, las comparaciones del peor de los casos son Pero para el algoritmo de caso especial, en el que agrega una bandera para indicar que ha habido un intercambio en el paso anterior. Si no hubo intercambios, salimos del ciclo ya que la matriz ya está ordenada. En este caso, las comparaciones son no 0.$\Theta(n^2)$$n$

Para la clasificación rápida, ha mencionado que los intercambios del peor de los casos son . Bueno, el peor de los casos para la ordenación rápida es cuando todos los elementos están ordenados, por lo que no habrá intercambios, por lo que debería ser cero.$n^2$