Mesclando listas de objetos frágeis

Antecedentes: Chao Xu postou a seguinte pergunta há algum tempo: " Existe algum algoritmo de classificação de comparação conhecido que não se reduz a redes de classificação, de modo que cada elemento seja comparado vezes?$O(\log n)$ ". Parece que estamos um pouco presos ao problema; Discuti o mesmo problema com Valentin Polishchuk em 2009 e não chegamos a lugar algum.

Para obter algumas idéias novas, tentei formular a pergunta mais simples possível, com um sabor semelhante e que não é completamente trivial. Daí a seguinte pergunta.

Pergunta: Você recebe duas listas classificadas, cada uma delas com elementos. Você pode mesclar as listas para que cada elemento seja comparado apenas vezes?$n$$O(1)$

Naturalmente, a saída deve ser uma lista classificada que contenha todos os elementos .$2n$

[Isso acabou sendo trivial, a resposta é "não".]

Pergunta 2: Você recebe duas listas classificadas, cada uma delas com elementos. Você pode mesclar as listas para que cada elemento seja comparado apenas vezes, se você puder descartar uma pequena fração de elementos ?$n$$O(1)$

Mais precisamente, a saída deve ser uma lista classificada que contém elementos e uma "lixeira" que contém elementos . Quão pequeno você pode fazer o valor ? Obter é trivial. Algo como deve ser factível de maneira direta. Mas você pode obter ?$2n-T(n)$$T(n)$$T(n)$$T(n) = n$$T(n) = n/100$$T(n) = o(n)$

Notas:

• Nós usamos o modelo de comparação aqui. Somente algoritmos determinísticos, estamos interessados ​​nas piores garantias.

• Observe que ambas as listas possuem exatamente elementos. Se tivéssemos uma lista com elementos e outra com elemento, a resposta é claramente "não"; no entanto, se as duas listas forem longas, parece que alguém poderá fazer algum "balanceamento de carga".n $n$$n$$1$

• Desta vez, qualquer tipo de algoritmo é válido. Se o seu algoritmo usa redes de classificação como um componente básico, está perfeitamente correto.

• Para um ponto de partida, aqui está um algoritmo simples que compara cada elemento no máximo 200 vezes: basta usar o algoritmo de mesclagem padrão, mas mantenha os contadores para os cabeçalhos das listas. Quando chegar a 200, descarte o elemento. Agora, para cada elemento que você descarta, você colocou com sucesso 200 elementos em sua matriz de saída. Portanto, você atingiu .$T(n) = n/100$

Não, esse algoritmo não pode existir.

Assumem comparações por elemento são permitidos.$t$

Para começar, considere a situação de mesclar duas listas, uma de tamanho um e outra de tamanho $2^t$$2^t+1$$t+1$

A partir disso, é fácil construir uma instância com duas listas de tamanho que consiste em n $n$$n/2^t$$n/2^t$

$t$$o(n)$

Em uma nota lateral, parece que é possível corresponder a esse limite por um algoritmo em que cada elemento é comparado com aproximadamente o log do tamanho da parte circundante da outra lista. Se isso for interessante, tentarei descobrir os detalhes.