Troca de tempo e espaço por problema de elemento ausente

Aqui está um problema conhecido.

Dada uma matriz de números inteiros positivos, produz o menor número inteiro positivo que não está na matriz. $A[1\dots n]$

O problema pode ser resolvido no espaço e no tempo : leia a matriz, acompanhe no espaço se ocorreu, procure o menor elemento. $O(n)$ $O(n)$ $1,2,\dots,n+1$

Notei que você pode trocar espaço por tempo. Se você tiver apenas memória , poderá fazê-lo em rodadas e obter tempo . Em um caso especial, obviamente existe um algoritmo de tempo quadrático no espaço constante. $O(\frac{n}{k})$ $k$ $O(k n)$

Minha pergunta é:

Essa é a troca ideal, ou seja, ? Em geral, como alguém prova esse tipo de limites? $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$

Assuma o modelo de RAM, com acesso aritmético e aleatório limitado a matrizes em O (1).

Inspiração para este problema: troca de espaço-tempo para palíndromos no modelo de uma fita (veja, por exemplo, aqui ).

complexity-theory time-complexity space-complexity sdcvvc
fonte

Não, você pode classificar sua matriz em

O (n \log n)

$O(n \log n)$ e encontrar o número ausente (o primeiro número deve ser 1, o segundo deve ser 2, ... caso contrário, você o encontrará) em O (n), essa classificação pode ser feita com mergesort no local, significa

O (1)

$O(1)$ espaço extra; portanto, o tempo

\cdot

$\cdot$ espaço pertence a

O (n \log n)

$O(n \log n)$ . Não sei se entendi exatamente o seu problema (por isso não respondi, também não sei se há um limite melhor).

Presumo que a entrada seja somente leitura. (Caso contrário, o problema pode ser resolvido de maneira ideal no espaço

: multiplique a entrada por 2 e use a paridade para simular o algoritmo

)

O (n)

$O(n)$

O (1)

$O(1)$

O (n) / O (n)

$O(n)/O(n)$

sdcvvc

Qual é o algoritmo de espaço constante? Parece que você precisaria

espaço para o

versão que é "óbvio" para mim

\log n

$\log n$

n^{2}

$n^2$

Xodarap

Nesse modelo, números inteiros em tamanho de palavra recebem

; se for mais conveniente, você pode responder a qualquer variante da pergunta com

O (1)

$O(1)$

para alguma constante

time \cdot space = Ω (\frac{n^{2}}{\log^{k} n})

$\operatorname{time} \cdot \operatorname{space} = \Omega(\frac{n^2}{\log^k n})$

k

$k$

Sdcvvc

@sdcvvc, não consigo entender o seu algoritmo

, você o descreveria um pouco mais? (observe que a leitura em bits leva

O (n) / O (1)

$O(n)/O(1)$

O (\log n)

$O(\log n)$

Respostas:

Isso pode ser feito nas operações de palavras $O(n \log n)$ e $O(1)$ palavras de memória (respectivamente tempo $O(n \log^2 n)$ e memória $O(\log n)$ no modelo de RAM no nível de bit). De fato, a solução será baseada na seguinte observação.

Digamos existem $n_0$ mesmo e $n_1$ números ímpares na gama $[1, n + 1]$ (de modo $n_0 \approx n_1$ e $n_0 + n_1 = n + 1$ ). Então há $b \in \{0, 1\}$ tal forma que existem no máximo $n_b - 1$ valores com paridade $b$ na entrada. De fato, caso contrário, existem pelo menos $n_0$ pares e pelo menos $n_1$ valores ímpares na entrada, o que significa que há pelo menos $n_0 + n_1 = n + 1$ valores na entrada, contradição (existem apenas $n$ deles). Isso significa que podemos continuar pesquisando o número ausente apenas entre os números ímpares ou pares. O mesmo algoritmo também pode ser aplicado a bits mais altos de notação binária.

Portanto, nosso algoritmo ficará assim:

Suponha que já agora existam apenas valores de $x$ na entrada, com o restante do módulo $2^b$ igual a $r \in [0, 2^b)$ mas há pelo menos $x + 1$ números no intervalo $[1, n + 1]$ que possuem restante $r$ módulo $2^b$ (no início sabemos com certeza para $b = 0, r = 0$ ).
Digamos que existam valores $x_0$ na entrada com o restante do módulo $r$ $2^{b + 1}$ e valores $x_1$ na entrada com o restante $r + 2^b$ módulo $2^{b + 1}$ (podemos encontrar esses números em uma única passagem pela entrada). Claramente, $x_0 + x_1 = x$ . Além disso, como existem pelo menos $x + 1$ números na entrada com o restante $r$ módulo $2^b$ , pelo menos um dos pares $(r, b + 1), (r + 2^b, b + 1)$ satisfaz os requisitos da etapa $1$ .
Encontramos o número ausente quando $2^b \geqslant n + 1$ : existe apenas um número no intervalo $[1, n + 1]$ que pode ter o restante $r$ módulo $2^b$ ( $r$ si, se estiver no intervalo), então existem no mais zero valores na entrada que possuem esse restante. Então $r$ realmente está faltando.

Claramente, o algoritmo pára nas etapas $O(\log n)$ , cada uma delas precisa de tempo $O(n)$ (passagem única sobre a matriz de entrada). Além disso, são necessárias apenas $O(1)$ palavras de memória.

Kaban-5
fonte

Estou feliz em ver a pergunta respondida após esse tempo :)

sdcvvc

Se eu entendo suas definições, isso pode ser feito em tempo linear com espaço constante. Este é obviamente o limite mais baixo, porque precisamos pelo menos ler toda a entrada.

A resposta dada nesta pergunta é satisfatória.

É impossível executar isso com menos tempo ou espaço, e adicionar tempo ou espaço extra é inútil, portanto, não há troca de espaço-tempo aqui. (Observe que , para que o tradeoff que você observou não seja assintoticamente, em nenhum caso). $n=O(n/k)$

Em termos de sua pergunta geral, não conheço nenhum bom teorema de improviso que o ajude a provar trocas no espaço-tempo. Esta pergunta parece indicar que não há uma resposta fácil (conhecida). Basicamente:

Suponha que alguma linguagem seja decidida no tempo (usando uma certa quantidade de espaço) e no espaço (usando uma certa quantidade de tempo). Podemos encontrar tal que é decidível por , que é executado em tempo e espaço? $t$ $s$ $f,g$ $L$ $M$ $f(t,s)$ $g(t,s)$

é desconhecido, e uma resposta forte resolveria muitos problemas em aberto (principalmente sobre SC), o que implica que não existe uma solução fácil.

EDIT: Ok, com repetição (mas ainda estou assumindo que, com uma entrada de tamanho o número máximo possível é ). $n$ $n+1$

Observe que nosso algoritmo precisa ser capaz de diferenciar entre pelo menos respostas possíveis. Suponha que, a cada passagem dos dados, possamos obter no máximo partes de dados. Em seguida, precisaremos de passes para diferenciar todas as respostas. Supondo que então corremos em $n$ $k$ $n/k$ $k=n/s$ tempo. Então eu acho que isso prova o que você quer. $\frac{n}{n/s}n=sn$

A dificuldade está em mostrar que, a cada vez, obtemos apenas bits. Se você assumir que nossa única operação legal é =, então estamos bem. No entanto, se você permitir operações mais complexas, poderá obter mais informações. $k$

Xodarap
fonte

A pergunta que você vinculou assume que cada número aparece no máximo uma vez. Como não faço essa suposição, a solução não se aplica. Obrigado pelo segundo link.

Sdcvvc

@sdcvvc: Meu erro, eu assumi que você estava usando a versão que eu estou familiarizado. Não tenho uma resposta completa, mas é muito longo para um comentário - espero que minha edição seja útil.

Xodarap

Não comprei seu argumento depois de "EDIT". Mesmo que você possa coletar

bits em uma única passagem, isso é suficiente em princípio para distinguir

saídas possíveis. Portanto, esse argumento pode implicar apenas um limite inferior de

passes, não

k

$k$

2^{k}

$2^k$

n / 2^{k}

$n/2^k$

n / k

$n/k$

Jeffe