Spaß mit inversem Ackermann

11

Die inverse Ackermann-Funktion tritt häufig bei der Analyse von Algorithmen auf. Eine großartige Präsentation finden Sie hier: http://www.gabrielnivasch.org/fun/inverse-ackermann . und [Notation: [x] bedeutet, dass wir x auf die nächste ganze Zahl aufrunden, während log ∗ ist die hier beschriebene iterierte Protokollfunktion: http://en.wikipedia.org/wiki/Iterated_logarithm ]

α1(n)=[n/2]
α2(n)=[log2n]
α3(n)=logn
...
αk(n)=1+αk(αk1(n))
α(n)=min{k:αk(n)3}

Meine Frage ist: Was ist die Funktion

k(n)=min{k:αk(n)k}
Klar 1k(n)α(n) . Welche engeren Grenzen kann man für k(n) ? Ist k(n)logα(n) ?
Dana Moshkovitz
quelle
Ich weiß, warum k(n)α(n) , aber können Sie erklären, warum k(n)α(n) ?
jbapple
Ok, bearbeitet auf das unumstrittene k(n)<α(n) .
Dana Moshkovitz
3
@DanaMoshkovitz: Ich habe die Definitionen mithilfe der mir bekannten Ackermann-Hierarchie angenähert: α(n)=min{k:Ak(1)n} und k(n)=min{k:Ak(k)n} . Mit einer typischen Definition der Ackermann-Funktionen ist Ak+1(1)=Ak(Ak(1))Ak(k) . Wenn also Ak(k)n dann ist Ak+1(1)n , dh k(n)α(n)1 . (Ich hoffe, ich habe dort keinen Fehler gemacht.)
Sylvain
1
@DanaMoshkovitz: Zur Verdeutlichung verwende ich und , die etwas schneller wachsen als Ihre Definition, z. B. anstelle von . Es sollte jedoch keine große Konsequenz haben: und sind so ziemlich dasselbe. A1(n)=2nAk+1(n)=Akn+1(1)A2(n)=2n+12nα(n)k(n)
Sylvain
1
@ DanaMoshkovitz: Ich verstehe nicht, warum . Für unendlich viele Werte von Sie , dh wann immer ; Da schnell wächst, haben Sie immer längere solche Sequenzen. Mit Ihren Definitionen ist es sogar möglich, : daher aber . k(n)<α(n)nα(n)=k(n)Ak(k)<nAk+1(1)<Ak+1(k+1)Ak+1(1)Ak(k)α(n)<k(n)α2(8)=3>2α(8)=2k(8)=3
Sylvain

Antworten:

12

Sei die Umkehrung von . . Ich behaupte, dass .AkαkA1(x)=2x,A2(x)=2x,k1(x)=Ax(x)

Da und da , . Als Ergebnis ist .x=αx(Ax(x))z,αy(z)>αx(z)αy(Ax(x))>αx(Ax(x))=xk(Ax(x))=x

Betrachten Sie nun den Wert von . Nach Definition von ist dies . Wir wissen, dass , also . Ich behaupte, dass . . Jetzt ist , also . Da , , also . Somit istα(k1(n))=α(An(n))αminz{αz(An(n))3}αn(An(n))=nα(An(n))>nα(An(n))n+2αn+1(An(n))=1+αn+1(n)α(n)=minz{αz(n)3}αα(n)(n)3n+1>α(n)αn+1(n)3αn+1(An(n))4αn+2(An(n))=1+αn+2(αn+1(n))1+αn+2(4)3.

Wir haben also , also sind und im Wesentlichen gleich.n<α(k1(n))n+2kα

jbapple
quelle
9
Und lassen Sie mich hinzufügen, dass all diese Funktionen nur verschiedene komplizierte Arten sind, die Nummer 4 zu schreiben.
Sariel Har-Peled
0

Das ist falsch; siehe die Kommentare.

Eine Funktion, die dieser sehr nahe kommt, wurde " " genannt und in Petties "Splay Trees, Davenport-Schinzel Sequences und The Deque Conjecture" verwendet , in der er zeigte, dass " deque-Operationen [in einem Spreizbaum] erforderlich sind nur Zeit, wobei die minimale Anzahl von Anwendungen der inversen Ackermann-Funktion ist, die auf eine Konstante abbildet. "αnO(nα(n))α(n)n

Diese Funktion wächst sehr langsam und langsamer als . Betrachten Sie die Funktionlogα(n)f:NN

f(n)={1 n = 02f(n1) n > 0

Diese Funktion wächst ungefähr so ​​schnell wie , wächst also langsamer als . Jetzt werde ich und auf auswerten :A(4,n)A(n)=A(n,n)logα(n)α(n)A(f(n))

logα(A(f(n)))=logf(n)=f(n1)

α(A(f(n)))=1+α(f(n))<1+α(A(n))<2+α(n)

Da , wächst viel schneller als .f(n1)ω(2+α(n))logα(n)α(n)

jbapple
quelle
Wie ist die Beziehung zwischen alpha ^ * und k (n)? (Beachten Sie, dass ich in der Definition von k (n) die Notation alpha_k (n) verwende, die in dem Link definiert ist, den ich in der Frage hatte.)
Dana Moshkovitz
Oh, tut mir leid, ich habe dein als gelesen ! αkαk
jbapple