Существует хорошо известный в худшем случае алгоритм выбора , чтобы найти K «й наибольший элемент в массиве целых чисел. Он использует медиану из-медианы подойти , чтобы найти достаточно хороший стержень, разбивает входной массив на месте , а затем рекурсивно продолжается в его поисках к «го по величине элемента.
Что если бы нам не разрешили коснуться входного массива, сколько дополнительного пространства потребовалось бы, чтобы найти -й по величине элемент за O ( n ) времени? Можем ли мы найти k -й по величине элемент в O ( 1 ) дополнительном пространстве и при этом сохранить время выполнения O ( ? Например, нахождение максимального или минимального элемента занимает O ( п ) времени и O ( 1 ) пространство.
Интуитивно, я не могу представить, что мы могли бы сделать лучше, чем пространство, но есть ли доказательства этому?
Может ли кто-то указать на ссылку или выдвинуть аргумент, почему «й элемент требует пространство можно найти в O ( N ) времени?
Ответы:
Это открытая проблема, если вы можете сделать выбор с временем и O ( 1 ) дополнительными ячейками памяти без изменения входа (см. Здесь ). Но вы можете подойти довольно близко к этому.O(n) O(1)
Манро и Раман предложили алгоритм выбора, который выполняется за время при использовании только O ( 1 / ε ) дополнительного хранилища (ячеек). Этот алгоритм оставляет вход без изменений. Вы можете выбрать любой маленький εO(n1+ε) O(1/ε) ε>0
По своей сути алгоритм Манро и Рамана работает как классический алгоритм : он поддерживает левую и правую границу (называемую фильтром ), которые представляют собой два элемента с известным рангом. Запрашиваемый элемент содержится между двумя фильтрами (по рангу). Выбирая хороший элемент pO(n) p p
Кстати, алгоритмы, которые вы ищете, недавно были названы алгоритмами постоянного рабочего пространства .
Я не знаю какой-либо нижней границы.
источник