Encontrando o menor elemento de uma sequência dada apenas com o tempo de memória O (k) O (n)

Suponha que lemos uma sequência de números, um por um. Como encontrar o menor elemento do apenas com o uso da memória da célula e no tempo linear ( ). Acho que devemos salvar os primeiros termos de sequência e, quando obter o termo ', exclua um termo que tenha certeza de que não pode ser o ' é o menor elemento e, em seguida, salve o termo '. Portanto, devemos ter um indicador que mostre esse termo inutilizável em cada etapa e esse indicador deve ser atualizado rapidamente em cada etapa. Eu comecei com "max" ; mas não pode atualizar rapidamente; Significa que se considerarmos max $n$ $k$ $O(k)$ $O(n)$ $k$ $k+1$ $k$ $k+1$ então, na primeira exclusão, perdemos o máximo e devemos procurar o máximo em e sua causa que não é linear. Talvez devêssemos salvar os primeiros termos de sequência de maneira mais inteligente. $O(k)$ $(n-k)\times O(k)$ $k$

Como eu resolvo este problema?

data-structures search-algorithms quicksort Shahab_HK
fonte

Você está interessado em um algoritmo on-line ou faria algum algoritmo?

Yuval Filmus 01/01

Se , você poderá fazê-lo usando o algoritmo de estatísticas da ordem. Se , você pode fazê-lo com memória e tempo usando árvores com altura balanceada.

k = θ (n)

$k = \theta(n)$

k = o (n)

$k = o(n)$

O (k)

$O(k)$

O (n \log k)

$O(n\log k)$

Shreesh

É chamado de problema de seleção en.wikipedia.org/wiki/Selection_algorithm

xavierm02

Existem algoritmos lineares de tempo no local, que você pode pesquisar no Google, mas são um pouco complicados.

Yuval Filmus 01/01

@ xavierm02 não é o problema de seleção de forma idêntica. Porque existe uma restrição de limite de memória.

Shahab_HK

Respostas:

Crie um buffer de tamanho . Leia os elementos da matriz. Use um algoritmo de seleção de tempo linear para particionar o buffer para que os menores elementos sejam os primeiros; isso leva tempo . Agora leia outros itens de sua matriz no buffer, substituindo os maiores itens no buffer, particione o buffer como antes e repita. $2k$ $2k$ $k$ $O(k)$ $k$ $k$

Isso ocupa tempo e espaço. $O(k * n/k) = O(n)$ $O(k)$

jbapple
fonte

+1, isso se encaixa nos assintóticos solicitados. Dito isto, não acredito que isso seja mais rápido do que fazer um único algoritmo de seleção de tempo linear ... exceto quando é uma pequena constante, então ele fornece uma perspectiva interessante. Por exemplo, para esse algoritmo produz a função.

k

$k$

k = 1

$k = 1$ min

orlp

Às vezes, o algoritmo de seleção de tempo linear usa muito espaço. Por exemplo, não é adequado para uso em um contexto de streaming ou quando a matriz de entrada é imutável.

Jbapple #

Esses são pontos válidos.

orlp

$O(k)$ $O(n \log k)$ $k$ $O(k)$ $O(\log k)$ $O(k + n\log k)$ $O(n \log k)$

$O(\log n)$ $O(n)$ $k$ $k$

$O(\log n)$ $O(k)$ $O(\log n)$ $2^{64}$ $\log 2^{64}= 64$ $k$ $n$

orlp
fonte

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

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

@ xavierm02 = . Prova: o pior caso para é . O pior caso para é . Eles são os mesmos dentro de um fator constante, portanto = .

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 Dito isto, ainda é uma boa aceleração :)

orlp

u_{n, k} = k

$u_{n,k}=k$ é mas não é . Suponha que sim. Depois, há alguns e alguns modo que, para cada , temos , o que é claramente falso (porque podemos levar Então .

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)$

precisa saber é o seguinte

@ xavierm02 Não conheço sua notação . Para ser justo, em geral, não estou familiarizado com a notação big- multidimensional , especialmente considerando que as dimensões não são independentes.

u_{n, k}

$u_{n, k}$

O

$O$

n, k

$n, k$

orlp