algorithm - por - ordenamiento quicksort

¿Por qué es el tiempo de ejecución del algoritmo de selección O(n)? (6)

Según Wikipedia , el algoritmo de selección tiene un tiempo de ejecución de O(n) , pero no estoy convencido de ello. ¿Alguien puede explicar por qué es O(n) ?

En la ordenación rápida normal, el tiempo de ejecución es O(n log n) . Cada vez que dividimos la rama en dos ramas (mayor que el pivote y menor que el pivote), debemos continuar procesando ambos lados de las ramas, mientras que el algoritmo de selección solo necesita procesar un lado de la rama. Entiendo totalmente estos puntos. Pero si piensa en el algoritmo de búsqueda binaria, después de que elegimos el elemento central, también continuamos buscando un lado de la rama. Entonces, ¿eso hace el algoritmo O(1) ? No , por supuesto, el algoritmo de búsqueda binaria sigue siendo O(log N) lugar de O(1) . Esto también es lo mismo que el elemento de búsqueda en un Árbol de búsqueda binario. Solo buscamos un lado, pero aún consideramos O(log n) lugar de O(1) .

¿Alguien puede explicar por qué en el algoritmo de selección, si continuamos buscando un lado, podemos considerar O(1) lugar de O(log n) ? Para mí, considero que el algoritmo es O(n log n) , O(N) para la partición y O(log n) para el número de veces para continuar encontrando.

En Quicksort, el árbol de recursión tiene niveles de lg (N) y cada uno de estos niveles requiere una cantidad de trabajo O (N). Entonces el tiempo total de ejecución es O (NlgN).

En Quickselect, el árbol de repetición tiene niveles de lg (N) y cada nivel requiere solo la mitad del trabajo del nivel superior. Esto produce lo siguiente:

N * (1/1 + 1/2 + 1/4 + 1/8 + ...)

N * Summation(1/i^2) 1 < i <= lgN

Lo importante a tener en cuenta aquí es que voy de 1 a lgN, pero no de 1 a N y tampoco de 1 a infinito.

La suma se evalúa como 2. Por lo tanto, Quickselect = O (2N).

Hay varios algoritmos de selección diferentes, desde la selección rápida mucho más simple (O (n) esperado, O (n ² ) en el caso más desfavorable) hasta el algoritmo de mediana de medianas más complejo (Θ (n)). Ambos algoritmos funcionan al usar un paso de partición de ordenamiento rápido (tiempo O (n)) para reorganizar los elementos y colocar un elemento en su posición correcta. Si ese elemento está en el índice en cuestión, hemos terminado y solo podemos devolver ese elemento. De lo contrario, determinamos de qué lado recurriremos y responderemos allí.

Supongamos que estamos usando quickselect (seleccione el pivote al azar) y en cada iteración podemos adivinar la mitad exacta de la matriz. En ese caso, nuestro algoritmo funcionará así: hacemos un paso de partición, desechamos la mitad de la matriz y luego procesamos recursivamente la mitad de la matriz. Esto significa que en cada llamada recursiva terminamos haciendo un trabajo proporcional a la longitud de la matriz en ese nivel, pero esa longitud sigue disminuyendo en un factor de dos en cada iteración. Si resolvemos las matemáticas (ignorando factores constantes, etc.) terminamos obteniendo el siguiente tiempo:

Trabajar en el primer nivel: n
Trabajar después de una llamada recursiva: n / 2
Trabaja después de dos llamadas recursivas: n / 4
Trabaja después de tres llamadas recursivas: n / 8
...

Esto significa que el trabajo total realizado está dado por

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...)

Observe que este último término es n veces la suma de 1, 1/2, 1/4, 1/8, etc. Si calcula esta suma infinita, a pesar de que hay infinitos términos, la suma total es exactamente 2. Esto significa que el trabajo total es

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) = 2n

Esto puede parecer extraño, pero la idea es que si hacemos trabajo lineal en cada nivel pero seguimos cortando la matriz a la mitad, terminamos haciendo solo 2n de trabajo.

Un detalle importante aquí es que efectivamente hay O (log n) diferentes iteraciones aquí, pero no todas están haciendo una cantidad igual de trabajo. De hecho, cada iteración hace la mitad de trabajo que la iteración anterior. Si ignoramos el hecho de que el trabajo está disminuyendo, puede concluir que el trabajo es O (n log n), lo cual es correcto pero no un límite estricto. Este análisis más preciso, que utiliza el hecho de que el trabajo realizado sigue disminuyendo en cada iteración, proporciona el tiempo de ejecución O (n).

Por supuesto, esta es una suposición muy optimista: ¡casi nunca obtenemos una división 50/50! - pero utilizando una versión más potente de este análisis, puede decir que si puede garantizar cualquier división de factor constante, el trabajo total realizado es solo un múltiplo constante de n. Si seleccionamos un elemento totalmente aleatorio en cada iteración (como lo hacemos en la selección rápida), en la expectativa solo tenemos que elegir dos elementos antes de que terminemos eligiendo un elemento pivote en el 50% medio de la matriz, lo que significa que, en expectativa, solo se requieren dos rondas de selección de un pivote antes de que terminemos eligiendo algo que da una división de 25/75. Aquí es de donde proviene el tiempo de ejecución esperado de O (n) para selección rápida.

Un análisis formal del algoritmo de mediana de medianas es mucho más difícil porque la recurrencia es difícil y no es fácil de analizar. Intuitivamente, el algoritmo funciona realizando una pequeña cantidad de trabajo para garantizar que se elija un buen pivote. Sin embargo, debido a que se realizan dos llamadas recursivas diferentes, un análisis como el anterior no funcionará correctamente. Puede usar un resultado avanzado llamado teorema de Akra-Bazzi , o usar la definición formal de big-O para demostrar explícitamente que el tiempo de ejecución es O (n). Para un análisis más detallado, echa un vistazo a "Introducción a los algoritmos, tercera edición" de Cormen, Leisserson, Rivest y Stein.

¡Espero que esto ayude!

Ordenar = reorganizar elementos es O (n log n), pero la selección es algo así como tomar el elemento i = indexación. Y para eso, tanto en una lista enlazada, como en un árbol binario, es O (n).

Permítame tratar de explicar la diferencia entre la selección y la búsqueda binaria.

El algoritmo de búsqueda binaria en cada paso realiza operaciones O (1). Totalmente hay pasos de registro (N) y esto lo hace O (registro (N))

El algoritmo de selección en cada paso realiza operaciones O (n). Pero esta ''n'' sigue reduciéndose a la mitad cada vez. Hay pasos totalmente log (N). Esto hace que sea N + N / 2 + N / 4 + ... + 1 (log (N) veces) = 2N = O (N)

Para la búsqueda binaria es 1 + 1 + ... (log (N) veces) = O (logN)

Porque para la selección, no estás ordenando, necesariamente. Simplemente puede contar cuántos elementos hay que tengan un valor determinado. Por lo tanto, se puede realizar una mediana O (n) contando cuántas veces aparece cada valor y seleccionando el valor que tiene el 50% de los elementos por encima y por debajo. Es 1 paso a través de la matriz, simplemente incrementando un contador para cada elemento de la matriz, por lo que es O (n).

Por ejemplo, si tiene una matriz "a" de números de 8 bits, puede hacer lo siguiente:

int histogram [ 256 ]; for (i = 0; i < 256; i++) { histogram [ i ] = 0; } for (i = 0; i < numItems; i++) { histogram [ a [ i ] ]++; } i = 0; sum = 0; while (sum < (numItems / 2)) { sum += histogram [ i ]; i++; }

Al final, la variable "i" contendrá el valor de 8 bits de la mediana. Fue alrededor de 1,5 pases a través de la matriz "a". Una vez a través de toda la matriz para contar los valores, y la mitad a través de ella nuevamente para obtener el valor final.

Quicksort no tiene una gran O de nlogn; en el peor de los casos, el tiempo de ejecución es n ^ 2.

Supongo que está preguntando sobre el algoritmo de selección de Hoare (o selección rápida) no sobre el algoritmo de selección ingenuo que es O (kn). Al igual que quicksort, quickselect tiene un tiempo de ejecución de peor caso de O (n ^ 2) (si se eligen pivotes incorrectos), no O (n). Puede ejecutarse en el tiempo de expectativa n porque solo está ordenando un lado, como señala.