В чем преимущество рандомизированной быстрой сортировки?

18

В своей книге Рандомизированных алгоритмы , Motwani и Raghavan открыть введение с описанием их функции RandQS - Рандомизированная - где быстрой сортировкой стержень, используемый для разделения множества на две части, выбирается случайным образом .

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

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

Может ли кто-нибудь просветить меня в довольно простых терминах?

Brent.Longborough
источник

Ответы:

19

Если входной массив распределен случайным образом равномерно, то (как вы заметили) нет никакой разницы между тем, чтобы всегда выбирать элемент в фиксированной позиции (например, средний, как вы предлагаете) или выбирать элемент, выбранный случайным образом.

О(NжурналN)

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

Jernej
источник
7
О(NжурналN)О(N2)
N!1N!
@ RobertS.Barnes Да
Jernej,
4

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

Юхо
источник