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

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

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

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

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

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

Ответы

Ответ 1

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

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

Ответ 2

Способ, которым он используется в этой статье, как представляется, описывает что-то как:

O (log ^ p n)

Ответ 3

Полилог (n) является просто "полиномиальным в логане n". Wikipedia

Ответ 4

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

Ответ 5

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

Ответ 6

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