Si n'est pas polynomial ou exponentiel, alors comment s'appelle cette fonction?

13

Je viens de trouver cette phrase à la page 6 de "Ordinateurs et intractabilité" de Garey et Johnson.

Tout algorithme dont la fonction de complexité temporelle ne peut pas être ainsi bornée est appelé algorithme de temps exponentiel (bien qu'il convient de noter que cette définition inclut certaines fonctions de complexité temporelle non polynomiales, comme , qui ne sont normalement pas considérées comme exponentielles les fonctions).nJournaln

Ma question comme suit,

Si n'est pas polynomial ni exponentiel, alors comment s'appelle cette fonction? Est-ce que cela a un nom ou des cas spéciaux ou non?nJournaln

Je vous remercie.

user777
la source

Réponses:

12

Il n'y a pas de terminologie fixe pour ces types de fonctions. Vous pouvez parfois voir «sous-exponentiel» ou «superpolynomial» utilisé pour désigner ce type de comportement.

Tom van der Zanden
la source
7
Un autre terme courant est quasipolynomial .
Yuval Filmus
3
cn11+γ
cJournal1+γn
c,γ>0