Предположим, что мы хотим отсортировать список из действительных чисел. Предположим, что нам дан черный ящик, который может мгновенно отсортировать реальных чисел. Какое преимущество мы можем получить, используя этот черный ящик?n √
Например, можем ли мы отсортировать номера только с помощью вызовов в черный ящик? Лучший алгоритм, который я нашел, использует вызовов черного ящика. Но я не смог улучшить его дальше. Вот мой алгоритм, который похож на сортировку слиянием:н
Сначала разбейте список на списков примерно с размером. Затем используйте вызовов черного ящика для сортировки этих списков. Наконец, объедините отсортированные списки, используя черный ящик следующим образом:√ ы1,ев2,. , , ,с √ √ √
Поместите наименьшие элементы списков в новый список , затем вызовите черный ящик, чтобы отсортировать его. Число в (первый и наименьший элемент ) будет наименьшим номером в . Мы можем поставить его на первое место в списке вывода.
Если предположить , что элемент был выбран из , заменим с вторым наименьшим элементом списка сортировки , и снова запустить черный ящик на нем , чтобы вычислить второй наименьший элемент из .
Мы продолжаем, пока все элементы не отсортированы. Общее количество вызовов черного ящика для этой части будетL [ 1 ] L S s j L [ 1 ] s j S n - √
, Поэтому общее количество звонков будет .
С другой стороны, похоже, что мы должны быть в состоянии получить нижнюю границу, используя нижнюю границу для сравнения чисел, необходимых для сортировки, следующим образом: Мы можем реализовать черный ящик, используя сравнений. Если мы сможем решить эту проблему с помощью вызовов в черный ящик и слияния в линейное время, мы можем отсортировать действительных чисел с помощью сравнений, что невозможно.o( √no(nlgn)
Я предполагаю, что мы могли бы доказать, что является нижней границей для количества вызовов в черный ящик, поскольку многие сравнения, используемые в черном ящике, будут разделены и, следовательно, будут пересчитаны в нашем аргументе.
ОБНОВЛЕНИЕ: Как и в других сообщениях, также достижимо.
Ответы:
Можно сортировать с помощью звонки в черный ящик и никаких сравнений.O ( n--√журналн )
Сначала рассмотрим следующую проблему сбалансированного разбиения: дано элементов A [ 1 .. m ] (где √м A [ 1 .. м ] ), разделите их на две группы, наименьший размер которых должен составлять не менееm/4, чтобы все элементы в первой группе были меньше, чем все элементы во второй группе. Это можно сделать с помощьюO(m/ √N--√≤ m ≤ n м / 4 звонки в черный ящик. (Я опишу это позже.) Затем используйте быструю сортировку с этим алгоритмом разделения:O ( м / н--√)
Предполагая, что каждый шаг разбиения занимает вызовы черного ящика, приведенный выше алгоритм, учитывая входA[1 ..n], сделаетO( √O ( м / н--√) A [ 1 .. n ] обращается к черному ящику, потому что дерево рекурсии имеет глубинуO(logn),и каждый уровень дерева имеет в общей сложностиO(n/ √O ( n--√журналн ) O ( журналн ) звонки в черный ящик.O ( н / н--√) = O ( n--√)
Сделайте шаг разбиения следующим образом:
источник
Я думаю, что ваш вопрос был рассмотрен в статье Бейгеля и Джилла " Сортировка n объектов с использованием k-sorter " от 1990 года, и реферат статьи говорит сам за себя:
источник
источник