Man*_*agu 49 compression algorithm complexity-theory full-text-search
简介:
当学术(计算机科学)论文说"O(polylog(n))"时,它们是什么意思？我不会对"Big-Oh"符号感到困惑,我非常熟悉它,而是使用polylog(n)函数.他们不是在谈论我认为的复杂分析函数Li s(Z).或者是他们？也许完全不同的东西？
更多细节:
主要是出于个人兴趣,我最近一直在查看关于压缩后缀阵列的各种论文,例如后向搜索的优点 - 高效的辅助内存和压缩后缀阵列的分布式实现.所述的计算复杂度估计有时涉及polylog(n),这是我不熟悉的函数.
维基百科给出了polylog s(z)的定义,它似乎主要是关于复杂分析和解析数论.我怀疑它与压缩文件中的polylog(n)无关,尽管我更喜欢听到知识渊博的人的其他信息.如果是这种情况,为什么省略下标是否合理？
我唯一的猜测是,O(polylog(n))可能意味着"渐近于log(n)的多项式函数".但这只是一个猜测:我没有证据证明这一点,并且它会滥用记谱法来启动.
在任何情况下,非常感谢指向合理权威定义的链接!
Shr*_*saR 68
滥用符号或不符号,polylog(n)的意思是"log(n)中的某些多项式",正如"poly(n)"可以表示"n中的某些多项式".所以O(polylog(n))意味着"O((log n)k)对于某些k".(参见维基百科:Polylogarithmic,或者,在上下文中看到它,Scott Aaronson教授的博客:我最喜欢的增长率.)
关键在于,正如我们经常不关心常数因素一样,忽略对数幂通常很方便.有时候,"对数因子"被完全忽略,你可能会看到"Õ(f(n))" - O在它上面有一个波浪号 - 意思是 "O(f(n)polylog(f(n)))",即,"O(f(n)(log f(n))k)对于某些k".