Num artigo clássico, Munro e Paterson estudam o problema de quanto armazenamento é necessário para que um algoritmo encontre a mediana em uma matriz classificada aleatoriamente. Em particular, eles se concentram no seguinte modelo:
a entrada é lida da esquerda para a direita por um número P de vezes.
É mostrado que as células de memória são suficientes, mas o limite inferior correspondente é conhecido apenas por P = 1. Não vi nenhum resultado para P> 1. Alguém está ciente desses limites inferiores?
Observe que a principal dificuldade aqui é que, na segunda passagem, a entrada não é mais ordenada aleatoriamente.
ds.algorithms
space-bounded
data-streams
MassimoLauria
fonte
fonte
O primeiro artigo a provar limites por mais de 1 passe foi o meu artigo com Jayram e Amit da SODA'08. Depois, há o artigo que Warren mencionou, que melhora os limites com uma prova mais limpa.
Em resumo, entendemos a dependência se você permitir constantes antes do número de passes. Obviamente, essas constantes estão no expoente, para que você possa solicitar um entendimento preciso. Minha principal reclamação é que o modelo de streaming multipass não é tão motivado.
A questão mais intrigante é se podemos provar um limite inferior do programa de ramificação. Pode ser que, mesmo para um algoritmo de espaço delimitado que possa acessar a memória como deseje, a melhor estratégia seja apenas fazer o streaming multipass?
A resposta parece afirmativa e temos algum progresso parcial no sentido de prová-la.
fonte