Algorytm czasu liniowego znajdowania przesuniętego maks

Załóżmy, że otrzymujemy tablicę $A[1..n]$ zawierającą nieujemne liczby całkowite (niekoniecznie różne).

$B$ $A$

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

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

Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w najgorszym przypadku. $A$ $m$ $O(n \lg n)$

Czy można to zrobić lepiej? Czy możemy obliczyć czasie liniowym? $m$

Moje główne pytanie to powyższe. Byłoby jednak interesujące wiedzieć o następującym uogólnieniu problemu.

Niech być sortowane według niektórych porównania oracle i w zależności od danego wyrocznię. Biorąc pod uwagę i wyrocznie dla i , co możemy powiedzieć o czasie potrzebnym do obliczenia ? $B$ $A$ $\leq$ $f$ $A$ $\leq$ $f$ $m = \max_{i \in [n]} f(B[i],i)$

Możemy obliczyć jeszcze w czasu. Ale czy możemy udowodnić superliniową granicę dolną dla tego uogólnionego przypadku? $m$ $O(n \lg n)$

Jeśli odpowiedź brzmi „tak”, czy dolna granica jest zachowana, jeśli założymy, że jest zwykłą kolejnością na liczbach całkowitych, a jest funkcją „ładną” (monotoniczną, wielomianową, liniową itp.)? $\leq$ $f$

cc.complexity-theory ds.algorithms optimization sorting Kaveh
źródło

Odpowiedzi:

Możemy obliczyć czasie liniowym. $m$

Dla uproszczenia załóżmy, że tablice są oparte na 0: , . Chcemy obliczyć . $A[0..n-1]$ $B[0..n-1]$ $m = \max_i B[i]+i$

Niech . Oczywiście . $max = \max_i A[i]$ $max \leq m$

Niech będzie po sortowaniu. Jeśli mamy $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.$

Dlatego możemy zignorować gdy . Musimy tylko wziąć pod uwagę liczby z zakresu . $A[j]$ $A[j] \leq max - n$ $[max-n, max]$

Możemy użyć liczenia sortowania w celu posortowania numery , które należą do zakresu , w czasie liniowej i użyć do obliczenia posortowanej listy . $A$ $[max-n, max]$ $m$

Marzio De Biasi
źródło

... mmm ... ale jaki jest koszt C [x] = C [x] +1?!?

Marzio De Biasi,

czy jest problem z twoją odpowiedzią? ponieważ wydaje mi się to w porządku: mówisz, że dbamy tylko o elementy tablicy z wartościami w , więc możemy użyć sortowania zliczającego. Działa to dla ogólnego problemu, ilekroć dla wszystkich .

[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

Dzięki @Marzio. :) Lekko zredagowałem twoją odpowiedź dla jasności. Zapraszam do wycofania mojej edycji lub dalszej edycji.

Kaveh,

To rozwiązanie wydaje się działać również dla dowolnego gdzie dla wszystkich i , .

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: edycja jest w porządku! Szybko napisałem odpowiedź i nawet nie byłem pewien jej poprawności: -S

Marzio De Biasi,

-1

Jeśli tablica składa się z różnych liczb całkowitych, to , ponieważ odległość między sąsiednimi wpisami w wynosi co najmniej ; sytuacja jest bardziej interesująca, gdy nie muszą być wyraźne. $A$ $m = \max(A) + 1$ $B$ $1$

W przypadku bardziej ogólnego pytania wyobraź sobie sytuację, w której jest „interesujące” tylko wtedy, gdy . Wydaje się, że możliwe jest skonstruowanie argumentu przeciwnika, który zmusza cię do zapytania dla wszystkich zanim będziesz mógł poznać , dlatego musisz posortować , aby znajdź odpowiedź, która bierze porównania . (Istnieją pewne komplikacje, ponieważ może się zdarzyć, że możemy przetestować, czy w stałym, a nie liniowym czasie, poprzez zapytanie .) Tak jest, nawet jeśli jest wielomianem (wysokiego stopnia). $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
źródło

Co jeśli A ma n - 1 zer i jeden? Zatem odpowiedź brzmi n, nie 1.

Grigorij Jarosławtsev

Cześć Yuval. Nie można powtarzać numery . Jak powiedział Grigory, rozwiązanie wydaje się nie działać.

A

$A$

Kaveh

Myślę, że widzę twój pomysł na dolną granicę argumentu: biorąc pod uwagę , możemy szybko obliczyć używając par zapytań utworzonych dla przez algorytm rozwiązujący problem w czasie . Możemy upewnić się, że algorytm wysyła zapytania do wszystkich ale nie możemy upewnić się, że nie wyszukuje zapytań dla innych par. Możemy jednak ustawić wartość dla innych par, aby były wyróżnialną wartością, abyśmy mogli odrzucić te pary.

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