Ограничено пространство для выбора алгоритма?

11

Существует хорошо известный в худшем случае алгоритм выбора , чтобы найти K «й наибольший элемент в массиве целых чисел. Он использует медиану из-медианы подойти , чтобы найти достаточно хороший стержень, разбивает входной массив на месте , а затем рекурсивно продолжается в его поисках к «го по величине элемента.O(n) kk

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

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

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

user834
источник
2
Я не эксперт, но, возможно, эти статьи полезны: основанные на сравнении нижние границы пространства-времени
Vor

Ответы:

13

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

Манро и Раман предложили алгоритм выбора, который выполняется за время при использовании только O ( 1 / ε ) дополнительного хранилища (ячеек). Этот алгоритм оставляет вход без изменений. Вы можете выбрать любой маленький εO(n1+ε)O(1/ε)ε>0

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

pA(k)ε=1/kA(k)A(k1)A(1)алгоритм. Размер правый блок (и делать математику) дает вам время работы и требования к пространству, как указано выше.

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

Я не знаю какой-либо нижней границы.

A.Schulz
источник