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

Question

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

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

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

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

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

Answer 1

Злоупотребление обозначениями или нет, polylog (n) означает «некоторый многочлен в log (n)», так же как «poly (n)» может означать «некоторый многочлен от n». Таким образом, O (polylog (n)) означает «O ((log n) ^k ) для некоторого k». (См. Wikipedia: Polylogarithmic , или, чтобы увидеть его в контексте, блог профессора Скотта Ааронсона: Мои любимые темпы роста .)

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

Answer 2

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

O (log ^ p n)

Answer 3

Разное Полилог статьи . Вы догадываетесь, что это довольно близко.

Answer 4

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

Answer 5

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

Answer 6

Я уверен, что они означают только положительную целую действительную ось: Re(n) = n