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

Не путать с Полилогарифм.

А полилогарифмическая функция в п это многочлен в логарифм из п,

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

Обозначение ${\displaystyle \log ^{k}n}$ часто используется как сокращение для ${\displaystyle (\log n)^{k}}$, аналогично ${\displaystyle \sin ^{2}\theta }$ за ${\displaystyle (\sin \theta )^{2}}$.

В Информатика, полилогарифмические функции встречаются как порядок из время или же используемая память некоторыми алгоритмы (например, «имеет полилогарифмический порядок»).

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

Рекомендации

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