简要:
当学术(计算机科学)论文说“O(polylog(n))”时，它们是什么意思？我对我非常熟悉的“Big-Oh”表示法并不感到困惑，而是对函数polylog(n)感到困惑。我认为他们不是在谈论复杂的分析功能Li(Z)。还是他们？可能完全不同吗？
更多详情:
主要出于个人利益，我最近一直在浏览有关压缩后缀数组的各种论文，例如Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays。陈述的计算复杂性估算有时涉及polylog(n)，这是我不熟悉的功能。
维基百科给出了polylog(z)的定义，该定义似乎主要是关于复杂分析和解析数论的。我的怀疑是，它与压缩文件中的polylog(n)没有关系，尽管我很乐意听取其他更博学的人的意见。如果是这种情况，为什么省略下标到底是合理的呢？
我唯一的其他猜测是，也许O(polylog(n))的意思是“渐近到log(n)的多项式函数”。但这只是一个猜测:我没有任何证据，这会导致启动符号的滥用。
无论如何，将不胜感激地链接到一个权威的定义!
最佳答案
是否滥用表示法，polylog(n)的确表示“log(n)中的某些多项式”，就像“poly(n)”可以表示“n中的某些多项式”一样。因此，O(polylog(n))的意思是“对于某些k，O((log n)k)”。 (请参阅Wikipedia: Polylogarithmic，或者在上下文中查看它，Scott Aaronson教授的博客:My Favorite Growth Rates。)
关键是，正如我们经常不在乎常数因子一样，忽略对数的幂通常很方便。有时，“对数因子”会被完全忽略，您可能会看到“Õ(f(n))” —在其上有波浪号的O — means“O(f(n)polylog(f(n)))”，即，“对于某些k为O(f(n)(log f(n))k)”。