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).
Respuestas:
Preprocese la matriz de valores en el tiempo :O ( n )norte O ( n )
El tiempo total de precálculo está dentro deO ( 1 + 2 + 4 +...+n)⊆O(n)
Responda una consulta para los elementos más pequeños en A en el tiempo O ( k ) :k UN O ( k )
contiene los k elementos más pequeños.A [ 1 .. k ] k
Referencias
fuente
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 - 1 ≤ k ≤ 2 t ; tenga en cuenta que 2 t ≤ 2 k . Filtrar todos los elementos de rango como máximo 2 tn=2m 2m−1,2m−2,2m−3,…,1 k t 2t−1≤k≤2t 2t≤2k 2t , 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 ) .k O(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)
fuente
Frederickson, Greg N. , Un algoritmo óptimo para la selección en un montón mínimo , Inf. Comput 104, núm. 2, 197-214 (1993). ZBL0818.68065 ..
fuente
fuente