Как разработать эффективного противника для сортировки?

Question

Мы знаем, что теоретически информация о количестве сравнений для алгоритма сортировки на основе сравнения равна ceil (lg (n!)), Где lg обозначает логарифм с основанием 2.

Мы можем построить противника, где мы выберемупорядочение путем подсчета количества линейных расширений для частичного порядка в обоих случаях, если меньше или больше.Какой бы путь не имел более высоких линейных расширений, выберите этот путь.(Это автоматически устраняет несоответствия, потому что если ответ с одной стороны непоследователен, он будет равен нулю, а другой будет таким же, как предыдущий)

Однако такой злоумышленник неэффективен, так как подсчет числа линейныйрасширение до частичного заказа составляет # P-complete .

Другой вариант - использовать более простого противника за полиномиальное время, которое делает:

1. a> b, если a никогда не проигрывал, а b проигрывал хотя бы один раз.
2. a> b, если как непобедимый, так и a имеет больше побед, чем b.
3. a> b, если частичный порядок заставляет a> b
4. a выберите любой другой вариант.

Этот злоумышленник взят из книги «Искусство компьютерного программирования», том 3, второе издание, стр. 209. Он хорошо работает для таких задач, как поиск второго по величине элемента, поскольку он вызывает n + ceil (lg (n)) - 2 сравнения.К сожалению, это не навязывает теоретическую информацию для сортировки.Это остается верным, даже если я добавлю больше эвристик, таких как доминирующий счетчик (количество значений, которое оно больше, чем), для сравнения вместо случайного выбора порядка.

Я знаю, что это не принудительно, поскольку Collections.sort () вJava 8 сортирует 23-элементный массив в 74 сравнениях, когда нижняя граница равна 75. Исходный код показывает, что для всех чисел, меньших 23, он смог форсировать нижнюю границу, для 100 чисел sort () удалосьделать 506 сравнений, когда нижняя граница равна 525.

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

Answer 1

Существует «вероятно приблизительно успешный» противник за полиномиальное время, который использует рандомизацию для (например) принудительного сравнения ceil (lg (n!) - n ⁻¹⁰⁰ ) с вероятностью не менее 1 - n ⁻¹⁰⁰ .

Ключевая идея заключается в том, что, хотя подсчет количества линейных расширений является сложным, выборка равномерных случайных расширений проста (ну, по крайней мере, за полиномиальное время), следовательно, мы можем получитьвероятно, приблизительно правильная оценка количества расширений с a b.Очевидно, что мы не можем сказать, что более вероятно, если отсчеты достаточно близки, но, взяв достаточно выборок (но все же полиномиальное число), мы можем с уверенностью обеспечить использование границы Хоффдинга, которая с вероятностью не менее 1 - n ⁻¹⁰² , исход, который выбирает противник, согласуется по крайней мере с 1/2 - n ⁻¹⁰² долей линейных расширений.Мы можем связать кумулятивные эффекты этих ошибок с помощью n ⁻¹⁰⁰ .