Полілогарифмічна функція

У математиці полілогарифмічна функція від Шаблон:Mvar — це поліном від логарифма Шаблон:Mvar:

$a_k(\log n{)}^k+a_{k-1}(\log n{)}^{k-1}+\cdots +a_1(\log n)+a_0.$

Для скорочення запису Шаблон:Math часто використовується позначення Шаблон:Math, за аналогією до скорочення Шаблон:Math для Шаблон:Math.

В інформатиці полілогарифмічні функції описують часову складність деяких операцій зі структурами даних. Крім того, композиція експоненційної та полілогарифмічної функцій є функцією з квазіполіноміальним порядком росту. Кажуть, що алгоритми з такою часовою складністю мають квазіполіноміальний час виконання.

У нотації Ландау можна записати, що усі полілогарифмічні функції від Шаблон:Mvar входять до класу Шаблон:Math для довільного Шаблон:Math. Тобто довільна полілогарифмічна функція зростає повільніше, ніж довільний поліном. Це спостереження лежить в основі позначення м’яке О, Шаблон:Math.