Todo algoritmo de tempo linear é um algoritmo de streaming?

Sobre a esta pergunta sobre a contagem de inversão , eu encontrei um papel que prova um limite inferior da complexidade espaço para todos (exatas) streaming de algoritmos . Eu afirmei que esse limite se estende a todos os algoritmos de tempo linear. Isso é um pouco ousado, pois, em geral, um algoritmo de tempo linear pode pular à vontade (acesso aleatório) que um algoritmo de streaming não pode; tem que investigar os elementos em ordem. Eu posso executar várias passagens, mas apenas constantemente várias (para tempo de execução linear).

Portanto, minha pergunta:

Todo algoritmo de tempo linear pode ser expresso como um algoritmo de streaming com constantemente muitos passes?

O acesso aleatório parece impedir que uma construção (simples) seja uma resposta positiva, mas também não consegui encontrar um exemplo contrário.

Dependendo do modelo da máquina, o acesso aleatório pode até não ser um problema, em termos de tempo de execução. Eu estaria interessado em respostas para esses modelos:

• Máquina de Turing, entrada plana
• RAM, entrada como matriz
• RAM, entrada como lista vinculada

Para que os algoritmos de streaming sejam significativos, eles precisam trabalhar com uma quantidade significativamente menor de espaço de trabalho que a própria entrada. Por exemplo, se você permitir a mesma quantidade de espaço de trabalho que a entrada, poderá declarar trivialmente qualquer algoritmo como um "algoritmo de streaming de passagem única" que primeiro copie a entrada para o espaço de trabalho em uma única passagem e depois use apenas o trabalho espaço.

Eu acho que é típico restringir o espaço de trabalho a no máximo polilogarítmico no tamanho da entrada ao falar sobre algoritmos de streaming. Sob esse pressuposto, a seleção mediana não possui um algoritmo de transmissão O-1 pelo resultado de Munro e Paterson [MP80]: qualquer algoritmo de transmissão P- passagem para seleção mediana em N elementos precisa armazenar Ω ( N ^{1 / P} ) elementos. Por outro lado, a seleção mediana possui um conhecido algoritmo determinístico de tempo linear [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest e Robert E. Tarjan. Limites de tempo para a seleção. Journal of Computer and System Sciences , 7 (4): 448–461, agosto de 1973. DOI: 10.1016 / S0022-0000 (73) 80033-9

J. Ian Munro e Mike S. Paterson. Seleção e classificação com armazenamento limitado. Ciência da Computação Teórica , 12 (3): 315–323, novembro de 1980. DOI: 10.1016 / 0304-3975 (80) 90061-4

No modelo de streaming, você só pode armazenar dados extras constantes ou poliolarítmicos durante a varredura pela entrada. Se você considerar um algoritmo de tempo linear
que segue o paradigma de dividir e conquistar , precisará armazenar mais informações e / ou deverá verificar seus dados tantas vezes quanto a profundidade da recursão.

Um exemplo é o algoritmo DC3 para construir a matriz de sufixos de um texto (fornecido como matriz no modelo de RAM). Para construir uma matriz de sufixos, agrupe os caracteres em trigêmeos, para obter um texto com novos super caracteres . Você pode fazer isso com um deslocamento de 0 , 1 , 2 , o que resulta em três novos textos T 1 , T 2 , T 3 . Curiosamente, você pode calcular a matriz de sufixo, se você tem a matriz sufixo T 1 ⋅ T 2 no tempo linear. Portanto, o algoritmo precisa$T$$0,1,2$$T_1,T_2,T_3$$T_1\cdot T_2$

Tempo. Essa recursão resolve claramente para . Não vejo como isso pode ser transformado em um algoritmo de streaming.$t(n)=O(n)$

Outro exemplo bem conhecido é o algoritmo clássico de seleção de tempo linear .

$P$ . Nós definimos:

• $R(P)$$P$ pode ter. Eu acho que o modelo exato não importa tanto, mas vamos dizer que temos uma palavra RAM que recebe a entrada como uma matriz somente leitura de acesso aleatório.
• $S(P)$$P$ pode ter; aqui assumimos que o algoritmo (que é novamente modelado como uma máquina de RAM com palavras) prossegue em etapas de tempo: a cada etapa em que uma célula da matriz de entrada é fornecida, o algoritmo realiza algum processamento, registra algumas informações em seu armazenamento local e depois prossegue para a próxima etapa. A matriz é "repetida" um número constante de vezes dessa maneira.

$R(P)$$S(P)$ .

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

$O(1/\log^2 n)$$ps = \Omega(\sqrt{n})$$p$$s$$O(\log^2 n)$

Mesmo na definição mais simples de "algoritmo de streaming" (um algoritmo que, após cada iteração incremental na fonte, resulta no conhecimento imediato da próxima parte incremental do resultado), posso pensar em alguns algoritmos lineares que não se comportar dessa maneira. Os algoritmos de hash são grandes; O FNV-1a é linear ao número de bytes na fonte, mas não conhecemos nenhuma parte do hash final até que a fonte completa tenha sido processada.

RadixSort, também conhecido como BucketSort, é O (N) (tecnicamente O (NlogM), onde M é o valor máximo nos itens N, que é considerado pequeno), e deve ser executado em sua totalidade para garantir que qualquer item individual esteja em seu lugar final.

Para ser um algoritmo de "streaming", na sua forma mais simples, um algoritmo deve ter as duas propriedades a seguir, nenhuma das quais é expressamente limitada pelo tempo:

• Melhor que a complexidade do espaço O (N) (declarado de forma equivalente, a fonte inteira não precisa ser conhecida e o resultado inteiro não precisa ser armazenado)
• Relação de E / S O (N) (o algoritmo produz um número de saídas linearmente proporcionais às suas entradas)

Portanto, a principal classe de algoritmos que transmitem é a de algoritmos que executam "projeções" (transformações incrementais de uma entrada em saídas X> 0).