簡単な：
学術論文（コンピュータサイエンス）で「O(polylog(n))」と書かれている場合、それは何を意味するのでしょうか。私が混乱しているのは「Big-Oh」表記法ではなく、関数polylog(n)です。彼らは複素解析関数について話しているわけではありません。リス（ Z）思います。それとも違うのでしょうか? まったく違うものなのでしょうか?
もっと詳しく：
主に個人的な興味から、私は最近、圧縮サフィックス配列に関するさまざまな論文を読んでいます。例えば、後方検索の利点 - 効率的な二次メモリと圧縮サフィックス配列の分散実装記載されている計算複雑度の見積もりには、私がよく知らない関数である polylog(n) が含まれることがあります。
Wikipediaでは次のように定義されていますポリログs (z)これは主に複素解析と解析的数論に関するもののようです。圧縮論文の polylog(n) とは関係ないのではないかと思いますが、もっと詳しい人からそうでない意見を聞きたいです。もしそうだとしたら、なぜ下付き文字を省略するのが合理的だと考えられるのでしょうか?
私の唯一の推測は、O(polylog(n)) は「log(n) の多項式関数の漸近」を意味するのではないかということです。しかし、これは単なる推測に過ぎません。私にはこれを証明する証拠はなく、さらにこれは表記法の乱用にもなります。
いずれにせよ、妥当な権威のある定義へのリンクをいただければ幸いです。
ベストアンサー1
表記法の乱用かどうかは別として、polylog(n) は「log(n) の何らかの多項式」を意味します。これは、「poly(n)」が「n の何らかの多項式」を意味するのと同じです。したがって、O(polylog(n)) は「何らかの k に対して O((log n) k )」を意味します。(Wikipedia: 多重対数または、文脈を理解するために、スコット・アーロンソン教授のブログをご覧ください。私の好きな成長率。
重要なのは、定数因子を気にしないことが多いのと同じように、対数の累乗を無視すると便利な場合が多いということです。時には「対数因子」が完全に無視され、「Õ(f(n))」—上にチルダが付いたO—が表示されることがあります。手段「O(f(n) polylog(f(n)))」、つまり「あるkに対してO(f(n) (log f(n)) k )」。