В чем смысл O( полилог(n) )?В частности, как определяется polylog(n)?

Question

Краткий:
Когда в академических (компьютерных) статьях говорится "O (polylog (n))", что они имеют в виду?Меня смущает не обозначение "Big-Oh", с которым я очень хорошо знаком, а скорее функция polylog(n).Они не говорят о функции сложного анализа Li_s(Z) Я думаю.Или так и есть?Может быть, что-то совершенно другое?

Более подробно:
В основном из личного интереса, я недавно просматривал различные статьи о сжатых массивах суффиксов, например Преимущества обратного поиска - Эффективная вторичная память и распределенная реализация сжатых массивов суффиксов.Указанные оценки вычислительной сложности иногда включают polylog (n) , с которой я не знаком.

Википедия дает определение полилог_s(z) который, по-видимому, в основном посвящен комплексному анализу и аналитической теории чисел.Я подозреваю, что это не связано с полилогом (n) в документах по сжатию, хотя я хотел бы услышать иное от кого-то более осведомленного.Если это так, то почему именно считается разумным опустить нижний индекс?

Мое единственное другое предположение заключается в том, что, возможно, O (polylog (n)) должно означать "Асимптотическую для полиномиальной функции log (n)". Но это только предположение:У меня нет доказательств этого, и в придачу это было бы злоупотреблением обозначениями.

В любом случае, мы были бы весьма признательны за ссылку на достаточно авторитетное определение!

Answer 1

Злоупотребление обозначениями или нет, polylog (n) действительно означает "некоторый многочлен в log (n)", точно так же, как "poly (n)" может означать "некоторый многочлен в n".Итак, O (полилог(n)) означает "O((log n)^k) для некоторого k".(См. Википедия:Полилогарифмический, или, чтобы увидеть это в контексте, проф.Блог Скотта Ааронсона: Мои любимые Темпы Роста.)

Дело в том, что точно так же, как мы часто не заботимся о постоянных коэффициентах, часто бывает удобно игнорировать степени логарифмов.Иногда "логарифмические факторы" полностью игнорируются, и вы можете увидеть "Õ(f(n))" — O с тильдой над ним — которая означает "O (f(n) полилог (f(n)))", т. е. "O(f(n) (log f(n))^k) для некоторого k".

Answer 2

То, как он используется в этот документ кажется, описывает что-то как:

O(логарифм^p n)

Answer 3

Polylog(n) - это просто "многочлен в логарифме n". Википедия

Answer 4

Другой полилоговая статья.Вы предполагаете, что это довольно близко.

Answer 5

Я уверен, что они имеют в виду только натуральную вещественную ось: Re(n) = n

Answer 6

Вольфрам дает вам выбор, из которых полилогарифм страница выглядит наиболее многообещающе.