Почему алгоритм медианы медианов описывается как использование вспомогательного пространства O (1)?

Однако в середине алгоритма мы делаем рекурсивный вызов в подмассиве размером n/5, чтобы найти медиану медианов. Когда это рекурсивный вызов возвращается, мы используем возвращаемую медиану медиан в качестве опоры для разделения массива.

Разве этот алгоритм не вставляет записи активации O(lg n) в стек времени выполнения как часть рекурсии? Из того, что я вижу, эти рекурсивные вызовы для поиска последовательных медианов медианов не могут быть оптимизированы с помощью хвоста, потому что мы делаем дополнительную работу после возвращения рекурсивных вызовов. Поэтому, похоже, для этого алгоритма требуется вспомогательное пространство O(lg n) (как и Quicksort, список Википедии которого требует использования вспомогательного пространства O(lg n) из-за пространства, используемого стеком времени выполнения).

Я что-то упустил, или статья в Википедии неверна?

(Примечание. Рекурсивный вызов, на который я имею в виду, - это return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) на странице Википедии.)

Ответы

Ответ 1

Хотя я не могу исключить, что O (1) возможно, эта информация Википедии представляется ошибкой.

Показанная там реализация принимает O (log n), а не только O (1).
Совершенно не очевидно, как реализовать его с помощью O (1), и нет объяснения/ссылки для него.
Я спросил автора, который изначально добавил эту информацию и ответил, что он не помнит и что это, вероятно, ошибка.
A документ за 2005 год, посвященный решению проблемы выбора с O (n) временем, и O (1) дополнительного пространства говорит BFPRT (также известный как Median медиан) использует Θ (log n) дополнительное пространство. С другой стороны, основным результатом статьи является то, что O (n) время и O (1) дополнительное пространство возможно, и один из двух алгоритмов, представленных в качестве доказательства, является некоторой "эмуляцией" BFPRT. Поэтому в этом смысле это возможно, но я думаю, что эмуляция скорее делает его другим алгоритмом, а O (1) не следует отнести к "регулярному" BFPRT. По крайней мере, не без объяснения причин.
(Спасибо Yu-HanLyu за то, что он показал эту статью и многое другое в комментариях)

Ответ 2

Это O (1).

Скажем, мы начинаем с массива длины n, и мы намереваемся найти k-й элемент отсортированного списка.

После того, как медиана первого вызова медианов выплюнет меньший массив, теперь нам нужно оценить i-й элемент этого меньшего массива. Обратите внимание, что i-ый элемент этого меньшего массива является результатом, поэтому мне не нужно передавать любую информацию в предыдущий вызов.

В быстрой сортировке мне нужно вернуть обратно отсортированные малые массивы в правильное положение и, таким образом, произойдет рекурсия. С медианой медиан, после цикла (хвостовая рекурсия), я останусь с ответом.

Глубина рекурсии = O (1)