Алгоритм выбора медианы - находит ли он абсолютную медиану или «медиану медиан», близкую к абсолютной медиане?

Question

Раздел 9.3 в CLRS 3-е издание «Выбор в наихудшем линейном времени» рассказывает об алгоритме «Выбор» (иногда называемом алгоритмом BFPRT из-за Блума, Флойда, Пратта, Ривеста и Тарьяна) для нахождения медианы список в O (N) время в худшем случае. Я немного запутался, пытаясь запустить образец на доске. Я понимаю, что определенное количество элементов может быть исключено при каждом вызове «Выбрать» (я прочитал, что исключено 30% против 70%, которые необходимо проверить еще раз), меня смутило то, какая часть массива может быть исключен, т. е. если массив визуализируется как матрица с высотой 5 и шириной n / 5, то в каком квадранте (ах) располагаются исключенные элементы? Сначала я думал, что это два диагонально смежных квадранта, но теперь я думаю, что это только один квадрант в зависимости от медианы медиан (см. Шаги 5, 6 и 7 здесь ).

Так что я пошел в Википедию, чтобы посмотреть, было ли быстрое объяснение с меньшим количеством анализа, чем в CLRS (для понимания алгоритма, прежде чем я вернулся к CLRS для анализа). Я пришел к этому , в частности: «Наконец,« медиана медиан »выбрана как стержень». Судя по описанию в википедии, «Выбрать» не находит истинную медиану, а элемент, который достаточно медиан для цели выбора точки быстрой сортировки.

Так что же делает «Выбор» в терминах истинной медианы и как он это делает? Фраза, которая приходит на ум через все это, является «частичной иерархией», которая, как я понимаю, является причиной, по которой работает «Выбор», но по какой логике вы можете исключить элементы из списка из медианы, основанной на этой частичной иерархии?

Answer 1

Он находит абсолютную медиану.

Как вы сказали, "Выбор" не находит истинную медиану, скорее, элемент, который достаточно медиан для цели выбора точки для быстрой сортировки. В частности, он достаточно медиан, чтобы на каждой итерации гарантированно выпадало не менее 30% набора данных.К сожалению, это также дорогостоящая операция.

Основная идея заключается в том, что медиана медиан меньше или равна 3 из каждых 5 элементов, медиана которых меньше или равна ей.Таким образом, он меньше или равен 3 из каждых 5 элементов для половины групп из 5, так что по крайней мере 30% набора меньше или равно ему.Таким образом, он находится в наибольших 70% набора данных.

Аналогично, он находится в наименьших 70% набора данных.

Это гарантирует, что вы избежите потенциальной ловушки быстрого выбора, которыйвыбирает опорные точки с экстремальными значениями.

Если вы хотите объединить эффективность и худший случай, вы можете комбинировать это с быстрым выбором.Например, 4 раунда быстрого выбора, за которым следует один раунд, за которым следуют 4 раунда быстрого выбора и т. Д. Дорогие раунды BFPRT гарантируют O(n), тогда как быстрый выбор в среднем будет быстрым.Откладывая ваш первый раунд BFPRT до нескольких раундов быстрого выбора, вы можете сделать дополнительное время бега всего на несколько процентов больше, чем в среднем быстрый выбор.(Стоимость наихудшего случая возрастает совсем немного, но мы не ожидаем, что столкнемся с этим.)