Fusionar listas de objetos frágiles

Antecedentes: Chao Xu publicó la siguiente pregunta hace algún tiempo: " ¿Hay algún algoritmo de clasificación de comparación conocido que no se reduzca a redes de clasificación, de modo que cada elemento se compare veces?$O(\log n)$ ". Parece que estamos un poco atascados con el problema; He discutido el mismo problema con Valentin Polishchuk en 2009, y no llegamos a ningún lado.

Para obtener algunas ideas nuevas, traté de hacer la pregunta más simple posible que tenga un sabor similar y no sea completamente trivial. De ahí la siguiente pregunta.

Pregunta: Se le dan dos listas ordenadas, cada una de ellas con elementos. ¿Puedes fusionar las listas para que cada elemento solo se compare veces?$n$$O(1)$

Naturalmente, la salida debe ser una lista ordenada que contenga todos los elementos .$2n$

[Esto resultó ser trivial, la respuesta es "no".]

Pregunta 2: Se le dan dos listas ordenadas, cada una de ellas con elementos. ¿Puedes fusionar las listas para que cada elemento solo se compare veces, si puedes descartar una pequeña fracción de elementos ?$n$$O(1)$

Más precisamente, el resultado debe ser una lista ordenada que contenga elementos y una "papelera" que contenga elementos . ¿Qué tan pequeño puede hacer el valor ? Obtener es trivial. Algo como debería ser factible de una manera directa. Pero, ¿puedes obtener ?T ( n ) T ( n ) T ( n ) = n T ( n ) = n / 100 T ( n ) = o ( n $2n-T(n)$$T(n)$$T(n)$$T(n) = n$$T(n) = n/100$$T(n) = o(n)$

Notas:

• Usamos el modelo de comparación aquí. Solo algoritmos deterministas, estamos interesados ​​en las garantías del peor de los casos.

• Tenga en cuenta que ambas listas tienen exactamente elementos. Si teníamos una lista con elementos y otra con elemento, la respuesta es claramente "no"; sin embargo, si ambas listas son largas, parece que uno podría hacer algo de "equilibrio de carga".n $n$$n$$1$

• Esta vez, cualquier tipo de algoritmo es válido. Si su algoritmo usa redes de clasificación como un bloque de construcción, está perfectamente bien.

• Como punto de partida, aquí hay un algoritmo simple que compara cada elemento como máximo 200 veces: solo use el algoritmo de fusión estándar, pero mantenga los contadores para los encabezados de las listas. Una vez que alcances 200, descarta el elemento. Ahora, por cada elemento que descarte, ha colocado con éxito 200 elementos en su matriz de salida. Por lo tanto, ha logrado .$T(n) = n/100$

No, dicho algoritmo no puede existir.

$t$

$2^t$$2^t+1$$t+1$

$n$$n/2^t$$n/2^t$

$t$$o(n)$

En una nota al margen, parece que es posible hacer coincidir esto limitado por un algoritmo donde cada elemento se compara con aproximadamente el registro del tamaño de la parte circundante de la otra lista. Si esto es de interés, intentaré resolver los detalles.