Fusion de listes d'objets fragiles

Contexte: Chao Xu a posté il y a quelque temps la question suivante: " Existe-t-il des algorithmes de tri de comparaison connus qui ne se réduisent pas à des réseaux de tri, de sorte que chaque élément est comparé fois?$O(\log n)$ ". Il semble que nous soyons un peu coincés avec le problème; J'ai discuté du même problème avec Valentin Polishchuk en 2009, et nous sommes arrivés nulle part.

Pour avoir de nouvelles idées, j'ai essayé de trouver la question la plus simple possible qui a une saveur similaire et n'est pas complètement triviale. D'où la question suivante.

Question: Vous obtenez deux listes triées, chacune avec éléments. Pouvez-vous fusionner les listes pour que chaque élément ne soit comparé que O ( 1 ) fois?$n$$O(1)$

Naturellement, la sortie doit être une liste triée qui contient les éléments.$2n$

[Cela s'est avéré être trivial, la réponse est "non".]

Question 2: Vous obtenez deux listes triées, chacune avec éléments. Pouvez-vous fusionner les listes afin que chaque élément ne soit comparé que O ( 1 ) fois, si vous êtes autorisé à supprimer une petite fraction des éléments ?$n$$O(1)$

Plus précisément, la sortie doit être une liste triée qui contient éléments, et une «poubelle» qui contient T ( n ) éléments. Comment pouvez-vous faire la valeur T ( n ) ? Obtenir T ( n ) = n est trivial. Quelque chose comme T ( n ) = n / 100 devrait être réalisable de manière simple. Mais pouvez-vous obtenir T ( n ) = o ( $2n-T(n)$$T(n)$$T(n)$$T(n) = n$$T(n) = n/100$ ?$T(n) = o(n)$

Remarques:

• Nous utilisons ici le modèle de comparaison. Algorithmes déterministes uniquement, nous nous intéressons aux pires garanties.

• Notez que les deux listes ont exactement éléments. Si nous avions une liste avec n éléments et une autre avec 1 élément, la réponse est clairement «non»; cependant, si les deux listes sont longues, il semble que l'on pourrait être en mesure de faire un "équilibrage de charge".$n$$n$$1$

• Cette fois, tout type d'algorithme est valide. Si votre algorithme utilise des réseaux de tri comme bloc de construction, cela convient parfaitement.

• Pour un point de départ, voici un algorithme simple qui compare chaque élément au maximum 200 fois: Utilisez simplement l'algorithme de fusion standard, mais conservez des compteurs pour les têtes des listes. Une fois que vous avez atteint 200, jetez l'élément. Maintenant, pour chaque élément que vous supprimez, vous avez réussi à placer 200 éléments dans votre tableau de sortie. Vous avez donc atteint .$T(n) = n/100$

Non, un tel algorithme ne peut pas exister.

Assume sont autorisés comparaisons par élément.$t$

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

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

$t$$o(n)$

Sur une note latérale, il semble qu'il soit possible de faire correspondre cela lié par un algorithme où chaque élément est comparé à environ logarithme de la taille de la partie environnante de l'autre liste. Si cela vous intéresse, je vais essayer de trouver les détails.