Análisis de algoritmos (complejidad)

Question

¿Cómo se analizan los algoritmos? ¿Qué hace que quicksort tenga un rendimiento en el peor de los casos O(n^2) mientras que merge sort tiene un peor rendimiento en el O(n log(n))?

Answer 1

Ese es un tema para todo un semestre. En definitiva, estamos hablando del límite superior en el número de operaciones que deben completarse antes de que el algoritmo finalice en función del tamaño de la entrada. No incluimos los coeficientes (es decir, 10N vs 4N^2) porque para N es lo suficientemente grande, ya no importa.

Cómo demostrar lo que es el gran oh de un algoritmo puede ser bastante difícil. Requiere una prueba formal y hay muchas técnicas. A menudo, una buena forma ad hoc es simplemente contar cuántos pases de datos hace el algoritmo. Por ejemplo, si su algoritmo ha anidado bucles, entonces para cada uno de los N elementos debe operar N veces. Eso generalmente sería O (N^2).

En cuanto a la clase de fusión, divide los datos por la mitad una y otra vez. Eso requiere log2 (n). Y para cada división haces un pase en los datos, lo que da N log (n).

ordenar rápidamente es un poco más complicado porque en el caso promedio también es n log (n). Debe imaginarse qué sucede si su partición divide los datos de tal forma que cada vez que obtiene solo un elemento en un lado de la partición. Luego deberá dividir los datos n veces en lugar de registrar (n) veces, lo que lo convierte en N^2. La ventaja del quicksort es que se puede implementar y que, por lo general, nos acercamos más al rendimiento de N log (n).

Answer 2

quicksort y merge sort dividen la matriz en dos, ordene cada parte recursivamente, luego combine el resultado. Quicksort se divide al elegir un elemento "pivote" y dividir la matriz en más pequeña o más grande que el pivote. Merge sort se divide arbitrariamente y luego combina los resultados en tiempo lineal. En ambos casos, un solo paso es O (n), y si el tamaño de la matriz se reduce a la mitad cada vez, esto daría un número logarítmico de pasos. Entonces, esperaríamos O (n log (n)).

Sin embargo, el quicksort tiene el peor caso en el que la división es siempre desigual, por lo que no obtendrá una cantidad de pasos proporcionales a la logarítmica de n, sino una cantidad de pasos proporcionales a n. Merge sort se divide exactamente en dos mitades (o lo más cerca posible) por lo que no tiene este problema.

Answer 3

• ordenamiento rápido tiene muchas variantes en función de selección de pivotes
• Asumamos siempre seleccionamos primero elemento de la matriz como pivote

Si la matriz de entrada se ordena a continuación, ordenar rápida será sólo será tipo de selección tipo! Porque no está realmente dividiendo la matriz ... solo está seleccionando el primer artículo en cada ciclo

Por otro lado, merge sort siempre dividirá la matriz de entrada de la misma manera, independientemente de su contenido.

También tenga en cuenta: el mejor rendimiento en dividir y conquistar cuando las divisiones de longitud son casi iguales!

Answer 4

1. Este es un análisis introductorio del material del curso de algoritmos.

2. Se define una operación (es decir, multiplicación) y el análisis se realiza en términos de espacio o tiempo.

3. Esta operación se cuenta en términos de espacio o tiempo.Por lo general, los análisis se realizan como Tiempo siendo la variable dependiente del Tamaño de entrada.

Ejemplo pseudocódigo:

foreach $elem in @list 

    op(); 

endfor 

Habrá n operaciones realizadas, donde n es el tamaño de @list. Cuente usted mismo si no me cree.

Para analizar quicksort y mergesort se requiere un nivel decente de lo que se conoce como sofisticación matemática. Sin apretar, se resuelve una ecuación diferencial discreta derivada de la relación recursiva.