¿Cómo encontrar el k-ésimo elemento más grande en una matriz sin clasificar de longitud n en O (n)?
Creo que hay una manera de encontrar el k-ésimo elemento más grande en una matriz sin clasificar de longitud n en O(n). O tal vez sea O(n) "esperado" o algo así. ¿Cómo podemos hacer esto?
A esto se le llama encontrar el estadístico de orden k . Hay un algoritmo aleatorio muy simple (llamado selección rápida ) que toma O(n)el tiempo promedio, O(n^2)el tiempo en el peor de los casos, y un algoritmo no aleatorio bastante complicado (llamado introselect ) que toma O(n)el tiempo en el peor de los casos. Hay algo de información en Wikipedia , pero no es muy buena.
Todo lo que necesitas está en estas diapositivas de PowerPoint . Solo para extraer el algoritmo básico del O(n)algoritmo del peor de los casos (introselección):
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
También está muy bien detallado en el libro Introducción a los algoritmos de Cormen et al.
Si desea un O(n)algoritmo verdadero, a diferencia de O(kn)algo así, entonces debe usar la selección rápida (básicamente es una clasificación rápida donde descarta la partición que no le interesa). Mi profesor tiene un excelente artículo, con el análisis del tiempo de ejecución: ( referencia )
El algoritmo QuickSelect encuentra rápidamente el k-ésimo elemento más pequeño de una matriz de nelementos sin clasificar. Es un algoritmo aleatorio , por lo que calculamos el tiempo de ejecución esperado en el peor de los casos .
Aquí está el algoritmo.
QuickSelect(A, k)
let r be chosen uniformly at random in the range 1 to length(A)
let pivot = A[r]
let A1, A2 be new arrays
# split into a pile A1 of small elements and A2 of big elements
for i = 1 to n
if A[i] < pivot then
append A[i] to A1
else if A[i] > pivot then
append A[i] to A2
else
# do nothing
end for
if k <= length(A1):
# it's in the pile of small elements
return QuickSelect(A1, k)
else if k > length(A) - length(A2)
# it's in the pile of big elements
return QuickSelect(A2, k - (length(A) - length(A2))
else
# it's equal to the pivot
return pivot
¿Cuál es el tiempo de ejecución de este algoritmo? Si el adversario lanza monedas por nosotros, podemos encontrar que el pivote es siempre el elemento más grande y ksiempre es 1, lo que da un tiempo de ejecución de
T(n) = Theta(n) + T(n-1) = Theta(n2)Pero si las elecciones son realmente aleatorias, el tiempo de ejecución esperado viene dado por
T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))donde asumimos, no del todo razonablemente razonable, que la recursividad siempre cae en el mayor de A1o A2.
Adivinemos eso T(n) <= anpara algunos a. Entonces obtenemos
T(n)
<= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
= cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n aiy ahora de alguna manera tenemos que conseguir que la horrenda suma a la derecha del signo más absorba la cnde la izquierda. Si lo vinculamos como , obtenemos aproximadamente . Pero esto es demasiado grande: no hay espacio para meter uno extra . Entonces, expandamos la suma usando la fórmula de la serie aritmética:2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn
∑i=floor(n/2) to n i
= ∑i=1 to n i - ∑i=1 to floor(n/2) i
= n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
<= n2/2 - (n/4)2/2
= (15/32)n2donde aprovechamos que n es "suficientemente grande" para reemplazar los floor(n/2)factores feos por otros mucho más limpios (y más pequeños) n/4. Ahora podemos continuar con
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= anproporcionó a > 16c.
Esto da T(n) = O(n). Está claro Omega(n), así que lo entendemos T(n) = Theta(n).
