Linearer Zeitalgorithmus zum Auffinden von verschobenen max

11

Angenommen, wir erhalten ein Array das nichtnegative ganze Zahlen enthält (nicht unbedingt verschieden).A[1..n]

Lassen sein A in der nichtwachsende Reihenfolge sortiert. Wir wollen m = max i [ n ] B [ i ] + i berechnen .BA

m=maxi[n]B[i]+i.

Die naheliegende Lösung besteht darin, sortieren und dann m zu berechnen . Dies ergibt einen Algorithmus, der im schlimmsten Fall in der Zeit O ( n lg n ) läuft .AmO(nlgn)

Kann man es besser machen? Können wir in linearer Zeit berechnen ?m


Meine Hauptfrage ist die oben. Es wäre jedoch interessant, die folgende Verallgemeinerung des Problems zu kennen.

Lassen werden A , sortiert nach irgendeinem Vergleich Oracle und f eine Funktion von einem Oracle gegeben. Gegeben A und Orakel für und f , was können wir sagen , über die benötigte Zeit zu berechnen m = max i [ n ] f ( B [ i ] , i ) ?BAfAfm=maxi[n]f(B[i],i)

Wir können immer noch in O ( n lg n ) Zeit berechnen . Aber können wir für diesen verallgemeinerten Fall eine superlineare Untergrenze beweisen?mO(nlgn)

f

Kaveh
quelle

Antworten:

10

m

A[0..n1]B[0..n1]m=maxiB[i]+i

max=maxiA[i]maxm

A[j]B[k]A[j]maxn

B[k]+kB[k]+(n1)=A[j]+(n1)(maxn)+(n1)=max1<maxm.

A[j]A[j]maxn[maxn,max]

A[maxn,max]m

Marzio De Biasi
quelle
... mmm ... aber was kostet C [x] = C [x] +1?!?
Marzio De Biasi
1
[Mn,M]|f(B[i],i)B[i]|=O(n)i
Danke @Marzio. :) Ich habe Ihre Antwort aus Gründen der Klarheit leicht bearbeitet. Fühlen Sie sich frei, meine Bearbeitung zurückzusetzen oder weiter zu bearbeiten.
Kaveh
1
f(x,i)xin|f(x,i)x|=O(n)
@Kaveh: Bearbeiten ist ok! Ich schrieb die Antwort schnell und war mir nicht einmal sicher, ob sie richtig war: -S
Marzio De Biasi
-1

Am=max(A)+1B1

f(B[i],j)i=jf(B[i],i)imaxif(B[i],i)AΩ(nlogn)A[i]=B[j]f(A[i],j)f

Yuval Filmus
quelle
1
Was ist, wenn A n - 1 Nullen und eine einzelne Eins hat? Dann ist die Antwort n, nicht 1.
Grigory Yaroslavtsev
A
ABfo(nlgn)f(B[i],i)f