简介:
当学术(计算机科学)论文说“O(polylog(n))”时，它们是什么意思？我并没有对我非常熟悉的“Big-Oh”表示法感到困惑，而是对函数 polylog(n) 感到困惑。他们不是在谈论复杂的分析功能 Lis(Z)我认为。或者他们是？也许是完全不同的东西？
更多详情:
主要是出于个人兴趣，我最近一直在查看有关压缩后缀数组的各种论文，例如Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays .所述的计算复杂度估计有时涉及 polylog(n)，这是一个我不熟悉的函数。
维基百科给出了polylogs(z)的定义这似乎主要是关于复杂的分析和解析数论。我怀疑它与压缩论文中的 polylog(n) 无关，尽管我很想听听更有知识的人的说法。如果是这样，为什么省略下标被认为是合理的？
我唯一的其他猜测是，也许 O(polylog(n)) 应该表示“渐近到 log(n) 的多项式函数”。但这只是一个猜测:我没有这方面的证据，这将是对符号的滥用。
无论如何，我们将不胜感激指向合理权威定义的链接!
最佳答案
无论是否滥用符号，polylog(n) 确实表示“log(n) 中的某个多项式”，就像“poly(n)”可以表示“n 中的某个多项式”一样。所以 O(polylog(n)) 的意思是“O((log n)k) for some k”。 (请参阅 Wikipedia: Polylogarithmic，或者，要在上下文中查看它，Scott Aaronson 教授的博客:My Favorite Growth Rates。)
要点在于，正如我们通常不关心常数因子一样，忽略对数的幂通常也很方便。有时“对数因子”会被完全忽略，您可能会看到“Õ(f(n))”——O 上面有波浪线——means “O(f(n) polylog(f(n)))”，即“O(f(n) (log f(n))k) 对于某些 k”。
关于algorithm - O( polylog(n) ) 是什么意思？特别是，polylog(n) 是如何定义的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1801135/