Что такое «противник убийцы для быстрого сортировки»?

Question

Я прочитал быстрый вид. Мы используем элемент поворота независимо от другого набора данных в массиве. Насколько я знаю; этот противник-убийца рассказывает ввод, который приводит к квадратичной временной сложности (практически). Но как?

Редактировать: Следующие строки из published paper на Убийца для быстрого сортировки не понимали.

"Первоначально противник делает все элементы gas.When сравниваются два элемента газа, один„замораживаются“в определенного„твердое“значение, больше, чем любая уже твердая стоимость. Затем операнды сравниваются заново. Когда твердый элемент сравнивается с элементом газа, он сравнивает low.when сравниваются два твердых предметов, то ответ зависит от замороженных значений. «

Link to adversary killer for quick sort

Answer 1

Придумайте„газа“и» твердое "в качестве меток, которые противник применяет к элементам массива, чтобы пережить которые элементы уже видели в quicksort. Противник работает следующим образом:

• противник дает массив предметов с надписью «газ» и значениями положительной бесконечности для быстрой сортировки;
• quicksort выбирает, какие предметы он хочет сравнить;
• Противник может вмешаться, сменить метку «газ» на «твердую» метку, дать элементу конечное целочисленное значение, а затем разрешить работу быстрой сортировки.

Процедура разработана таким образом, что объект может быть заморожен только в том случае, если quicksort еще не сдвинул его. Таким образом, если мы возьмем предметы после того, как все они прочны, упорядочьте их в первоначальном порядке и дайте им быстро сортировать без противника, quicksort будет использовать точно такую ​​же последовательность сравнений, как и в случае присутствия противника.

Answer 2

Бумага предполагает необычные возможности на стороне противника: противник имеет контроль над функцией сравнения, вызванной quicksort. Другими словами, противник может не только создать вредоносный массив данных в начале, он может адаптировать его поведение во время прогона quicksort.

С учетом этой силы противник может эффективно построить входной массив «на лету» (как это видно из quicksort), где каждый стержень выбирается так, чтобы иметь значение выше, чем все ранее обнаруженные элементы. Таким образом, выбираются n пивоты, и каждый из них сравнивается с элементами O(n), что дает время выполнения O(n^2).

Возможность «на лету» позволяет также разбить рандомизированные версии quicksort. Однако, если вы не предоставляете онлайн-службу сортировки, где злоумышленник предоставляет как вход, так и метод сравнения, вам не нужно беспокоиться об этой атаке.