Mergesort es un algoritmo de divide y vencerás y es O (log n) porque la entrada se reduce a la mitad repetidamente. Pero, ¿no debería ser O (n) porque aunque la entrada se reduce a la mitad en cada ciclo, cada elemento de entrada debe iterarse para hacer el intercambio en cada matriz dividida en dos? Esto es esencialmente asintóticamente O (n) en mi mente. Si es posible, proporcione ejemplos y explique cómo contar las operaciones correctamente. Todavía no he codificado nada, pero he estado buscando algoritmos en línea. También adjunté un gif de lo que Wikipedia está usando para mostrar visualmente cómo funciona mergesort.
algorithms
big-o
perseverancia
fuente
fuente
Respuestas:
Es O (n * log (n)), no O (log (n)). Como ha supuesto con precisión, toda la entrada debe iterarse, y esto debe ocurrir O (log (n)) veces (la entrada solo se puede reducir a la mitad O (log (n)) veces). n elementos iterados log (n) veces dan O (n log (n)).
Se ha demostrado que ningún tipo de comparación puede funcionar más rápido que esto. Solo los tipos que se basan en una propiedad especial de la entrada, como la clasificación de radix, pueden superar esta complejidad. Sin embargo, los factores constantes de mergesort generalmente no son tan buenos, por lo que los algoritmos con peor complejidad a menudo pueden tomar menos tiempo.
fuente
La complejidad del tipo de fusión es O (nlogn) y NOT O (logn).
La ordenación por fusión es un algoritmo de divide y vencerás. Piénselo en términos de 3 pasos:
Ahora, para los pasos 1 y 3, es decir, entre O (1) y O (n), O (n) es mayor. Consideremos que los pasos 1 y 3 toman el tiempo O (n) en total. Digamos que es cn para alguna constante c.
¿Cuántas veces se ejecutan estos pasos?
Para esto, mire el árbol a continuación: para cada nivel de arriba a abajo, el Nivel 2 llama al método de fusión en 2 sub-matrices de longitud n / 2 cada una. La complejidad aquí es 2 * (cn / 2) = cn El nivel 3 llama al método de fusión en 4 sub-matrices de longitud n / 4 cada una. La complejidad aquí es 4 * (cn / 4) = cn y así sucesivamente ...
Ahora, la altura de este árbol es (logn + 1) para un n dado. Por lo tanto, la complejidad general es (logn + 1) * (cn). Eso es O (nlogn) para el algoritmo de clasificación de fusión.
Créditos de imagen: Khan Academy
fuente
Merge Sort es un algoritmo recursivo y la complejidad del tiempo se puede expresar como la siguiente relación de recurrencia.
La recurrencia anterior se puede resolver utilizando el método del árbol de recurrencia o el método maestro. Cae en el caso II del Método maestro y la solución de la recurrencia es ɵ (n log n).
La complejidad de tiempo de Merge Sort es ɵ (nLogn) en los 3 casos (peor, promedio y mejor), ya que la clasificación de fusión siempre divide la matriz en dos mitades y toma tiempo lineal para fusionar dos mitades.
Divide la matriz de entrada en dos mitades, se llama a sí misma para las dos mitades y luego combina las dos mitades ordenadas. La función merg () se usa para fusionar dos mitades. La combinación (arr, l, m, r) es un proceso clave que supone que arr [l..m] y arr [m + 1..r] están ordenados y fusiona los dos sub-arrays ordenados en uno. Vea la siguiente implementación de C para más detalles.
Si observamos más de cerca el diagrama, podemos ver que la matriz se divide recursivamente en dos mitades hasta que el tamaño se convierte en 1. Una vez que el tamaño se convierte en 1, los procesos de fusión entran en acción y comienzan a fusionarse de nuevo hasta que la matriz completa esté fusionado
fuente
Los algoritmos de ordenación basados en la comparación tienen un límite inferior
𝞨(n*log(n))
, lo que significa que no es posible tener un algoritmo de ordenación basado en la comparación con laO(log(n))
complejidad del tiempo.Por cierto, el tipo de fusión es
O(n*log(n))
. Piénsalo de esta manera.Esto parece un árbol binario invertido.
Deje que el tamaño de entrada sea
n
.Cada uno
a_n
representa una lista de elementos. La primera líneaa_n
tiene solo un elemento.En cada nivel, la suma del costo de fusión en promedio es
n
(existen casos de esquina cuyo costo es menor [1]). Y la altura del árbol eslog_2(n)
.Por lo tanto, la complejidad temporal del tipo de fusión es
O(n*log_2(n))
.fuente
La clasificación es un problema NP-completo en informática (problema no polinómico). Esto significa que, a menos que se demuestre matemáticamente, no puede ir por debajo de O (n log n) al ordenar una lista de elementos.
Consulte este artículo en Wikipedia ( https://en.wikipedia.org/wiki/P_versus_NP_problem )
Básicamente, hasta ahora nadie logró demostrar eso (P == NP) y si lo hace, primero se hace millonario, luego comienza la Tercera Guerra Mundial debido al hecho de que podrá romper todos los mecanismos de seguridad de pub / clave privada utilizados en todas partes hoy en día :)
fuente