Limite de espaço para o algoritmo de seleção?

Existe um algoritmo de seleção pior caso conhecido para encontrar o 'ésimo elemento em uma matriz de números inteiros. Ele usa uma abordagem de mediana de medianas para encontrar um pivô bom o suficiente, particiona a matriz de entrada no local e continua recursivamente na busca pelo 'ésimo elemento maior. $O(n)$ $k$ $k$

E se não pudéssemos tocar na matriz de entrada, quanto espaço extra seria necessário para encontrar o 'ésimo elemento em tempo? Podemos encontrar o 'ésimo elemento no espaço extra de e ainda manter o tempo de execução ? Por exemplo, encontrar o elemento máximo ou mínimo ocupa tempo e espaço. $k$ $O(n)$ $k$ $O(1)$ $O(n)$ $O(n)$ $O(1)$

Intuitivamente, não consigo imaginar que pudéssemos fazer melhor que espaço, mas há uma prova disso? $O(n)$

Alguém pode apontar para uma referência ou apresentar um argumento por que o elemento exigiria que espaço fosse encontrado em tempo? $\lfloor n/2 \rfloor$ $O(n)$ $O(n)$

algorithms algorithm-analysis space-complexity lower-bounds user834
fonte

Eu não sou um especialista, mas talvez esses papéis são úteis: Comparação baseada no tempo-espaço Lower Bounds para Seleção e compensações espaço-tempo e problemas de primeira ordem em um modelo de programas

Vor

Respostas:

É um problema em aberto se você pode fazer a seleção com tempo e células de memória extras sem alterar a entrada (veja aqui ). Mas você pode chegar bem perto disso. $O(n)$ $O(1)$

Munro e Raman propuseram um algoritmo para seleção que é executado no tempo enquanto usa apenas armazenamento extra (células). Este algoritmo deixa a entrada inalterada. Você pode escolher qualquer pequeno . $O(n^{1+\varepsilon})$ $O(1/\varepsilon)$ $\varepsilon>0$

Em sua essência, o algoritmo de Munro e Raman funciona como o algoritmo clássico : mantém um limite esquerdo e direito (chamado filtro ), que são dois elementos com classificação conhecida. O elemento solicitado está contido entre os dois filtros (classificação). Escolhendo um bom elemento pivô , podemos verificar todos os números nos filtros . Isso torna possível atualizar os filtros e diminui o número de elementos restantes para verificação (classificação). Repetimos até encontrar o elemento de solicitação. $O(n)$ $p$ $p$

O que é diferente do algoritmo clássico é a escolha de . Seja o algoritmo que resolve a seleção para . O algoritmo divide a matriz em blocos de tamanho igual e identifica um bloco em que existem muitos elementos, cujas fileiras estão entre os filtros (existência pelo princípio do buraco de pombo). Este bloco será verificado em busca de um bom elemento pivô com a ajuda do algoritmo . A âncora de recursão é o algoritmo trivial . O tamanho certo do bloco (e fazendo as contas) fornece os requisitos de tempo e espaço de execução, conforme indicado acima. $p$ $A(k)$ $\varepsilon=1/k$ $A(k)$ $A(k-1)$ $A(1)$

Btw, os algoritmos que você está procurando, foram nomeados recentemente como algoritmos de espaço de trabalho constante .

Não conheço nenhum limite inferior.

A.Schulz
fonte