O（polylog（n））の意味は何ですか？特に、polylog（n）はどのように定義されていますか？

Question

簡潔：
学術論文（コンピューターサイエンス）で「O（polylog（n））」と書かれている場合、それはどういう意味ですか？ 「Big-Oh」に戸惑うことはありません。表記法、私は非常によく知っているが、むしろ関数polylog（n）によって。彼らは複雑な分析関数 Li _s （Z）と思います。それとも彼らですか？多分まったく違うものですか？

詳細：
主に個人的な興味のために、私は最近、圧縮サフィックスアレイに関するさまざまな論文を調べてきました。 後方検索の利点-効率的なセカンダリメモリと圧縮サフィックスアレイの分散実装。記載されている計算の複雑さの見積もりには、polylog（n）が含まれることがありますが、これは私がよく知らない関数です。

ウィキペディアは polylog _s （z）の定義を提供します。主に複雑な分析と解析的数論についてのようです。私の疑いは、それが圧縮紙のpolylog（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 を参照するか、コンテキストで確認するには、Scott Aaronson教授のブログ：< a href = "http://scottaaronson.com/blog/?p=263" rel = "noreferrer">お気に入りの成長率。）

重要なのは、定数係数を気にしないことが多いように、対数のべき乗を無視すると便利なことが多いということです。時々、「ログ要因」完全に無視され、＆quot;＆＃213;（f（n））＆quot; ＆＃8212;＆nbsp; Oの上にチルダがあります＆＃8212; 意味＆quot; O（f（n）polylog（f（n））） ＆quot ;、つまり＆quot; O（f（n）（log f（n）） ^k ）いくつかのk＆quot;。

Answer 2

このペーパーでの使用方法何かを次のように説明しているようです：

O（log ^ p n）

Answer 3

Polylog（n）は、単に「nのログ内の多項式」です。 ウィキペディア

Answer 4

異なるポリログ記事。かなり近いと思います。

Answer 5

これらは正の整数の実軸のみを意味していると確信しています： Re（n）= n

Answer 6

Wolframは、選択を提供し、その中の polylogarithm ページが最も有望に見えます。