Слияние списков хрупких объектов

19

Справочная информация: Чао Сюй некоторое время назад опубликовал следующий вопрос: « Существуют ли какие-либо известные алгоритмы сортировки сравнения, которые не сводятся к сортировке сетей, так что каждый элемент сравнивается раз?O(logn) ». Кажется, мы немного застряли в проблеме; Я обсуждал ту же проблему с Валентином Полищуком в 2009 году, и мы ни к чему не привели.

Чтобы получить свежие идеи, я попытался найти простейший из возможных вопросов, который имеет схожий вкус и не совсем тривиален. Отсюда следующий вопрос.


Вопрос: Вам даны два отсортированных списка, каждый из которых состоит из элементов. Можете ли вы объединить списки так, чтобы каждый элемент сравнивался только O ( 1 ) раз?nO(1)

Естественно, вывод должен быть отсортированным списком, который содержит все элементов.2n

[Это оказалось тривиальным, ответ «нет».]


Вопрос 2: Вам даны два отсортированных списка, каждый из которых состоит из элементов. Можете ли вы объединить списки так, чтобы каждый элемент сравнивался только O ( 1 ) раз, если вам разрешено отбрасывать небольшую часть элементов ?nO(1)

Точнее, выходные данные должны быть отсортированным списком, который содержит элементов, и «мусорную корзину», которая содержит T ( n ) элементов. Как мало вы можете сделать значение T ( n ) ? Получение T ( n ) = n тривиально. Нечто подобное T ( n ) = n / 100 должно быть выполнимо прямым способом. Но вы можете получить T ( N ) = O ( N2nT(n)T(n)T(n)T(n)=nT(n)=n/100 ?T(n)=o(n)


Примечания:

  • Мы используем модель сравнения здесь. Только детерминированные алгоритмы, нас интересуют гарантии наихудшего случая.

  • Обратите внимание, что оба списка имеют ровно элементов. Если бы у нас был один список с n элементами, а другой с 1 элементом, ответ однозначно «нет»; Однако, если оба списка давно, кажется , что один может быть в состоянии сделать некоторые «балансировка нагрузки».nn1

  • На этот раз любой вид алгоритма действителен. Если ваш алгоритм использует сортировку сетей в качестве строительного блока, это прекрасно.

  • T(n)=n/100

Юкка Суомела
источник
8
Вы сказали, что «Если бы у нас был один список с n элементами, а другой с 1 элементом, ответ однозначно - нет». Разве случай с n элементами в каждом списке не является более общей проблемой? Например, если нам обещают, что все элементы во втором списке, кроме первого, намного больше, чем все элементы в первом списке, не сводится ли это к первой проблеме?
Робин Котари
Ω(logn)
T(n)

Ответы:

5

Нет, такой алгоритм не может существовать.

t

2t2t+1t+1

nn/2tn/2t

to(n)

С другой стороны, кажется, что можно сопоставить эту границу с помощью алгоритма, в котором каждый элемент сравнивается примерно с логарифмом размера окружающей части другого списка. Если это будет интересно, я постараюсь проработать детали.

Рико Джейкоб
источник