encontrar los elementos k más pequeños en la matriz en O (k)

12

Esta es una pregunta interesante que he encontrado en la web. Dada una matriz que contiene n números (sin información sobre ellos), debemos preprocesar la matriz en tiempo lineal para que podamos devolver los k elementos más pequeños en el tiempo O (k), cuando se nos da un número 1 <= k <= n

He estado discutiendo este problema con algunos amigos pero nadie pudo encontrar una solución; ¡Cualquier ayuda sería apreciada!

notas rápidas: -el orden de los k elementos más pequeños no es importante -los elementos en la matriz son número, pueden ser enteros y pueden no serlo (por lo que no hay clasificación de radix) -el número k no se conoce en la etapa de preprocesamiento. el preprocesamiento es O (n) tiempo. la función (encontrar k elementos más pequeños) en el tiempo O (k).

Idan
fuente
44
¿Qué hay de usar un montón mínimo?
Shir
1
Mire la computación k-skyband y top-k. El documento cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf tiene una buena revisión de la literatura relacionada.
András Salamon
1
Shir-he examinado la idea del montón mínimo. sin embargo, para imprimir los k números más pequeños en el montón mínimo es en tiempo O (klogn) y no O (k) como se requiere
Idan
44
@idannik: ¿Por qué crees que lleva tiempo encontrar los elementos más pequeños en un montón mínimo? kΩ(klogn)k
Kristoffer Arnsfelt Hansen
8
No creo que esto sea a nivel de investigación. Parece una tarea. ¿Dónde lo encontraste?
Kaveh

Respuestas:

24

Preprocese la matriz de valores en el tiempo :O ( n )nO(n)

  • in
  • mientrasi>2
    • Calcule la mediana de en el tiempoA [ 1 .. i ] O ( i )mA[1..i]O(i)
    • partición en A [ 1 .. i / 2 - 1 ] m y A [ i / 2 + 1 .. i ] m en el mismo tiempo.A[1..i]A[1..i/21]mA[i/2+1..i]m
    • ii/2

El tiempo total de precálculo está dentro de O(1+2+4+...+n)O(n)

Responda una consulta para los elementos más pequeños en A en el tiempo O ( k ) :kAO(k)

  • llog2k
  • seleccione el th elemento x de A [ 2 l . .2 l + 1 ] en el tiempo O ( 2 l ) O ( k )(k2l)xA[2l..2l+1]O(2l)O(k)
  • partición por x al mismo tiempoA[2l..2l+1]x

contiene los k elementos más pequeños.A[1..k]k

Referencias

  • En 1999, Dor y Zwick dieron un algoritmo para calcular la mediana de elementos en el tiempo dentro de 2.942 n + o ( n ) comparaciones, lo que arroja un algoritmo para seleccionar el elemento k entre n elementos no ordenados en menos de 6 n comparaciones.n2.942n+o(n)kn6n
Jeremy
fuente
1
Supongo que se supone que el bucle externo es 'para i en '. ¿Es su algoritmo diferente al de la respuesta de Yuval Filmus? {2lgn,,4,2,1}
Radu GRIGore
2
Esta es una generalización de mi algoritmo a arbitraria . También detalla algunos detalles de implementación que fueron (deliberadamente) omitidos en mi respuesta. n
Yuval Filmus
3
@YuvalFilmus ¿Desea implicar por su comentario que mi respuesta es poco ética a la suya? Esta es la solución que se me ocurrió cuando revisé la pregunta. Vi que publicaste uno similar, pero lo encontré poco claro, así que escribí el mío (en lugar de hacer una gran edición tuya). Lo que importa en última instancia es la calidad de las respuestas en los sistemas, no realmente quién las escribió: las insignias y la reputación son solo incentivos, no objetivos en sí mismos.
Jeremy
44
@ Jeremy No, en absoluto; Solo que las dos soluciones son las mismas (pero la tuya funciona para arbitraria ), y que no realicé los detalles en caso de que realmente fuera una pregunta de tarea. n
Yuval Filmus
2
Oh :( Lo siento por eso entonces. (Aunque todavía pensaría que dar respuestas completas es una prioridad sobre las sospechas de asignación)
Jeremy
14

Supongamos por simplicidad que . Use el algoritmo de selección de tiempo lineal para encontrar los elementos en las posiciones 2 m - 1 , 2 m - 2 , 2 m - 3 , ... , 1 ; Esto lleva tiempo lineal. Dado k , encuentre t tal que 2 t - 1k 2 t ; tenga en cuenta que 2 t2 k . Filtrar todos los elementos de rango como máximo 2 tn=2m2m1,2m2,2m3,,1kt2t1k2t2t2k2t, y ahora use el algoritmo de selección de tiempo lineal para encontrar el elemento en la posición en el tiempo O ( 2 t ) = O ( k ) .kO(2t)=O(k)

Aclaración: puede parecer que el preprocesamiento lleva tiempo , y ese es el caso si no tiene cuidado. Aquí se explica cómo hacer el preprocesamiento en tiempo lineal:Θ(nlogn)

while n > 0:
  find the (lower) median m of A[0..n-1]
  partition A in-place so that A[n/2-1] = m
  n = n/2

n+n/2+n/4++1<2nAkA[0..n/2k1]n/2k

Yuval Filmus
fuente
1
O(1)kO(n)
44
lognnlogn
3
@ AndrásSalamon: Si lees la respuesta dada por Jeremy (que me parece casi igual a esta), ves que primero procesas toda la matriz, luego la primera mitad, y así sucesivamente.
Radu GRIGore
3
n+n/2+n/4++1<2n
55
Por cierto, este algoritmo aparece como una subrutina en mi respuesta a una pregunta anterior: cstheory.stackexchange.com/questions/17378/…
David Eppstein
0

kk

jbapple
fuente
1
k
2
Veo. Mi error.
jbapple