(log n)^k = O(n)? 对于k大于等于1。
我的教授在课上给我们展示了这个陈述,但我不确定函数具有O(n)的时间复杂度意味着什么。甚至像n^2 = O(n^2)
这样的东西,函数f(x)怎么可能有运行时间复杂度?
对于这个陈述,它为什么等于O(n),而不是O((logn)^k)?
f(x) = O(g(x))
意味着f(x)
增长的速度比或相当于g(x)
。
技术上解释为:“我们可以找到一个x_0
值和一个比例因子M
,使得x_0
之后f(x)
的大小小于g(x)
的缩放大小。”或者用数学表示:
|f(x)| < M |g(x)|对于所有x > x_0
。
所以对于你的问题:
log(x)^k = O(x)?
是在问:是否存在x_0
和M
这样的数字,使得log(x)^k < M x 对于x>x_0
。
使用各种极限结果即可确定M
和x_0
的存在,而且不需要微积分。
我能想出的最简单的证明方法不依赖于L'Hopitals规则,而是使用泰勒展开式。
e^z = 1 + z + z^2/2 + ... = sum z^m / m!
使用公式z = (N! x)^(1/N)
,我们可以看出
e^(x^(1/N)) = 1 + (N! x)^(1/N) + (N! x)^(2/N)/2 + ... (N! x)^(N/N)/N! + ...
当x>0时,所有项都为正数,因此只保留第N个项,则有
e^((N! x)^(1/N)) = N! x / N! + (...)
= x + (...)
> x for x > 0
对两边取对数(因为对数函数是单调递增的),然后将其乘以N次方(也是单调递增的,因为N>0)
(N! x)^(1/N) > log x for x > 0
N! x > (log x)^n for x > 0
这正是我们需要的结果,对于所有的x > x_0
,存在一些M
使得(log x)^N < M x
,其中M = N!
,x_0=0
。