Если

Я только что нашел это предложение на странице 6 книги Гари и Джонсона «Компьютеры и неразрешимость».

Любой алгоритм, функция сложности времени которого не может быть настолько ограниченной, называется алгоритмом экспоненциального времени (хотя следует отметить, что это определение включает в себя некоторые неполиномиальные функции сложности времени, такие как , которые обычно не рассматриваются как экспоненциальные функции). $n^{\log n}$

Мой вопрос следующим образом,

Если не является полиномиальным или экспоненциальным, то как называется эта функция? У этого есть имя или особые случаи или нет? $n^{\log n}$

Спасибо.

algorithms terminology polynomial-time user777
источник

Ответы:

Для этих типов функций нет фиксированной терминологии. Иногда вы можете увидеть «субэкспоненциальный» или «суперполином», используемый для обозначения такого рода поведения.

Том ван дер Занден
источник

Другой распространенный термин - квазиполиномиальный .

Юваль Фильмус

с^{N^{\frac{1}{1 + γ}}}

$c^{n^{\frac1{1+\gamma}}}$ в то время как суперполином или квазиполином является формой

с^{{журнал}^{1 + γ} N}

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

c, γ > 0

$c,\gamma>0$ оставшиеся исправлены