В своей книге Рандомизированных алгоритмы , Motwani и Raghavan открыть введение с описанием их функции RandQS - Рандомизированная - где быстрой сортировкой стержень, используемый для разделения множества на две части, выбирается случайным образом .
В течение некоторого времени я ломал свои мозги (по общему мнению, в недостаточной степени), но я не смог понять, какое преимущество имеет этот алгоритм по сравнению с простым выбором, скажем, среднего элемента (по индексу, а не по размеру) каждый раз.
Я полагаю, что я не вижу этого: если начальный набор находится в случайном порядке, в чем разница между выбором элемента в случайном месте в наборе и выбором элемента в фиксированной позиции?
Может ли кто-нибудь просветить меня в довольно простых терминах?
источник
Как отметил Джерней, предположение о том, что все перестановки входных данных одинаково вероятны, не всегда верно в действительности. Первой идеей может быть перестановка входного массива. Это сработало бы, но проще проанализировать ситуацию, когда стержень выбирается случайным образом. Это также известно как случайная выборка .
источник