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

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

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

обозначений $Журнал к n$ часто используется как сокращение для $(log n) к$ , аналог $греха 2 θ$ для $(sin θ) 2$ .

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

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

Ссылки

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

Эта математическому анализу, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

Эта полиномам, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

[1] Блэк, Пол Э. (17 декабря 2004 г.). «полилогарифмический» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 10 января 2010 г.

[2] Зоопарк сложности : Класс QP: Квазиполиномиальное время

[3] Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Кембридж, Массачусетс: MIT Press. стр. 74–75. ISBN 9780262046305 .

[1]

[2]

[3]