代码之家 › 专栏 › 技术社区 › Managu

o(polylog(n))的意思是什么?尤其是polylog(n)是如何定义的?

complexity-theory compression full-text-search algorithm

Managu · 技术社区 · 15 年前

简介:
当学术(计算机科学)论文说“o(polylog(n))”时,它们是什么意思?我对“big oh”表示法并不感到困惑,这是我非常熟悉的,但对函数polylog(n)却很熟悉。他们不是在谈论复杂的分析函数 Li _s (Z) 我想。或者是它们?有什么完全不同的吗?

更多细节:
主要是为了个人的兴趣,我最近一直在查看各种关于压缩后缀数组的论文,例如 Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays . 所述的计算复杂度估计有时涉及polylog(n),这是一个我不熟悉的函数。

维基百科给出了 polylog _s (z) 这主要是关于复分析和解析数论。我的怀疑是这与压缩文件中的polylog(n)无关,不过我想听听其他知识渊博的人的意见。如果是这样,为什么认为省略下标是合理的呢?

我唯一的另一个猜测是,也许O(polylog(n))的意思是“对数(n)的多项式函数的渐近性”,但这只是一个猜测:我没有证据证明这一点,这将是一个滥用符号引导。

在任何情况下,一个合理的权威定义的链接将非常感谢!

6 回复 | 直到 15 年前

ShreevatsaR 15 年前

不管符号是否被滥用,poly log(n)的意思是“对数(n)中的某些多项式”,正如“poly(n)”的意思是“n中的某些多项式”。so o(polylog(n))表示“o”(log n) ^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 )。

Hamish Smith 15 年前

它的使用方式 this paper 似乎描述的是:

O(log ^ p n)

Donnie 15 年前

polylog(n)只是“n的对数中的多项式”。 Wikipedia

Kevin Montrose 15 年前

不同 polylog article .你猜差不多了。

kolypto 15 年前

我敢肯定它们只指正整数实轴: Re(n) = n

Ewan Todd 15 年前

沃尔夫拉姆给了你一个 selection 其中 polylogarithm 佩奇看起来很有前途。