Почему рандомизированная быстрая сортировка лучше стандартной быстрой сортировки?

Question

По словам самого Кормена: «Разница в том, что с детерминированным алгоритмом конкретный входной сигнал может вызвать это наихудшее поведение. Однако с рандомизированным алгоритмом никакой вход не всегда может вызвать наихудшее поведение».

Как добавление рандомизированной опорной точки что-либо меняет, алгоритм по-прежнему будет плохо работать при определенных входных данных, и, учитывая, что каждый тип входных данных с равной вероятностью, это не лучше, чем у стандартной быстрой сортировки, с той лишь разницей, что мы на самом деле не знаем, какой именно ввод вызовет наихудшую временную сложность. Так почему же рандомизированная версия считается лучшей?

Answer 1

Рассмотрим следующую версию быстрой сортировки , в которой мы всегда выбираем последний элемент в качестве точки поворота . Теперь рассмотрим следующий массив:

      int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};

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

      arr = [1, 8, 7, 6, 5, 4, 3, 2, 9];

Теперь он будет рекурсивно обрабатывать подмассивы:

      s1 = [1, 8, 7, 6, 5, 4, 3, 2];
s2 = [9];

В s1он снова выберет 2 в качестве своей оси, и только 8 и 2 поменяются местами. Таким образом, если мы попытаемся сформулировать рекуррентное соотношение, из-за его сложности оно будет

      T(n) = T(n-1) + O(n)

что соответствует O (n^2).

Итак, для этого массива стандартная версия всегда будет занимать время O (n^2).

В рандомизированной версии мы сначала обмениваем последний элемент с некоторым случайным элементом в массиве, а затем выбираем его в качестве опорного. Итак, для данного массива эта опорная точка будет разбивать массив случайным образом, скорее всего, посередине. Итак, теперь повторение будет

      T(n) = 2T(n/2) + O(n)

который будет O (n * Log(n)).

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

Answer 2

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

Следует уточнить, что это действительно рандомизированный алгоритм. Если вместо этого используется детерминированный псевдослучайный алгоритм, то преднамеренно созданные входные данные могут вызвать наихудшее поведение.

Однако при использовании рандомизированного алгоритма никакие входные данные не всегда могут вызвать наихудшее поведение.

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

---

В большинстве библиотечных реализаций быстрой сортировки с одной точкой поворота используется медиана 3 или медиана 9, поскольку они не могут полагаться на наличие быстрых инструкций для случайных чисел, таких как X86 RRAND и быстрое деление (для функции по модулю). Если бы быстрая сортировка каким-то образом была частью схемы шифрования, то во избежание атак, основанных на времени, можно было бы использовать действительно рандомизированный алгоритм.