Нахождение k-го наименьшего элемента из заданной последовательности только с O (k) памятью O (n) времени

11

Предположим , что мы читаем последовательность чисел, один за другим. Как найти к «й наименьший элемент только с помощью O ( K ) клеток памяти и в линейном времени ( O ( п ) ). Я думаю , что мы должны сохранить первые K члены последовательности и когда получим K + 1 «й член, удалить термин , который мы уверены , что она не может стать к » й наименьший элемент , а затем сохранить к + 1 «й член. Таким образом, у нас должен быть индикатор, который показывает этот непригодный термин на каждом шаге, и этот индикатор должен быстро обновляться на каждом шаге. Я начал с «Макс»nkO(k)O(n)kk+1kk+1; но он не может обновить быстро; Значит , что если мы будем рассматривать не более , то в первом делеции мы пропускаем макс , и мы должны искать максимум в и его причины ( п - к ) × O ( к ) время , что это не линейная. Может быть , мы должны сохранить первые K член последовательности более разумно.O(k)(nk)×O(k)k

Как мне решить эту проблему?

Shahab_HK
источник
1
Вы заинтересованы в сетевом алгоритме, или любой алгоритм подойдет?
Юваль Филмус
Если то вы можете сделать это, используя алгоритм статистики заказов. Если k = o ( n ), то вы можете сделать это O ( k ) памяти и O ( n log k ) времени, используя любые сбалансированные по высоте деревья. k=θ(n)k=o(n)O(k)O(nlogk)
Shreesh
Это называется проблемой отбора en.wikipedia.org/wiki/Selection_algorithm
xavierm02
Существуют линейные алгоритмы на месте, которые вы можете погуглить, но они несколько сложны.
Юваль
@ xavierm02 это не проблема выбора. Потому что есть ограничение памяти.
Shahab_HK

Ответы:

16

Создайте буфер размером . Прочитать в 2 k элементов из массива. Используйте алгоритм выбора линейного времени, чтобы разделить буфер так, чтобы k наименьших элементов были первыми; это занимает O ( K ) время. Теперь прочитайте еще k элементов из вашего массива в буфер, заменив k самых больших элементов в буфере, разделите буфер, как и раньше, и повторите.2k2kkO(k)kk

Для этого требуется времени и O ( k ) пространства.O(kn/k)=O(n)O(k)

jbapple
источник
+1, это соответствует заданной асимптотике. При этом я не верю, что это быстрее, чем делать один алгоритм линейного выбора времени ... за исключением случаев, когда - маленькая константа, тогда это дает интересную перспективу. Например, для k = 1 этот алгоритм производит функцию. kk=1min
orlp
1
Иногда алгоритм выбора линейного времени занимает слишком много места. Например, он не подходит для использования в контексте потоковой передачи или когда входной массив является неизменным.
17
Это действительные баллы.
orlp
3

O(k)O(nlogk)kO(k)O(logk)O(k+nlogk)O(nlogk)

O(logn)O(n)kk

O(logn)O(k)O(logn)264log264=64kn

orlp
источник
O(n×logmin(k,nk))
@ xavierm02 = . Доказательство: худший случай для равен . Худший случай для - . Они одинаковы в пределах постоянного множителя, поэтому = . O(min(k,nk))O(k)knmin(k,nk)n2O(min(k,nk))O(k)
orlp
@ xavierm02 Тем не менее, это все еще хорошее ускорение :)
orlp
un,k=k - это но это не . Предположим, что это так. Тогда есть некоторые и некоторые так что для каждого мы имеем , что явно неверно (потому что мы можем взять Итак, . O(k)O(min(k,nk))CMMknkC(nk)n=k+).O(min(k,nk))O(k)
xavierm02
@ xavierm02 Я незнаком с твоей нотацией . Честно говоря, я вообще незнаком с многомерными обозначениями Big , особенно учитывая, что измерения не связаны между собой. un,kOn,k
orlp