Рандомизированная быстрая сортировка, в которой после разделения снова выбирается пивот

Question

Я хотел бы придумать рецидив этой проблемы:

Рассмотрим вариант алгоритма рандомизированной быстрой сортировки, в котором стержень выбирается случайным образом, пока массив не будет разделен таким образом, чтобы как нижний подмассив L, так и больший подмассив G содержат 3/4 элементов массива. Например, если случайно выбранный стержень разделяет массив таким образом, что L содержит 1/10 элементов, тогда случайным образом выбирается другой стержень. Проанализируйте ожидаемое время выполнения этого алгоритма.

Сначала я рассмотрел этот вопрос так, как будто это обычный вопрос быстрой сортировки, и придумал такое повторение, где:

T(n) = T(3/4n) + T(n/4) + Θ(n) (where Θ(n) comes from the partition)

Это было бы целесообразно, если бы у нас был алгоритм, где разделение всегда составляет 1/4: 3/4. Но здесь мы используем случайный поворот, и поворот меняется каждый раз, когда условие разделения не выполняется. Я знаю, что наихудшее время выполнения для рандомизированной быстрой сортировки все еще равно O (n ^ 2), но я думаю, что в этих обстоятельствах худший случай сейчас отличается (что-то хуже, чем O (n ^ 2)). Я пока на правильном пути?

Answer 1

Временная сложность быстрой сортировки никогда не будет go выше O(n^2), если вы не выберете какую-либо логику c, для которой требуется O(n) время, чтобы выбрать ось.

Лучший способ выбора точки разворота - это случайный элемент, конец или первый элемент.

Answer 2

Есть n/2 плохих точек. Предполагая, что вы никогда не выбираете одну и ту же опорную точку дважды (в этом случае в худшем случае всегда выбирается неверная опорная точка, то есть бесконечное время), в худшем случае вы повторяете разбиение n/2 раз, что приводит к сложности Θ(n^2). этапа разбиения. Повторение становится

T(n) = T(n/4) + T(3n/4) + Θ(n^2)