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

Полиномиальная функция с логарифмическими членами

В математике полилогарифмическая функция от n — это многочлен от логарифма n , [ ^1]

${\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.}$

Обозначение log ^k n часто используется как сокращение для (log n ) ^k , аналогично sin ² θ для (sin θ ) ² .

В информатике полилогарифмические функции встречаются как порядок времени для некоторых операций со структурой данных . Кроме того , экспоненциальная функция полилогарифмической функции производит функцию с квазиполиномиальным ростом , и говорят, что алгоритмы с такой временной сложностью требуют квазиполиномиального времени . ^[2]

Все полилогарифмические функции n являются o( n ^ε ) для любого показателя ε > 0 (для значения этого символа см. малую нотацию o ), то есть полилогарифмическая функция растет медленнее, чем любая положительная экспонента. Это наблюдение является основой для мягкой нотации O Õ( n ) . ^[3]

Ссылки

1. Блэк, Пол Э. (2004-12-17). "полилогарифмический". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Получено 2010-01-10 .
2. Complexity Zoo : Класс QP: Квазиполиномиальное время
3. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Стайн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Кембридж, Массачусетс: The MIT Press. стр. 74–75. ISBN 9780262046305.