Wenn

13

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).nLogn

Meine frage wie folgt,

Wenn weder polynomisch noch exponentiell ist, wie heißt diese Funktion? Hat dies einen Namen oder Sonderfälle oder nicht?nLogn

Vielen Dank.

user777
quelle

Antworten:

12

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
7
Ein weiterer gebräuchlicher Begriff ist Quasipolynom .
Yuval Filmus
3
@ user777 Ich denke, Subexponential hat die Form
cn11+γ
cLog1+γn
c,γ>0