algorithm - punto - ¿Por qué el tipo de fusión es el peor de los casos? O(n log n)?
punto de fusion (6)
¿Puede alguien explicarme en inglés simple o una manera fácil de explicarlo?
Después de dividir la matriz en el escenario donde tiene elementos individuales, es decir, llamarlos sublistas,
en cada etapa, comparamos elementos de cada sublista con su sublista adyacente. Por ejemplo, [Reutilizando la imagen de @Davi]
- En la Etapa-1, cada elemento se compara con su adyacente, por lo que n / 2 comparaciones.
- En la Etapa-2, cada elemento de la sublista se compara con su sublista adyacente, ya que cada sublista está ordenada, esto significa que el número máximo de comparaciones hechas entre dos sublistas es <= longitud de la sublista, es decir, 2 (en la Etapa-2) y 4 comparaciones en la Etapa 3 y 8 en la Etapa 4 ya que las sublistas se siguen duplicando. Lo que significa el número máximo de comparaciones en cada etapa = (longitud de la sublista * (número de sublistas / 2)) ==> n / 2
- Como ha observado, el número total de etapas sería ''log (n)'' Entonces la complejidad total sería == (número máximo de comparaciones en cada etapa * cantidad de etapas) == O ((n / 2) * log (n)) ==> O (nlog (n))
El algoritmo MergeSort toma tres pasos:
- El paso Dividir calcula la posición media de la sub-matriz y toma el tiempo constante O (1).
- Conquer step recursivamente clasifica dos sub arrays de aproximadamente n / 2 elementos cada una.
- Combinar paso fusiona un total de n elementos en cada pasada que requieren como máximo n comparaciones, por lo que toma O (n).
El algoritmo requiere pases logn aproximados para ordenar una matriz de n elementos, por lo que la complejidad total del tiempo es nlogn.
En un tipo de combinación "tradicional", cada paso a través de los datos duplica el tamaño de las subsecciones ordenadas. Después del primer pase, el archivo se ordenará en secciones de longitud dos. Después del segundo pase, duración cuatro. Luego ocho, dieciséis, etc. hasta el tamaño del archivo.
Es necesario duplicar el tamaño de las secciones ordenadas hasta que haya una sección que comprenda todo el archivo. Tomará lg (N) duplicaciones del tamaño de la sección para alcanzar el tamaño del archivo, y cada pase de los datos llevará tiempo proporcional a la cantidad de registros.
Esto se debe a que, ya sea en el caso más desfavorable o en el caso promedio, la ordenación por fusión simplemente divide el conjunto en dos mitades en cada etapa, lo que le da el componente lg (n) y el otro componente N proviene de las comparaciones que se realizan en cada etapa. Entonces la combinación se vuelve casi O (nlg n). No importa si es el caso promedio o el peor de los casos, el factor lg (n) siempre está presente. El factor N en reposo depende de las comparaciones realizadas que provienen de las comparaciones realizadas en ambos casos. Ahora el peor de los casos es uno en el que las comparaciones N suceden para una entrada N en cada etapa. Entonces se convierte en O (nlg n).
Muchas de las otras respuestas son geniales, pero no vi ninguna mención de altura y profundidad relacionada con los ejemplos del "árbol de clasificación de fusión". Aquí hay otra forma de enfocar la pregunta con mucho enfoque en el árbol. Aquí hay otra imagen para ayudar a explicar:
Solo una recapitulación: como han señalado otras respuestas, sabemos que el trabajo de fusionar dos segmentos ordenados de la secuencia se ejecuta en tiempo lineal (la función auxiliar de fusión que llamamos desde la función principal de clasificación).
Ahora mirando este árbol, donde podemos pensar en cada descendiente de la raíz (que no sea la raíz) como una llamada recursiva a la función de clasificación, intentemos evaluar cuánto tiempo pasamos en cada nodo ... Desde el corte de la secuencia y la fusión (ambas juntas) toman el tiempo lineal, el tiempo de ejecución de cualquier nodo es lineal con respecto a la longitud de la secuencia en ese nodo.
Aquí es donde entra la profundidad del árbol. Si n es el tamaño total de la secuencia original, el tamaño de la secuencia en cualquier nodo es n / 2 i , donde i es la profundidad. Esto se muestra en la imagen de arriba. Al unir esto con la cantidad lineal de trabajo para cada segmento, tenemos un tiempo de ejecución de O (n / 2 i ) para cada nodo en el árbol. Ahora solo tenemos que resumirlo para los n nodos. Una forma de hacerlo es reconocer que hay 2 i nodos en cada nivel de profundidad en el árbol. Entonces, para cualquier nivel, tenemos O (2 i * n / 2 i ), que es O (n) porque podemos cancelar las 2 i s. Si cada profundidad es O (n), solo tenemos que multiplicarla por la altura de este árbol binario, que es logn. Respuesta: O (nlogn)
referencia: estructuras de datos y algoritmos en Python
Merge Sort utiliza el enfoque Divide-and-Conquer para resolver el problema de clasificación. Primero, divide la entrada a la mitad usando la recursión. Después de dividir, ordena los medios y los fusiona en una salida ordenada. Ver la figura
Significa que es mejor clasificar primero la mitad de tu problema y hacer una subrutina de combinación simple. Por lo tanto, es importante conocer la complejidad de la subrutina de combinación y cuántas veces se llamará en la recursión.
El pseudocódigo para el tipo de fusión es realmente simple.
# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
if A[i] < B[j]
C[k] = A[i]
i++
else
C[k] = B[j]
j++
Es fácil ver que en cada bucle tendrá 4 operaciones: k ++ , i ++ o j ++ , la instrucción if y la atribución C = A | B. Por lo tanto, tendrá menos o igual a 4N + 2 operaciones que den una complejidad O (N) . Por el bien de la prueba, 4N + 2 será tratado como 6N, ya que es verdadero para N = 1 ( 4N +2 <= 6N ).
Asuma que tiene una entrada con N elementos y asuma que N es una potencia de 2. En cada nivel tiene dos veces más subproblemas con una entrada con medios elementos de la entrada anterior. Esto significa que en el nivel j = 0, 1, 2, ..., lgN habrá 2 ^ j subproblemas con una entrada de longitud N / 2 ^ j . El número de operaciones en cada nivel j será menor o igual a
2 ^ j * 6 (N / 2 ^ j) = 6N
Observe que no importa el nivel, siempre tendrá operaciones 6N menores o iguales.
Como hay niveles de LGN + 1, la complejidad será
O (6N * (lgN + 1)) = O (6N * lgN + 6N) = O (n lgN)
Referencias