Encontrar el elemento k'th más pequeño de una secuencia dada solo con O (k) memoria O (n) tiempo

Supongamos que leemos una secuencia de números, uno por uno. Cómo encontrar el elemento más pequeño de 'con solo usar la memoria de celda y en tiempo lineal ( ). Creo que deberíamos guardar los primeros términos de secuencia y, cuando obtengamos el término ', eliminemos un término que estamos seguros de que no puede ser el ' elemento más pequeño y luego guardemos 'término. Por lo tanto, deberíamos tener un indicador que muestre este término inutilizable en cada paso y este indicador debería actualizarse en cada paso rápidamente. Empecé con "max" ; pero no puede actualizarse rápidamente; Significa que si consideramos max $n$ $k$ $O(k)$ $O(n)$ $k$ $k+1$ $k$ $k+1$ luego, en la primera eliminación, perdemos el máximo y debemos buscar el máximo en y su causa tiempo en que no es lineal. Tal vez deberíamos guardar los primeros términos de secuencia de manera más inteligente. $O(k)$ $(n-k)\times O(k)$ $k$

¿Cómo resuelvo este problema?

data-structures search-algorithms quicksort Shahab_HK
fuente

¿Está interesado en un algoritmo en línea, o algún algoritmo lo haría?

Yuval Filmus el

Si , puede hacerlo utilizando el algoritmo de estadísticas de pedidos. Si entonces puede hacerlo memoria y usando cualquier árbol de altura equilibrada.

k = θ (n)

$k = \theta(n)$

k = o (n)

$k = o(n)$

O (k)

$O(k)$

O (n \log k)

$O(n\log k)$

Shreesh

Se llama el problema de selección en.wikipedia.org/wiki/Selection_algorithm

xavierm02

Hay algoritmos de tiempo lineal en el lugar, que puedes buscar en Google, pero son algo complicados.

Yuval Filmus

@ xavierm02 no es el problema de selección de forma idéntica. Porque hay una restricción de límite de memoria.

Shahab_HK

Respuestas:

Crea un búfer de tamaño . Lea en elementos de la matriz. Use un algoritmo de selección de tiempo lineal para dividir el búfer de modo que los elementos más pequeños sean los primeros; esto lleva tiempo. Ahora lea otros elementos de su matriz en el búfer, reemplazando los elementos más grandes en el búfer, particione el búfer como antes y repita. $2k$ $2k$ $k$ $O(k)$ $k$ $k$

Esto toma tiempo y espacio. $O(k * n/k) = O(n)$ $O(k)$

jbapple
fuente

+1, esto se ajusta a las asintóticas solicitadas. Dicho esto, no creo que esto sea más rápido que hacer un solo algoritmo de selección de tiempo lineal ... excepto cuando es una constante pequeña, entonces proporciona una perspectiva interesante. Por ejemplo, para este algoritmo produce la función.

k

$k$

k = 1

$k = 1$ min

orlp

A veces, el algoritmo de selección de tiempo lineal usa demasiado espacio. Por ejemplo, no es adecuado para su uso en un contexto de transmisión o cuando la matriz de entrada es inmutable.

jbapple

Esos son puntos válidos.

orlp

Puede hacerlo en la memoria y el tiempo formando un montón máximo de tamaño fijo a partir de los primeros elementos en el tiempo , luego iterando sobre el resto de la matriz y presionando un nuevo elemento y luego aparece para cada elemento dando tiempo total = . $O(k)$ $O(n \log k)$ $k$ $O(k)$ $O(\log k)$ $O(k + n\log k)$ $O(n \log k)$

Puede hacerlo en la memoria auxiliar y el tiempo utilizando el algoritmo de selección de mediana de medianas, seleccionando en y devolviendo los primeros elementos. Sin cambios en los asintóticos, puede usar introselect para acelerar el caso promedio. Esta es la forma canónica de resolver su problema. $O(\log n)$ $O(n)$ $k$ $k$

Ahora técnicamente y son incomparables. Sin embargo, sostengo que es mejor en la práctica, ya que es efectivamente constante teniendo en cuenta que ningún sistema informático tiene más de bytes de memoria, . Mientras tanto, puede llegar a ser tan grande como . $O(\log n)$ $O(k)$ $O(\log n)$ $2^{64}$ $\log 2^{64}= 64$ $k$ $n$

orlp
fuente

Tenga en cuenta que puede mejorar la complejidad del algoritmo basado en el montón a invirtiendo el orden utilizado por el montón cuando sea interesante.

O (n \times \log min (k, n - k))

$O(n \times \log\min (k, n - k))$

xavierm02

@ xavierm02 = . Prueba: el peor caso para es . El peor caso para es . Son iguales dentro de un factor constante, por lo tanto, = .

O (m i n (k, n - k))

$O(min(k, n-k))$

O (k)

$O(k)$

k

$k$

n

$n$

m i n (k, n - k)

$min(k, n-k)$

\frac{n}{2}

$n \over 2$

O (m i n (k, n - k))

$O(min(k, n-k))$

O (k)

$O(k)$

orlp

@ xavierm02 Dicho esto, sigue siendo una buena aceleración :)

orlp

u_{n, k} = k

$u_{n,k}=k$ es pero no es . Supongamos que lo es. Luego hay algo de y algo de modo que por cada , tenemos , que es claramente falso (porque podemos tomar Entonces .

O (k)

$O(k)$

O (min (k, n - k))

$O(\min (k, n-k))$

C

$C$

M

$M$

M \leq k \leq n

$M\le k\le n$

k \leq C (n - k)

$k\le C (n-k)$

n = k \to + \infty) .

$n=k \to +\infty).$

O (min (k, n - k)) ⊊ O (k)

$O(\min(k, n-k))\subsetneq O(k)$

xavierm02

@ xavierm02 No estoy familiarizado con tu . Para ser justos, en general no estoy familiarizado con la notación big- multidimensional , especialmente teniendo en cuenta que las dimensiones no están relacionadas.

u_{n, k}

$u_{n, k}$

O

$O$

n, k

$n, k$

orlp