Algoritmo de tempo linear para encontrar o deslocamento máximo

Suponha que recebamos uma matriz $A[1..n]$ contendo números inteiros não negativos (não necessariamente distintos).

Deixe $B$ ser $A$ ordenado na ordem não crescente. Queremos calcular

m = max_{i \in [n]} B [i] + i .

$m = \max_{i\in [n]} B[i]+i.$

A solução óbvia é classificar $A$ e depois calcular $m$ . Isso fornece um algoritmo que é executado no tempo $O(n \lg n)$ no pior dos casos.

É possível fazer melhor? Podemos calcular $m$ em tempo linear?

Minha principal pergunta é a acima. Mas seria interessante saber sobre a seguinte generalização do problema.

Deixe $B$ ser $A$ classificados de acordo com alguma comparação do Oracle $\leq$ e $f$ uma função dada por um Oracle. Dada $A$ e oráculos para $\leq$ e $f$ , o que podemos dizer sobre o tempo necessário para calcular $m = \max_{i \in [n]} f(B[i],i)$ ?

Ainda podemos calcular $m$ no tempo $O(n \lg n)$ . Mas podemos provar um limite inferior super-linear para este caso generalizado?

Se a resposta for sim, o limite inferior se mantém se assumirmos que é a ordem usual em números inteiros é uma função "agradável" (monótona, polinomial, linear etc.)? $\leq$ $f$

cc.complexity-theory ds.algorithms optimization sorting Kaveh
fonte

Respostas:

Podemos calcular em tempo linear. $m$

Para simplificar, suponha que as matrizes sejam baseadas em 0: , . Queremos calcular . $A[0..n-1]$ $B[0..n-1]$ $m = \max_i B[i]+i$

Seja . Obviamente . $max = \max_i A[i]$ $max \leq m$

Deixe ser , após separação. Se , temos $A[j]$ $B[k]$ $A[j] \leq max - n$

B [k] + k \leq B [k] + (n - 1) = A [j] + (n - 1) \leq (m a x - n) + (n - 1) = m a x - 1 < m a x \leq m .

$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$

Portanto, podemos ignorar quando . Só precisamos considerar os números no intervalo . $A[j]$ $A[j] \leq max - n$ $[max-n, max]$

Podemos usar a classificação de contagem para classificar os números em que estão no intervalo no tempo linear e usar a lista classificada para calcular . $A$ $[max-n, max]$ $m$

Marzio De Biasi
fonte

... mmm ... mas qual é o custo de C [x] = C [x] +1?!?

Marzio De Biasi

há algum problema com sua resposta? porque parece bom para mim: você está dizendo que só nos importamos com elementos de matriz com valores em , para que possamos usar a classificação de contagem. Isso funciona para o problema geral sempre que para todos .

[M - n, M]

$[M-n, M]$

| f (B [i], i) - B [i] | = O (n)

$|f(B[i], i) - B[i]| = O(n)$

i

$i$

Sasho Nikolov

Obrigado @Marzio. :) Editei levemente sua resposta para maior clareza. Sinta-se à vontade para reverter minha edição ou editar mais.

Kaveh 10/10

Essa solução parece funcionar também para qualquer onde, para todos e , .

f (x, i)

$f(x,i)$

x

$x$

i \leq n

$i\leq n$

| f (x, i) - x | = O (n)

$|f(x,i)-x| = O(n)$

Kaveh 10/10

@ Kaveh: editar está ok! Eu escrevi a resposta rapidamente e eu não tinha certeza de seu correcteness: -S

Marzio De Biasi

-1

Se a matriz consistir em números inteiros distintos, então , já que a distância entre as entradas adjacentes em é pelo menos ; a situação é mais interessante quando eles não precisam ser distintos. $A$ $m = \max(A) + 1$ $B$ $1$

Para sua pergunta mais geral, imagine uma situação em que seja apenas "interessante" quando . Parece possível construir um argumento adversário que obriga a consultar para todos os antes que você possa conhecer , portanto, você precisa classificar para encontre a resposta, que faz comparações . (Existem algumas complicações, pois pode ser o caso de podermos testar se em tempo constante, e não linear, consultando .) Esse é o caso, mesmo que é um polinômio (de alto grau). $f(B[i],j)$ $i = j$ $f(B[i],i)$ $i$ $\max_i f(B[i],i)$ $A$ $\Omega(n\log n)$ $A[i] = B[j]$ $f(A[i],j)$ $f$

Yuval Filmus
fonte

E se A tiver n - 1 zeros e um único? Então a resposta é n, não 1.

Grigory Yaroslavtsev

Oi Yuval. Não pode ser repetido em números . Como Grigory disse, a solução não parece funcionar.

A

$A$

Kaveh 9/10

Eu acho que vejo sua idéia para o argumento do limite inferior: dado , podemos calcular rapidamente usando os pares de consulta feitos por um algoritmo que resolve o problema no tempo . Podemos garantir que o algoritmo consulte em todos mas não podemos garantir que ele não consulte outros pares. No entanto, podemos definir para outros pares como um valor distinguível, para que possamos descartar esses pares.

A

$A$

B

$B$

f

$f$

o (n \lg n)

$o(n\lg n)$

f

$f$

(B [i], i)

$(B[i],i)$

f

$f$

Kaveh