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

Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space.Почему алгоритм медианы медианов описывается как использование вспомогательного пространства 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) на странице Википедии)

источник

2016-01-02 John Kurlak

Это просто пример того, как он используется в quickselect. Если вы внимательно прочитаете статью, вы обнаружите, что * только * сводная функция содержит фактический алгоритм медианных медианов. – Nuclearman

@Nuclearman Это справедливая точка, но функция 'pivot' делает вызов' select ', поэтому мы не можем сэкономить место, необходимое для 'select'.Статья в Википедии описывает две функции как * взаимно рекурсивные *. Если мы проигнорируем вызов 'select', мы не получим медиану медианов. Вместо этого мы получим медианные «n/5» из 5. –

После немного более продуманного, похоже, что у Википедии может быть не самая эффективная версия с пространственной эффективностью. Причина, по которой он не использует пространство для стека, заключается в том, что он не нужен, если вы конвертируете его из рекурсивного в итеративный. Взгляните на итеративные версии quickselect, и вы заметите, что нет стека, поскольку это можно сделать только с помощью циклов. Однако для быстрой сортировки нужен стек (неявно или явно). – Nuclearman

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

Реализация, показанная там, занимает O (log n), а не только O (1).
Совершенно очевидно, как реализовать его с помощью O (1), и для этого нет объяснений/ссылок.
Я спросил у автора, что originally added that information и he replied что он не помнит и что это, вероятно, ошибка.
A paper from 2005, посвященный решению проблемы выбора с временем O (n) и дополнительным пространством O (1), говорит, что BFPRT (ака медиана медиан) использует Θ (log n) дополнительное пространство. С другой стороны, основным результатом статьи является то, что O (n) время и O (1) дополнительное пространство возможно, и один из двух алгоритмов, представленных в качестве доказательства, является некоторой «эмуляцией» BFPRT. В этом смысле это возможно, но я думаю, что эмуляция скорее делает его другим алгоритмом, а O (1) не следует отнести к «регулярному» BFPRT. По крайней мере, не без объяснений.
(Благодаря Yu-HanLyu для показа, что бумага и многое другое в комментариях)

источник

2016-01-04 22:20:00

Большое спасибо за то, что нашли время для глубокого погружения в это! –

Последний пункт предполагает, что вход доступен только для чтения. Если вход модифицируется, медианное обнаружение может быть сделано на месте. –

@ Yu-HanLyu Вы уверены? Введение в документе гласит, что существует два типа алгоритмов с постоянным рабочим пространством, которым разрешено изменять входные данные. И в нем приводятся примеры использования в качестве дескриптора на месте и для быстрого сортирования. Тем не менее, я думаю, что мы действительно можем сделать алгоритм медианных медианов, используя только O (1) дополнительное пространство, если мы исключим некоторые из входных чисел, заменим их номерами с конца, а затем злоупотребляем этим концом для хранения рекурсивная информация. Это то, о чем вы думаете, или есть способ, по крайней мере, только переупорядочивать ввод без потери данных? –

-1

Это O (1).

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

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

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

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

источник

2017-02-18 20:42:31 kudalf

Поиск точки разбиения массива - это то, что занимает память O (lg n). Вы не можете разделить меньший массив до тех пор, пока вы не найдете pivot и 2) не разделите массив вокруг этого стержня. Вы правы, что как только вы разделили массив, вам не нужно передавать какую-либо информацию обратно исходному абоненту, но вы игнорируете тот факт, что обнаружение стержня принимает O (lg n) память. –

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

ответ

Смежные вопросы