¿Alguien es capaz de dar una explicación intuitiva, aunque formal, de 'inglés sencillo' de lo que hace que QuickSort n log n? Desde mi punto de vista, tiene que pasar por n elementos, y lo hace log n veces ... No estoy seguro de cómo ponerlo en palabras por qué lo hace este registro n veces.Explicación intuitiva de por qué QuickSort es n log n?
Cada operación de partición toma O (n) operaciones (una pasada en la matriz). En promedio, cada partición divide la matriz en dos partes (que resume operaciones de log n). En total tenemos operaciones O (n * log n).
I.e. en operaciones de partición log n promedio y cada partición toma operaciones O (n).
La parte log n proviene del hecho de que está (al menos idealmente) dividiendo la entrada a la mitad en cada iteración. Empezar desde N elementos, y dividirlos por la mitad cada vez, significa que tiene menos de 1 elemento después de registrar (N) iteraciones, en cuyo punto obviamente no puede subdividirlo más. Por ejemplo, a partir de, digamos, 128 elementos, se divide en grupos de 64, 32, 16, 8, 4, 2, 1 ítems - 7 iteraciones (y log (128) = 7).
Cada una de esas iteraciones explora toda la matriz para dividirla, por lo que termina con operaciones O (log N), cada una de las cuales tiene complejidad O (n), para la complejidad total O (n log n).
Para ser técnicamente correcto, el Big-O es O (N). Esto surge del hecho de que una elección suficientemente mala del elemento de partición podría dividir la matriz en un elemento en un lado, y el resto completo del conjunto en el otro. Si esto ocurre en cada iteración, se necesitan N iteraciones para dividirla en partes de un elemento cada una, de modo que se obtienen N operaciones, cada una con una complejidad de O (N), para O (N * N) en general.
En una implementación real, generalmente se detiene antes de eso, pero eso es lo más lejos que puede llegar.
Bueno, no siempre es n (log n). Es el tiempo de ejecución cuando el pivote elegido está aproximadamente en el medio. En el peor de los casos, si elige el elemento más pequeño o más grande como pivote, entonces el tiempo será O (n^2).
Para visualizar 'n log n', puede suponer que el pivote sea el elemento más cercano al promedio de todos los elementos de la matriz que se va a ordenar. Esto dividiría la matriz en 2 partes de aproximadamente la misma longitud. En ambos, aplica el procedimiento de búsqueda rápida.
Como en cada paso se va a reducir a la mitad la longitud de la matriz, se hará esto para log n (base 2) veces hasta llegar a la longitud = 1, es decir, una matriz ordenada de 1 elemento.
Tienes razón, pero no mezcles el promedio y la mediana. La mediana es lo que le permite dividirse en dos partes con la misma longitud (+ -1). – kvetis
De hecho, necesita encontrar la posición de todos los N elementos (pivote), pero el número máximo de comparaciones es logN para cada elemento (el primero es N, el segundo pivote N/2,3rd N/4. pivote .assuming es el elemento mediano)
Gracias por esto. La respuesta aceptada aquí simplemente reformuló lo que el OP (y yo) ya sabía (n operaciones hechas log n veces), pero pasó por alto la única parte importante: ¿por qué se hace log n veces? Esta respuesta es una explicación agradable y simple de dónde proviene realmente el término del registro. –
es muy claro respuesta gracias. – huseyin
esta es la mejor explicación – huseyin