Complexidade de bits da consulta de intervalo de tempo O (1) em um

Considere o seguinte problema:

Deixei $k$ seja uma constante. Nos é dado um $k$ matriz -ary $A_{d_1\times\ldots\times d_k}$ do $0$ e $1$ 's. Deixei $N = \prod_{i=1}^k d_i$ .

Queremos criar uma estrutura de dados pré-processando $A$ para executar o seguinte tipo de operações de consulta:

Dadas as coordenadas de um $k$ caixa de ary $D$ , Tem alguma $1$ na caixa?
Dadas as coordenadas de um $k$ caixa de ary $D$ , retorne a posição de um $1$ na caixa (se houver).

As operações devem ser executadas em tempo constante $O(1)$ . A complexidade do tempo é medida em uma máquina de RAM. O tempo e o espaço de pré-processamento para a estrutura de dados não são importantes para nós.

A questão é quanto espaço (em complexidade de bits) precisamos armazenar uma estrutura de dados que permita as operações acima?

O limite inferior trivial é $N$ bits, já que o array pode ser reconstruído para essas consultas (portanto, a estrutura de dados deve ter pelo menos a mesma quantidade de informações).

O limite superior trivial é armazenar a resposta para todas as consultas. Isso precisaria de bits. No entanto, suspeitamos que isso possa ser feito com muito mais eficiência. $\prod_{i=1}^k {d_i \choose 2} = \Theta(N^2)$

Por exemplo, considere o caso especial em que . Nesse caso, podemos usar uma estrutura de dados RMQ sucinta para resolver o primeiro problema, e a estrutura de dados leva bits para armazenar. $k=1$ $2N+o(N)$

O que é uma estrutura de dados eficiente para esta tarefa?
Quão baixa a complexidade do espaço (o número de bits) pode suportar essas operações (ou apenas a primeira operação)?

Atualização (1/15): No caso especial , usar bits é suficiente (na verdade é melhor, , onde é o número está em ) reduzindo o problema para um problema anterior e usando a redução do problema anterior para o dicionário totalmente indexável (FID). Veja " Mais pressa, menos desperdício: diminuindo a redundância em dicionários totalmente indexáveis " de Grossi, Orlandi, Raman e Rao (2009). $k=1$ $N +o(N)$ $\log {N\choose t}+O(t)$ $t$ $1$ $A$

Atualização (27/6): Reduza novamente o problema para RMQ. Usamos um RMQ dimensional de Yuan e Atallah para obter um limite superior de à quantidade de espaço necessário quando é corrigido. $k$ $O(n\log n)$ $k$

reference-request data-structures space-complexity Chao Xu
fonte

A questão não é clara: é uma questão de estrutura de dados? Em caso afirmativo, quais são as outras operações nessa matriz kD? Se não houver outra operação, não haverá 1 nela. Se a questão é que recebemos uma matriz de kD e o que fazer com algum pré-processamento e a armazenamos de tal forma que usamos pouca quantidade de memória, mas podemos executar essa operação de verificação no pior caso , esclareça isso. Explique também qual é o modelo de computação se você deseja um limite inferior.

O (1)

$O(1)$

Kaveh

citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5421

Kaveh

IIUC, o artigo diz que a resposta para 1D é realmente bits e a idéia é armazenar todas as caixas pequenas e todas as caixas com comprimentos de potência 2 e outras caixas podem ser obtidas de len pow-2 boxes em constante time ( ) e parece-me que a mesma coisa funcionaria aqui e os bits serão suficientes.

O (n \lg n)

$O(n\lg n)$

O (2^{k})

$O(2^k)$

O (n^{k} \lg^{k} n)

$O(n^k\lg^k n)$

Kaveh

Obrigado, eu adicionei alguns esclarecimentos. O jornal não disse que sua principal contribuição é o uso de bits no pré-processamento e no armazenamento?

2 n + o (n)

$2n+o(n)$

Chao Xu

Desculpe, o que eu descrevi foi de trabalho anterior. No entanto, seu resultado parece ser conceitualmente semelhante, ou seja, eles dividem o array em blocos, pré-calculam a resposta sobre eles e usam um número constante deles para calcular a resposta para qualquer um deles. Se em kD o número de blocos base necessários para calcular a resposta a um bloco arbitrário for uma constante, então um algoritmo semelhante funcionaria aqui e daria provavelmente algo como (eu não t verifique se é esse o caso).

O (n^{k}) = O (N)

$O(n^k) = O(N)$

Kaveh

Complexidade de bits da consulta de intervalo de tempo O (1) em um

Respostas: