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

11

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 maxnkO(k)O(n)kk+1kO ( k ) ( n - k ) × O ( k ) kk+1entã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)(nk)×O(k)k

Como eu resolvo este problema?

Shahab_HK
fonte
1
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=o(n)O(k)O(nlogk)
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:

16

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.2 k k O ( k ) k k2k2kkO(k)kk

Isso ocupa tempo e espaço.O ( k )O(kn/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 = 1kk=1min
orlp
1
À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
3

O(k)O(nlogk)kO(k)O(logk)O(k+nlogk)O(nlogk)

O(logn)O(n)kk

O(logn)O(k)O(logn)264log264=64kn

orlp
fonte
O(n×logmin(k,nk))
@ xavierm02 = . Prova: o pior caso para é . O pior caso para é . Eles são os mesmos dentro de um fator constante, portanto = . O(min(k,nk))O(k)knmin(k,nk)n2O(min(k,nk))O(k)
orlp
@ xavierm02 Dito isto, ainda é uma boa aceleração :)
orlp
un,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(min(k,nk))CMMknkC(nk)n=k+).O(min(k,nk))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. ó n , kun,kOn,k
orlp