Время выполнения R-Select против Select в среднем случае?
В худшем случае R-выбор - O(n^2), где выбор - O(n). Может кто-то объяснить и противопоставить свое поведение в средних случаях.
Ps - я не уверен, что это повторяющийся вопрос. Я могу удалить, если это так! Спасибо!!
1 ответ
Под R-select я предполагаю, что вы говорите об алгоритме рандомизированного выбора, который работает, выбирая стержень, разделяя его и рекурсивно исходя из этого. Если это не так, дайте мне знать!
Вы правы, что наихудшим случаем алгоритма R-выбора является Θ (n2), но на практике это крайне маловероятно. Это требует от вас очень часто выбирать опору, которая находится в пределах постоянного числа элементов от минимального или максимального значения, и вероятность того, что это происходит, экспоненциально мала. Среднее время выполнения O(n) на самом деле вполне вероятно; Например, вы можете доказать, что для любой константы k вероятность того, что время выполнения равно O(n log n), составляет не менее 1 - 1 / nk.
Постоянный член, скрытый в нотации big-O R-select, на самом деле очень низкий, настолько низкий, что R-select обычно намного, намного быстрее, чем алгоритм выбора медианы медиан. На самом деле, они иногда объединяются. Алгоритм интроселекции работает, запуская R-select и просматривая среду выполнения, переключаясь на алгоритм выбора медианы медиан в случае, если среда выполнения в конечном итоге выглядит плохо. Тогда общее время выполнения будет наихудшим O(n) и сравнимо с R-select.