(log n)^k = O(n)? 对于k大于等于1

Question

(log n)^k = O(n)? 对于k大于等于1。

我的教授在课上给我们展示了这个陈述，但我不确定函数具有O(n)的时间复杂度意味着什么。甚至像n^2 = O(n^2)这样的东西，函数f(x)怎么可能有运行时间复杂度？

对于这个陈述，它为什么等于O(n)，而不是O((logn)^k)？

- user1084113

---

从常见问题解答中：「你的问题应该要有明确的范围。如果你可以想象一本完整回答你问题的书，那么你的问题就太多了。」 - Steve

Answer 1

(log n)^k = O(n)?

是的。大O符号的定义是，如果存在正常数N和c，使得对于所有n > N：f(n) <= c*g(n)，则函数f在O(g(n))中。在这种情况下，f(n)为(log n)^k，g(n)为n，因此如果我们将其插入到定义中，我们得到：“存在常数N和c，使得对于所有n > N：(log n)^k <= c*n”。这是正确的，因此(log n)^k在O(n)中。

how can a function f(x) have a run time complexity

它不会。大O符号与运行时间复杂度无关。大O符号是一种分类函数增长的符号表示法。通常，我们所讨论的函数测量某些算法的运行时间，但我们可以使用大O符号来讨论任意函数。

- sepp2k

Answer 2

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。

- Michael Anderson