Fusionar la complejidad del tiempo de clasificación
División entera por dos
La división entera es necesaria al hacer un tipo de fusión.
Cuando un número impar se divide por dos, hay un resto de 1. Por ejemplo:
7/2 = 3 R 1
La división entera significa tomar el número completo como su respuesta y abandonar el 1.
Cuando un número uniforme se divide por dos, hay un resto de 0. Por ejemplo:
6/2 = 3 r 0
La división entera significa tomar el número completo como su respuesta y abandonar el 0.
En cualquier caso, se toma todo el número y el resto se abandona.
El objetivo de este artículo es determinar la complejidad del tiempo del tipo de fusión, escrita también como Mergesort. La clasificación puede ser ascendente o descendente. La clasificación en este artículo se refiere a clasificar ascender.
Algoritmo de clasificación de clasificación
Fusion Sort es un algoritmo de clasificación de división y conquistar. En este algoritmo, la lista sin clasificar se divide en dos mitades utilizando la división entera. Cada una de las mitades se divide en dos mitades nuevamente utilizando la división entera. Esta división continúa hasta que la lista se considera como elementos separados.
A partir de la izquierda, los elementos consecutivos se emparejan de manera ordenada. Los elementos emparejados se emparejan nuevamente en forma ordenada. Esta agrupación por parejas continúa hasta que toda la lista se reforma y ordene.
Complejidad del tiempo lineal y logarítmico
Considere el siguiente código en el idioma C:
para (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);
printf ("\ n");
La salida es:
1 2 3 4 5 6 7 8
El código es un for-bucle (ignorando la instrucción de impresión justo después del bucle de for-bucle). Imprime los enteros del 1 al 8, para un total de 8 números. El contenido del cuerpo del for-loop es:
int k = i + 1;
printf ("%d", k);
Estas dos declaraciones se consideran una operación principal en esta situación. Hay 8 operaciones. Sea N 8. Esta es una complejidad de tiempo lineal y se escribe de la siguiente manera:
En)
Donde n es el posible número máximo de operaciones. Esta es la notación Big-O. Comienza con O en mayúscula y seguido de paréntesis. Dentro de los paréntesis es el número máximo posible de operaciones.
Considere ahora el siguiente código donde de 8 números, se imprimen 3 números:
para (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);
if (k == 3) romper;
printf ("\ n");
La salida es:
1 2 3
El código es un for-bucle (ignorando la instrucción de impresión justo después del bucle de for-bucle). Imprime los enteros de 1 a 3 de 8 números. El contenido del cuerpo del for-loop es:
int k = i + 1;
printf ("%d", k);
if (k == 3) romper;
Aún así, estas tres declaraciones se consideran una operación principal en esta situación. Hay 3 operaciones de 8.
Ahora,
8 = 23
=> 3 = registro2(8)
Entonces, el número de operaciones principales realizadas por el código anterior es 3 (de 8).
Sea N 8. Esta es una complejidad del tiempo logarítmico y se escribe como:
O (registro2norte)
Donde (registro2 n) significa 3 para el código anterior.
Hubo 8 números. En general, cuando el número de operaciones para el código es entre 2 y 5 de 8 y no solo 3, la complejidad del tiempo se describe como log2(norte).
Ejemplo de lista no filmada y ordenada
Un ejemplo de lista no organizada es el siguiente:
P V D Q S X T B
Hay ocho elementos en la lista. Cuando esta lista está ordenada, se convierte en:
B D P Q S T V X
Contando el número de operaciones principales en el tipo de fusión
La siguiente lista:
P V D Q S X T B
se utiliza para contar el número de operaciones principales en clasificación de fusión.
La división entera por dos da el siguiente resultado:
P V D Q S X T B
Esta es una operación. Otra división de ambas partes por dos da el siguiente resultado:
P V D Q S X T B
Estas son tres operaciones hasta ahora (una más dos). Otra división de cada nueva parte por dos da el siguiente resultado:
P V D Q S X T B
Estas son siete operaciones hasta ahora (tres más cuatro). La lista de los ocho elementos ahora se considera como ocho elementos separados con un total de siete operaciones hasta ahora. La siguiente fase es emparejar mientras se clasifica, comenzando desde la izquierda. Entonces, el siguiente resultado es:
P V D Q S X B T
Hay dos cambios en la posición para el último par. Dos cambios son dos operaciones. Esto hace un total de nueve operaciones hasta ahora (siete más dos).
El emparejamiento y la clasificación continúan, siempre comenzando desde la izquierda para dar el siguiente resultado:
D P Q V B S T X
Cada uno de estos dos grupos tuvo cuatro cambios en la posición, haciendo ocho operaciones. Hay diecisiete operaciones hasta ahora (nueve más ocho). El emparejamiento y la clasificación continúan y, por último, para dar el siguiente resultado:
B D P Q S T V X
Hay siete cambios en la posición aquí, haciendo siete operaciones. Esto realiza veinticuatro operaciones (diecisiete más siete) para la clasificación completa.
Complejidad del tiempo para la clasificación de fusiones
El conteo anterior (ilustración) se utiliza para citar la complejidad del tiempo para el Mergesort. Hay veinticuatro operaciones.
24 = 8 x 3
Eso es:
24 = 8 x log2(8)
Porque log2 (8) es 3.
Sea 8. Con eso, la complejidad del tiempo de Mergesort viene dada por:
En.registro2norte)
donde el punto significa multiplicación.
En la práctica, de 8 elementos, el número de operaciones es de aproximadamente 24 o 24.
Conclusión
El Mergesort es un algoritmo de clasificación de división y conquistación particular. Es un algoritmo de clasificación muy eficiente. Su complejidad del tiempo es muy satisfactoria, en comparación con los otros algoritmos de clasificación. Su complejidad del tiempo es:
O (nlog2norte)
Nota: El número de operaciones no debe ser necesariamente n N -.log2n . Sin embargo, debería aproximarlo.
La codificación Mergesort necesita funciones recursivas. No es demasiado difícil codificarlo una vez que se ha entendido el algoritmo. Codificar el tipo de fusión es una discusión en otro momento.