Является ли каждый алгоритм линейного времени алгоритмом потоковой передачи?

В этом вопросе о подсчете инверсий я нашел статью, в которой доказывается нижняя оценка сложности пространства для всех (точных) потоковых алгоритмов . Я утверждал, что эта граница распространяется на все линейные алгоритмы времени. Это немного жирным шрифтом, так как в целом, алгоритм линейного времени может перемещаться по желанию (произвольный доступ), что алгоритм потоковой передачи не может; он должен исследовать элементы по порядку. Я могу выполнить несколько проходов, но только постоянно много (для линейного времени выполнения).

Поэтому мой вопрос:

Может ли каждый алгоритм линейного времени быть выражен как алгоритм потоковой передачи с постоянно большим количеством проходов?

Случайный доступ, кажется, препятствует (простой) конструкции, доказывающей положительный ответ, но я также не смог придумать контрпример.

В зависимости от модели машины, произвольный доступ может даже не быть проблемой с точки зрения времени выполнения. Мне были бы интересны ответы на эти модели:

• Машина Тьюринга, плоский ввод
• RAM, ввод в виде массива
• RAM, вход в виде связанного списка

Чтобы потоковые алгоритмы имели смысл, они должны работать со значительно меньшим объемом рабочего пространства, чем сам ввод. Например, если вы разрешите тот же объем рабочего пространства, что и для ввода, вы можете тривиально сформулировать любой алгоритм как «алгоритм потоковой передачи за один проход», который сначала копирует входные данные в рабочее пространство за один проход, а затем использует только работу. Космос.

Я думаю, что типично ограничивать рабочее пространство до максимально полилогарифмического размера ввода, когда речь идет об потоковых алгоритмах. При этом допущении медианный отбор не имеет алгоритма потоковой передачи O (1) в результате Манро и Патерсона [MP80]: любой алгоритм потоковой передачи P- прохода для медианного выбора на N элементах должен хранить Ω ( N ^{1 / P)} ) элементы. С другой стороны, медианный отбор имеет хорошо известный детерминистический алгоритм линейного времени [BFPRT73].

[BFPRT73] Мануэль Блюм, Роберт У. Флойд, Вон Пратт, Рональд Л. Ривест и Роберт Э. Тарьян. Границы времени для выбора. Журнал компьютерных и системных наук , 7 (4): 448–461, август 1973. DOI: 10.1016 / S0022-0000 (73) 80033-9

[MP80] Дж. Ян Мунро и Майк С. Патерсон. Выбор и сортировка с ограниченным хранением. Теоретическая информатика , 12 (3): 315–323, ноябрь 1980 г. DOI: 10.1016 / 0304-3975 (80) 90061-4

В потоковой модели вам разрешено хранить только постоянные или полулогарифмические дополнительные данные при сканировании через входные данные. Если вы рассматриваете алгоритм линейного времени,
который следует парадигме « разделяй и властвуй» , вам нужно хранить больше информации и / или вы должны сканировать свои данные столько раз, сколько глубина рекурсии.

Одним из примеров является алгоритм DC3 для построения суффиксного массива текста (заданного как массив в модели RAM). Чтобы создать массив суффиксов, вы группируете символы в триплеты, поэтому вы получаете текст с новыми суперсимволами . Вы можете сделать это со смещением 0 , 1 , 2 , что приводит к трем новым текстам T 1 , T 2$T$$0,1,2$ . Интересно, что вы можете вычислить массив суффиксов, если у вас есть массив суффиксов T 1 ⋅ T 2 за линейное время. Следовательно, алгоритм нуждается$T_1,T_2,T_3$$T_1\cdot T_2$

время. Эта рекурсия решает четко$t(n)=O(n)$ . Я не понимаю, как это можно превратить в алгоритм потоковой передачи.

Другой хорошо известный пример - классический алгоритм выбора линейного времени .

Я интерпретирую ваш вопрос следующим образом. Давайте исправим некоторые вычислительные проблемы$P$

• $R(P)$$P$
• $S(P)$$P$

$R(P)$$S(P)$ может быть .

$n$$[1, n-1]$$O(\log n)$$O(1)$$\omega(\log n)$

$O(1/\log^2 n)$, Затем Chakrabarti et al. показать, что если мы ограничим все проходы в одном направлении, мы имеем$ps = \Omega(\sqrt{n})$, где $p$ это количество проходов и $s$это космическая сложность. С другой стороны, Magniez et al. дать простой алгоритм, который использует$O(\log^2 n)$ пространство, имеет полиномиально малую вероятность ложного срабатывания, и делает один проход вперед и один назад.

Даже в простейшем определении «алгоритма потоковой передачи» (алгоритм, который после каждой инкрементальной итерации источника приводит к немедленному знанию следующей инкрементальной части результата), я могу представить несколько линейных алгоритмов, которые не вести себя так. Алгоритмы хеширования являются большими; FNV-1a является линейным по отношению к количеству байтов в источнике, но мы не знаем какой-либо части окончательного хэша, пока не будет обработан полный источник.

RadixSort, иначе BucketSort - это O (N) (технически O (NlogM), где M - максимальное значение в N элементах, которое считается небольшим), и должно выполняться полностью, чтобы гарантировать, что любой отдельный элемент находится на своем последнем месте.

Чтобы быть «потоковым» алгоритмом, в самом простом случае алгоритм должен иметь следующие два свойства, ни одно из которых явно не ограничено по времени:

• Лучше, чем O (N) сложность пространства (указано эквивалентно, весь источник не должен быть известен, и весь результат не должен быть сохранен)
• Отношение O (N) I / O (алгоритм выдает количество выходов, линейно пропорциональных его входам)

Таким образом, основной класс алгоритмов этого потока - это алгоритмы, которые выполняют «проекции» (инкрементные преобразования одного входа в X> 0 выходов).