Encontrar los kth cuantiles de un conjunto de n elementos. (Del cormen)

Question

Los kth cuantiles de un conjunto de n elementos son las estadísticas de orden k - 1 que dividen el conjunto ordenado en k conjuntos de igual tamaño (dentro de 1). Proporcione un algoritmo O (n lg k) -time para enumerar los kth cuantiles de un conjunto.

La solución directa sería seleccionar cada k, 2k, 3k .. ik el elemento más pequeño, cuyo tiempo de ejecución es O (kn) (k llama al procedimiento de selección de O (n)). Pero esto se puede optimizar para hacerlo mejor que O (kn). Después de encontrar la mediana de las medianas en el índice 'i' en el procedimiento de selección, realizamos la siguiente llamada recursiva.

si el índice de la mediana de las medianas i es> k, de forma recursiva llamar seleccionar el k-ésimo elemento más pequeño en el subconjunto izquierdo A [0 ... i]

si el i es < k, selecciono la forma recursiva n - i + k el elemento más pequeño en el subcampo derecho A [i + 1 ... n].

¿Pueden las llamadas recursivas anteriores modificarse como a continuación, lo que reduciría el factor 'k' a 'log k'?

si el índice de la mediana de las medianas i es> k, recursivamente selecciona el k-ésimo elemento más pequeño en el subcampo izquierdo A [0 ... i] y también recursivamente selecciona el n-k-ésimo elemento más pequeño en el subcampo derecho A [i + 1 ... n].

si el i es < k, recursivamente selecciona el n - i + k el elemento más pequeño del subarreglo derecho A [i + 1 ... n] y también selecciona recursivamente el k ésimo elemento más pequeño en el subcampo izquierdo A [ 0 ... i].

La llamada principal sería simplemente seleccionar (A, k, n).

Answer 1

No he seguido su enfoque, pero esta es una pregunta de Int. a Algoritmos por Cormen. De todos modos, estaba buscando una solución yo mismo, y me encantaría compartir mi versión del algoritmo. Intente refutar su corrección:

Supongo que tenemos un algoritmo de búsqueda de estadística O (n). Entonces puedo encontrar la estadística k-ésima en el tiempo O (n). Supongamos que digo que voy a encontrar todos los cuantiles n/k k-th usando el método de dividir y conquistar de manera que:

Si tengo n 'elementos, divido el conjunto en n'/2 partes, informe el límite k-ésimo cuantiles para ambas n '/ 2 particiones. E informa los cuantiles restantes recursivamente. En esencia, lo que estoy haciendo es, después de la partición usando la mediana, extraer el cuantil de la matriz izquierda, el cuantil más a la izquierda de la partición derecha y después de recortar estas matrices ejecutar el algoritmo de forma recursiva. Mi análisis de complejidad resulta ser:

T (n, k) = 2 * T (n/2, k/2) + O (n).

Esto resulta ser O (nlogk) ya que la parte k/2 convergerá más rápido, aunque es posible que desee resolver eso de forma más rigurosa. También hemos usado eso n> k (obvio por el problema. Tenga en cuenta que la tarea de extraer 2 cuantiles y recortar la matriz se hará en O (n)

Answer 2

Tenga en cuenta que usamos un PARTITION modificado al que se le da un índice al pivote para ser utilizado como parámetro de entrada el pasado.

se empieza con KTH-QUANTILES(A, 1, n, 1, k-1, k)

KTH-QUANTILES(A, p, r, i, j, k) 
n=A.length 
m=floor((i+j)/2) 
q=floor(m(n/k)) 
q=q-p+1 
q=SELECT(A, p, r, q) 
q=PARTITION(A, p, r, q) 
if i<m 
    L=KTH-QUANTILES(A, p, q-1, i, m-1, k) 
if m<j 
    R=KTH-QUANTILES(A, q+1, r, m+1, j, k) 
return L U A[q] U R 

la profundidad del árbol recursividad es lg k, ya que la partición se realiza alrededor de la mediana de las estadísticas de orden dado (de i a j).

En cada nivel del árbol de recursión hay operaciones Θ (n), por lo que el tiempo de ejecución es Θ (nlgk).