¿Qué es el algoritmo con complejidad temporal o(nlogn)?

El algoritmo con complejidad temporal o (nlogn) adopta la "idea de divide y vencerás", dividiendo la matriz que se va a ordenar desde el medio en las partes delantera y trasera, y luego ordenando las partes delantera y trasera respectivamente. y luego ordenar la matriz. Las dos partes de se fusionan para que la matriz esté ordenada.

Cada vez que se divide el área, se selecciona el punto medio para la división, por lo que la fórmula recursiva se puede escribir como: T(n) = T(n/2) + T(n/2) + n, T(1) = C (constante) // Se debe llamar a la función Merge() para cada fusión, la complejidad temporal es O(n), equivalente a T(n) = 2kT(n/2k) + k * n , el estado final de la recursividad es T (1) Es decir, n/2k = 1, entonces k = log2n.

Análisis de principios:

1. Se utiliza la idea de divide y vencerás. Seleccione el valor de la partición y divida la columna que se va a ordenar en dos partes. El valor del elemento de datos en la primera parte es menor o igual que el valor de la partición y el valor del elemento de datos en la última parte es mayor o igual. igual al valor de la partición Continúe particionando las dos partes respectivamente hasta que el tamaño de la partición sea 1.

2. El número de ejecuciones de la operación de intercambio se puede obtener del proceso de análisis de complejidad temporal. El número total de intercambios en Merge () es n * logn, porque independientemente del tamaño de las dos subsecuencias. , cada una de las subsecuencias Los elementos se colocarán primero en la matriz temporal temp y luego se volverán a colocar en la secuencia original, el número de operaciones de comparación es menor o igual que el número de operaciones de intercambio, y el número máximo de intercambios es; n * iniciar sesión.