Связанный на пространстве для алгоритма отбора?

Question

Есть известный худший случай $ O (n) $ Алгоритм отбора Чтобы найти самый большой элемент $ K $ 'в множестве целых чисел. Он использует медиана-медианы Подход, чтобы найти достаточно хорошего поворота, разделяет массив ввода на месте, а затем рекурсивно продолжается в поиске крупнейшего элемента $ K $ '.

Что если бы нам не позволили прикоснуться к массиву ввода, сколько дополнительного места потребуется, чтобы найти самый большой элемент $ K $ 'в $ O (n) $ времени? Можем ли мы найти самый большой элемент $ K $ 'в дополнительном пространстве $ O (1) $ и при этом сохранить время выполнения $ O (n) $? Например, поиск максимального или минимального элемента занимает $ O (N) $ Time и $ O (1) $ Space.

Интуитивно, я не могу представить, что мы можем сделать лучше, чем пространство $ O (n) $, но есть ли доказательство этого?

Может ли кто -нибудь указать на ссылку или придумать аргумент, почему элемент $ lfloor N/2 rfloor $ 'th потребует пространства $ O (n) $, которое можно было бы найти в $ O (n) $ времени?

Answer 1

Это открытая проблема, если вы можете сделать выбор с $ O (n) $ Time и $ O (1) $ дополнительные ячейки памяти без изменения ввода (см. здесь) Но вы можете приблизиться к этому.

Мунро и Раман предложили Алгоритм для отбора Это работает во время $ o (n^{1+ varepsilon}) $, используя только $ o (1/ varepsilon) $ дополнительное хранилище (ячейки). Этот алгоритм оставляет вход без изменений. Вы можете выбрать любой маленький $ vorepsilon> 0 $.

По своей сути алгоритм Мунро и Рамана работает как классический алгоритм $ O (n) $: он поддерживает оставил а также Правильно связан (называется фильтр), которые представляют собой два элемента с известным рангом. Запрашиваемый элемент содержится между двумя фильтрами (по рангу). Выбирая хороший элемент поворота $ p $, мы можем проверить все номера на фильтрах и $ p $. Это позволяет обновлять фильтры и уменьшить количество оставшихся элементов для проверки (по рангу). Мы повторяем, пока не найдем элемент запроса.

Что отличается от классического алгоритма, так это выбор $ p $. Пусть $ a (k) $ будет алгоритмом, который решает выбор для $ varepsilon = 1/k $. Алгоритм $ a (k) $ разделяет массив в блоках одинакового размера и идентифицирует блок, в котором есть много элементов, чьи ранги находятся между фильтрами (существование по принципу голубей). Затем этот блок будет отсканирован на наличие хорошего поворотного элемента с помощью алгоритма $ a (k-1) $. Рекурсионное якорь - это тривиальный алгоритм $ a (1) $. Правильный размер блока (и выполнение математики) дает вам требования времени и пространства, как указано выше.

Кстати, алгоритмы, которые вы ищете, были недавно названы Алгоритмы постоянного пространства.

Я не знаю ни о какой нижней границе.