Tag: 复杂度理论

O（polylog（n））的含义是什么？ 特别是，polylog（n）是如何定义的？

简要： 当学术（计算机科学）论文说“O（polylog（n））”时，它们是什么意思？ 我没有被我所熟悉的“Big-Oh”符号，而是由函数polylog（n）所迷惑。 他们不是在谈论复杂的分析函数Li s （Z）我认为。 还是他们？ 完全不同的东西也许？ 更多详情： 主要是为了个人兴趣，我最近一直在研究压缩后缀数组的各种论文，例如向后search的优点 – 有效的二级存储器和压缩后缀数组的分布式实现 。 估计的计算复杂度有时涉及到polylog（n），这是我不熟悉的函数。 Wikipedia给出了polylog s （z）的定义，似乎主要是关于复杂的分析和parsing数论。 我的怀疑是，它与压缩文件中的多词（n）没有关系，尽pipe我很乐意听到其他知识渊博的人。 如果是这样的话，为什么认为省略下标是合理的呢？ 我唯一的猜测是，也许O（polylog（n））应该是“渐近于log（n）的多项式函数”。 但这只是一个猜测：我没有证据certificate，这将是一个滥用符号启动。 无论如何，我们将不胜感激一个合理的权威定义。