Si no es polinomial o exponencial, ¿cómo se llama esta función?

13

Acabo de encontrar esta oración en la página 6 de "Computadoras e Intractabilidad" de Garey y Johnson.

Cualquier algoritmo cuya función de complejidad de tiempo no pueda estar tan limitada se llama algoritmo de tiempo exponencial (aunque debe tenerse en cuenta que esta definición incluye ciertas funciones de complejidad de tiempo no polinomiales, como , que normalmente no se consideran exponenciales funciones).nlogn

Mi pregunta de la siguiente manera,

Si no es polinómico ni exponencial, entonces, ¿cómo se llama esta función? ¿Esto tiene un nombre o casos especiales o no?nlogn

Gracias.

usuario777
fuente

Respuestas:

12

No existe una terminología fija para este tipo de funciones. A veces puede ver "subexponential" o "superpolynomial" para referirse a este tipo de comportamiento.

Tom van der Zanden
fuente
77
Otro término común es cuasipolinomial .
Yuval Filmus
3
cn11+γ
clog1+γn
c,γ>0