В худшем случае R-select является O (n^2), где в качестве выбора O (n). Может ли кто-то объяснить и сравнить их поведение в средних случаях.Runtime R-Select vs Выбрать в среднем случае?
P.s. - Я не уверен, что это повторяющийся вопрос. Я могу удалить, если это так! Благодаря!!
По R-select, я предполагаю, что вы говорите о рандомизированном алгоритме выбора, который работает, выбирая точку поворота, разбивая на эту точку и рекурсивно исходя из этого. Если это не так, дайте мне знать!
Вы правы, что худший случай алгоритма R-select равен Θ (n), но это вряд ли возникнет на практике. Это требует от вас очень часто выбирать опорную точку, находящуюся в пределах постоянного количества элементов, от минимального или максимального значения, и вероятность того, что это произойдет, экспоненциально низка. Среднее время выполнения O (n) на самом деле весьма вероятно; вы можете prove, например, что для любой константы k вероятность того, что время выполнения O (n log n) составляет не менее 1 - 1/n k.
Постоянный термин, спрятанный в обозначении R-select большой буквы O, на самом деле очень низок, настолько низкий, что R-select обычно намного, намного быстрее, чем алгоритм выбора медианы медианов. На самом деле их иногда объединяют вместе. Алгоритм introselect работает, выполняя R-select и просматривая время выполнения, переключаясь на алгоритм выбора медианы медианов в случае, если среда выполнения выглядит плохо. Общее время выполнения - это худший случай O (n) и сравнимый с R-select.
P.P.s .: Пожалуйста, дайте мне знать, если требуется дополнительная информация по вопросу! , Благодаря! – polyglot
Простите мое невежество, что такое «R-Select»? – Henry
IMHO, Если целью было найти i-й наименьший элемент в массиве (без изменения какого-либо порядка элементов), мы могли бы случайным образом выбрать опорный элемент для достижения этого. Это будет R-select. Надеюсь, это делает мой вопрос более понятным. благодаря! – polyglot