Справочная информация: Чао Сюй некоторое время назад опубликовал следующий вопрос: « Существуют ли какие-либо известные алгоритмы сортировки сравнения, которые не сводятся к сортировке сетей, так что каждый элемент сравнивается раз? ». Кажется, мы немного застряли в проблеме; Я обсуждал ту же проблему с Валентином Полищуком в 2009 году, и мы ни к чему не привели.
Чтобы получить свежие идеи, я попытался найти простейший из возможных вопросов, который имеет схожий вкус и не совсем тривиален. Отсюда следующий вопрос.
Вопрос: Вам даны два отсортированных списка, каждый из которых состоит из элементов. Можете ли вы объединить списки так, чтобы каждый элемент сравнивался только O ( 1 ) раз?
Естественно, вывод должен быть отсортированным списком, который содержит все элементов.
[Это оказалось тривиальным, ответ «нет».]
Вопрос 2: Вам даны два отсортированных списка, каждый из которых состоит из элементов. Можете ли вы объединить списки так, чтобы каждый элемент сравнивался только O ( 1 ) раз, если вам разрешено отбрасывать небольшую часть элементов ?
Точнее, выходные данные должны быть отсортированным списком, который содержит элементов, и «мусорную корзину», которая содержит T ( n ) элементов. Как мало вы можете сделать значение T ( n ) ? Получение T ( n ) = n тривиально. Нечто подобное T ( n ) = n / 100 должно быть выполнимо прямым способом. Но вы можете получить T ( N ) = O ( N ?
Примечания:
Мы используем модель сравнения здесь. Только детерминированные алгоритмы, нас интересуют гарантии наихудшего случая.
Обратите внимание, что оба списка имеют ровно элементов. Если бы у нас был один список с n элементами, а другой с 1 элементом, ответ однозначно «нет»; Однако, если оба списка давно, кажется , что один может быть в состоянии сделать некоторые «балансировка нагрузки».
На этот раз любой вид алгоритма действителен. Если ваш алгоритм использует сортировку сетей в качестве строительного блока, это прекрасно.
источник
Ответы:
Нет, такой алгоритм не может существовать.
С другой стороны, кажется, что можно сопоставить эту границу с помощью алгоритма, в котором каждый элемент сравнивается примерно с логарифмом размера окружающей части другого списка. Если это будет интересно, я постараюсь проработать детали.
источник