Zwischen O (nlog * n) und O (n)?

Question

Gibt es eine wirkliche Komplexität zwischen O (n logstar (n)) und O (n)? Ich weiß, dass O (n sqrt (logstar (n))) und andere ähnliche Funktionen zwischen diesen beiden sind, aber ich meine etwas Original, das nicht aus logstar (n) gemacht wird.

Answer 1

Ja, gibt es. Das berühmteste Beispiel wäre die Ackermann inverse function α (n), die viel langsamer wächst als log * n. Es zeigt sich in Kontexten wie der Disjoint-Set-Gesamtstruktur Datenstruktur, wo jede Operation einen amortisierten Kosten von O (α (n)) hat.

Sie können sich log * n so vorstellen, wie oft Sie log auf n anwenden müssen, um den Wert auf eine feste Konstante (z. B. 2) zu reduzieren. Sie können dies dann verallgemeinern, um ** n zu protokollieren, dh wie oft Sie log * auf n anwenden müssen, um den Wert auf 2 zu reduzieren. Sie können dann log *** n, log **** n definieren , log ***** n usw. auf ähnliche Weise. Der Wert α (n) wird normalerweise als die Anzahl der Sterne angegeben, die Sie in das Protokoll ^{** ... *} n eingeben müssen, um den Wert auf 2 herunterzusetzen, sodass er viel langsamer wächst als die iterierte Logarithmusfunktion.

Intuitiv gesprochen, Sie von log n als Kehrwert der Potenzierung (wiederholte Multiplikation) denken kann, log * n als das Inverse von tetration (wiederholte Potenzierung), log ** n als die Inverse von pentation (wiederholte tetration), usw. Die Ackermann-Funktion wendet die Verallgemeinerung der Potenzierung n-ter Ordnung auf die Zahl n effektiv an, also entspricht ihre Inverse der Höhe eines Potenzierungsgrads, den Sie anwenden müssen, um zu ihr zu gelangen. Dies führt zu einer unglaublich langsam wachsenden Funktion.

Die am meisten komisch langsam wachsende Funktion, die ich jemals in einem ernsthaften Zusammenhang verwendet habe, ist α * (n), die Anzahl der Male, die Sie die Ackermann inverse Funktion auf eine Zahl n anwenden müssen, um sie auf einige abzusetzen feste Konstante. Es ist fast undenkbar, wie groß eine Eingabe wäre, die Sie in diese Funktion stecken müssten, um etwas zurück zu bekommen, etwa 10. Wenn Sie neugierig sind, the paper that introduced it is available here.