Wenn

Ich habe diesen Satz gerade auf Seite 6 von Garey und Johnsons "Computers and Intractability" gefunden.

Jeder Algorithmus, dessen Zeitkomplexitätsfunktion nicht so begrenzt werden kann, wird als Exponentialzeitalgorithmus bezeichnet (obwohl zu beachten ist, dass diese Definition bestimmte nichtpolynomielle Zeitkomplexitätsfunktionen wie , die normalerweise nicht als Exponentialfunktionen angesehen werden). $n^{\log n}$

Meine frage wie folgt,

Wenn weder polynomisch noch exponentiell ist, wie heißt diese Funktion? Hat dies einen Namen oder Sonderfälle oder nicht? $n^{\log n}$

Vielen Dank.

algorithms terminology polynomial-time user777
quelle

Antworten:

Für diese Art von Funktionen gibt es keine feste Terminologie. Manchmal wird "subexponentiell" oder "Superpolynom" angezeigt, um auf diese Art von Verhalten zu verweisen.

Tom van der Zanden
quelle

Ein weiterer gebräuchlicher Begriff ist Quasipolynom .

Yuval Filmus

@ user777 Ich denke, Subexponential hat die Form

c^{n^{\frac{1}{1 + γ}}}

$c^{n^{\frac1{1+\gamma}}}$

c^{{Log}^{1 + γ} n}

$c^{\log^{1+\gamma} n}$

c, γ > 0

$c,\gamma>0$