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

不管符号是否被滥用,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 )。

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

O(log ^ p n)

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

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

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

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