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