¿Por qué el algoritmo de la mediana de las medianas no puede usar el tamaño de bloque 3?

Question

estoy trabajando a través del análisis de la mediana determinista encontrar bajo el supuesto de que la entrada se divide en 3 partes en lugar de 5 y la pregunta es ¿Dónde se descomponen?

la mediana determinista algoritmo de búsqueda de:

SELECT (i, n)

1. Divide los n elementos en grupos de 5. Encontrar la mediana de cada grupo de 5 elementos de memoria.

2. SELECCIONAR recursivamente la mediana x del grupo median/5⎦ grupo medianas para ser el pivote.

3. partición alrededor del pivote x. Sea k = rango (x)

4.if que i = k luego regrese x

elseif i < k

entonces SELECT de forma recursiva el elemento más pequeño ITH en la parte inferior

else recursivamente SELECCIONE el (i-k) th elemento más pequeño en la parte superior

Pasé por el anal ysis del algoritmo y creo que los pasos 1 y 3 tomarán O (n) donde solo lleva un tiempo constante encontrar la mediana de 5 elementos y Step2 toma T (n/5) .so al menos 3/10 de elementos son ≤ p, y al menos 3/10 de la matriz es ≥ p, por lo tanto, el Paso 4 será T (7n/10) y obtendrá la recurrencia. T (n) ≤ cn + T (n/5) + T (7n/10), pero cuando divido los elementos en goroup de 3, digamos los 9 elementos y los dividí en un grupo tal que:

{1,2,10} {4,11,14}, {15,20,22}

Tengo las medianas 2,11,20 y la p = 11.

en general en el grupo de cinco digamos g = n/5 grupos y al menos ⌈g/2⌉ de ellos (los grupos cuya mediana es ≤ p) al menos tres de los cinco elementos son ≤ p. entonces el número total de elementos ≤ p es al menos 3⌈g/2⌉ ≥ 3n/10. PERO en el grupo de 3 podemos obtener todos los tres elementos que podrían ser MENOS que p. y aquí creo que el algoritmo se descompondrá !!

he llegado hasta la idea correcta ???

Answer 1

En un grupo de 3, en cuanto a los grupos de 5, aproximadamente la mitad de los grupos tendrá su elemento mediano menor que la mediana de las medianas, por lo que en esos grupos puede descartar elementos menores que su mediana. En su caso, (1,2,10) tiene su mediana de menos de 11, por lo que puede desprenderse 1 y 2.

Donde creo que las cosas se descomponen para grupos de 3 está en la cuesta. 3 (piso (piso (n/5)/2 - 2) que es aproximadamente 3n/10 se convierte en 2 (piso (piso (n/3)/2 -2) más o menos, que es aproximadamente n/3. Esto significa que 7n/10 se convierte en 2n/3. piso (N/5) se convierte en baja (n/3), así que en vez de 7cn/10 + 2CN/10 = 9cn/10 que se va a obtener sólo 2CN/3 + cn/3 = CN, y en lugar de T (n) = cn < usted va a tener algo donde tendrá que mirar de cerca los términos que no implican c, y que podría terminar mostrando que no es lineal después de todo.

Parece que en realidad puedes tirar un poco más de elementos en cada etapa de la recursión, pero la recursión divide la cantidad de trabajo que queda por 3, no por 5, y esto no es suficiente para igualar.