algorithm - rap - Tiempo de ejecución medio de Quickselect

big o notation java (3)

En la selección rápida, según lo especificado, aplicamos la recursión en solo la mitad de la partición.

Análisis de casos promedio:

Primer paso: T (n) = cn + T (n / 2)

donde, cn = tiempo para realizar la partición, donde c es cualquier constante (no importa).
T (n / 2) = aplicando recursividad en la mitad de la partición.
Como es un caso promedio, asumimos que la partición era la mediana.

A medida que seguimos haciendo la recursión, obtenemos el siguiente conjunto de ecuaciones:

T (n / 2) = cn / 2 + T (n / 4)
T (n / 4) = cn / 2 + T (n / 8)
.
.
.
T (2) = c.2 + T (1)
T (1) = c.1 + ...

La suma de las ecuaciones y los valores similares de cancelación cruzada producen un resultado lineal.

c (n + n / 2 + n / 4 + ... + 2 + 1) = c (2n) // la suma de un GP

Por lo tanto, es O (n)

Wikipedia indica que el tiempo de ejecución promedio del algoritmo de selección rápida ( Link ) es O (n). Sin embargo, no pude entender claramente cómo esto es así. ¿Podría alguien explicarme (a través de la relación de recurrencia + uso del método maestro) cómo el tiempo de ejecución promedio es O (n)?

Para realizar un análisis de caso promedio de selección rápida, se debe considerar qué tan probable es que se comparen dos elementos durante el algoritmo para cada par de elementos y suponiendo un giro aleatorio . De esto podemos derivar el número promedio de comparaciones. Desafortunadamente, el análisis que mostraré requiere algunos cálculos más largos pero es un análisis de caso de promedio limpio en lugar de las respuestas actuales.

Asumamos que el campo del que queremos seleccionar el k -ésimo elemento más pequeño es una permutación aleatoria de [1,...,n] . Los elementos dinámicos que elegimos durante el curso del algoritmo también se pueden ver como una permutación aleatoria dada. Durante el algoritmo, siempre seleccionamos el siguiente pivote factible de esta permutación, por lo tanto, se eligen uniformemente al azar, ya que cada elemento tiene la misma probabilidad de ocurrir como el siguiente elemento factible en la permutación aleatoria.

Hay una observación simple pero muy importante: solo comparamos dos elementos i y j (con i<j ) si y solo si uno de ellos es elegido como primer elemento de pivote del rango [min(k,i), max(k,j)] . Si se elige primero otro elemento de este rango, entonces nunca se compararán porque seguimos buscando en un subcampo donde al menos uno de los elementos i,j no está contenido en.

Debido a la observación anterior y al hecho de que los pivotes se eligen uniformemente al azar, la probabilidad de una comparación entre i y j es:

2/(max(k,j) - min(k,i) + 1)

(Dos eventos de max(k,j) - min(k,i) + 1 posibilidades.)

Dividimos el análisis en tres partes:

max(k,j) = k , por lo tanto, i < j <= k
min(k,i) = k , por lo tanto k <= i < j
min(k,i) = i y max(k,j) = j , por lo tanto i < k < j

En el tercer caso, los signos menos iguales se omiten porque ya consideramos esos casos en los dos primeros casos.

Ahora vamos a ensuciarnos un poco los cálculos. Simplemente resumimos todas las probabilidades, ya que esto da el número esperado de comparaciones.

Caso 1

Caso 2

Similar al caso 1 así que esto permanece como un ejercicio. ;)

Caso 3

Usamos H_r para el número del armónico r-th que crece aproximadamente como ln(r) .

Conclusión

Los tres casos necesitan un número lineal de comparaciones esperadas. Esto muestra que, de hecho, la selección rápida tiene un tiempo de ejecución esperado en O(n) . Tenga en cuenta que, como ya se mencionó, el caso más desfavorable se encuentra en O(n^2) .

Nota: La idea de esta prueba no es mía. Creo que eso es más o menos el promedio de análisis de casos estándar de selección rápida.

Si hay algún error por favor hágamelo saber.

Porque

Ya sabemos en qué partición se encuentra nuestro elemento deseado.

No necesitamos ordenar (haciendo partición en) todos los elementos, solo hacemos la operación en la partición que necesitamos.

Como en la ordenación rápida, tenemos que hacer la partición en mitades *, y luego en las mitades de la mitad, pero esta vez, solo necesitamos hacer la siguiente partición redonda en una sola partición (la mitad) de las dos donde se espera el elemento. mentir en.

Es como (no muy preciso)

n + 1/2 n + 1/4 n + 1/8 n + ..... <2 n

Así que es O (n).

_{La mitad se utiliza por comodidad, la partición real no es exacta del 50%.}