Algorithme de temps linéaire pour trouver le max décalé

Supposons que l'on nous donne un tableau contenant des entiers non négatifs (pas nécessairement distincts). $A[1..n]$

Soit un trié dans l'ordre non croissant. Nous voulons calculer $B$ $A$

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

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

La solution évidente consiste à trier $A$ puis à calculer $m$ . Cela donne un algorithme qui s'exécute dans le temps $O(n \lg n)$ dans le pire des cas.

Est-il possible de faire mieux? Peut-on calculer $m$ en temps linéaire?

Ma principale question est celle ci-dessus. Mais il serait intéressant de connaître la généralisation suivante du problème.

Soit $B$ un $A$ trié selon une comparaison oracle $\leq$ et $f$ une fonction donnée par un oracle. Étant donné $A$ et les oracles pour $\leq$ et $f$ , que pouvons-nous dire du temps nécessaire pour calculer $m = \max_{i \in [n]} f(B[i],i)$ ?

On peut encore calculer $m$ en temps $O(n \lg n)$ . Mais peut-on prouver une borne inférieure super-linéaire pour ce cas généralisé?

Si la réponse est oui, la borne inférieure est-elle valable si nous supposons que est l'ordre habituel sur les entiers et est une fonction "agréable" (monotone, polynomiale, linéaire, etc.)? $\leq$ $f$

cc.complexity-theory ds.algorithms optimization sorting Kaveh
la source

Réponses:

Nous pouvons calculer en temps linéaire. $m$

Pour simplifier, supposons que les tableaux soient basés sur 0: , . Nous voulons calculer . $A[0..n-1]$ $B[0..n-1]$ $m = \max_i B[i]+i$

Soit . Évidemment . $max = \max_i A[i]$ $max \leq m$

Soit soit après le tri. Si nous avons $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.$

On peut donc ignorer quand . Il suffit de considérer les nombres dans la plage . $A[j]$ $A[j] \leq max - n$ $[max-n, max]$

Nous pouvons utiliser le tri par comptage pour trier les nombres dans qui sont dans la plage en temps linéaire et utiliser la liste triée pour calculer . $A$ $[max-n, max]$ $m$

Marzio De Biasi
la source

... mmm ... mais quel est le coût de C [x] = C [x] +1?!?

Marzio De Biasi

y a-t-il un problème avec votre réponse? car cela me semble bien: vous dites que nous ne nous soucions que des éléments de tableau avec des valeurs dans , donc nous pouvons utiliser le tri par comptage. Cela fonctionne pour le problème général lorsque pour tout .

[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

Merci @Marzio. :) J'ai légèrement modifié votre réponse pour plus de clarté. N'hésitez pas à annuler ma modification ou à modifier davantage.

Kaveh

Cette solution semble fonctionner aussi pour tout où pour tout et , .

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

@Kaveh: l'édition est ok! J'ai écrit la réponse rapidement et je n'étais même pas sûr de son exactitude: -S

Marzio De Biasi

-1

Si le tableau est composé d'entiers distincts, alors , car la distance entre les entrées adjacentes dans est d'au moins ; la situation est plus intéressante lorsqu'elles n'ont pas besoin d'être distinctes. $A$ $m = \max(A) + 1$ $B$ $1$

Pour votre question plus générale, imaginez une situation dans laquelle n'est "intéressant" que lorsque . Il semble possible de construire un argument adversaire qui vous oblige à interroger pour tout avant de pouvoir connaître , donc vous devez trier afin de trouver la réponse, qui prend des comparaisons . (Il y a quelques complications car il se peut que nous puissions tester si en temps constant plutôt que linéaire en interrogeant .) C'est le cas même si est un polynôme (de haut degré). $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
la source

Et si A a n - 1 zéros et un seul? Alors la réponse est n, pas 1.

Grigory Yaroslavtsev

Salut Yuval. Il peut y avoir des chiffres répétés dans . Comme l'a dit Grigory, la solution ne semble pas fonctionner.

A

$A$

Kaveh

Je pense que je vois votre idée pour l'argument de la borne inférieure: étant donné nous pouvons calculer rapidement en utilisant les paires de requêtes faites à par un algorithme résolvant le problème dans le temps . Nous pouvons nous assurer que l'algorithme interroge sur tous mais nous ne pouvons pas nous assurer qu'il ne questionne pas d'autres paires. Cependant, nous pouvons définir pour que les autres paires soient une valeur distincte afin que nous puissions éliminer ces paires.

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