Есть ли какое-либо значение выбора случайного поворота над последним элементом для быстрого выбора?Выбор элементов поворота в Quick Select
Я все еще могу найти нужный элемент, всегда выбирая последний элемент в качестве поворота. Будет ли это влиять на время выполнения.
Выбор стержня оказывает огромное влияние на время выполнения quickselect на заданном массиве.
В детерминированном quickselect, если вы всегда выбираете последний элемент в качестве своего стержня, представьте, что произойдет, если вы попытаетесь выбрать из всегда отсортированного списка. Ваш стержень всегда будет самым худшим возможным стержнем и только исключит одно число из массива, что приведет к Θ (n).
В рандомизированном Быстрый выбор, это все еще технически возможно, что во время выполнения будет Θ (п), если алгоритм всегда делает наихудший возможный выбор на каждом рекурсивном вызове, но это чрезвычайно маловероятно. Время выполнения будет O (n) с высокой вероятностью, и нет ввода «killer».
Других слов, Быстрый выбор с детерминированно-выбранной осью будет всегда иметь по крайней мере один вход «киллер», что заставляет его работать во время Θ (п), в то время как Быстрый выбор со случайным поворотом не имеют киллеров входов и имеет отличные средние гарантии времени. В результате анализы совершенно разные.
Надеюсь, это поможет!
Если ваш вход уже отсортирован, выбор последнего (или первого) элемента в качестве поворота будет плохим. См. Https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot – Jasper