f(n) = log(n)^m 是所有自然数 m 的 O(n)？

Question

一位助教今天告诉我这是真的，但我无法通过谷歌搜索来验证这一点。这就是说像 log(n)^2, log(n)^3, ..., log(n)^m 这样的函数都是 O(n).

这是真的吗？

Answer 1

领取

The function f(n) = log(n)^m, for any natural number m > 2 (m ∈ ℕ+) is in O(n).

I.e. there exists a set of positive constants c and n0 such that the following holds:
log(n)^m < c · n, for all n > n0, { m > 2 | m ∈ ℕ+ }      (+)

证明

假设(+)不成立，并将此假设表示为(*)。

即，给定 (*)，不存在正常数集 c 和 n0 使得 (+) 对 m > 2 的任何值都成立。在此假设下，以下内容成立，即 对于所有正常数 c 和 n0，存在一个 n > n0 这样 （感谢@Oriol） :

 log(n)^m ≥ c · n, { m > 2 | m ∈ ℕ+ }                       (++)

现在，如果 (++) 成立，那么在对不等式两边应用任何单调递增函数后，(++) 中的不等式也将成立。一个这样的函数是 log 函数本身

因此，在(++)成立的假设下，对于所有正常数c和n0，存在n > n0这样以下成立

 log(log(n)^m) ≥ log(c · n), { m > 2 | m ∈ ℕ+ }

 m · log(log(n)) ≥ log(c · n), { m > 2 | m ∈ ℕ+ }           (+++)

然而，(+++) 显然是一个矛盾：因为 log(n) 支配（w.r.t。增长）超过 log(log(n))，

我们可以——对于任何给定的 m > 2 值——总能找到一组常数 c 和 n0 使得 (+++)（因此 (++)) 违反了所有 n > n0.

因此，假设 (*) 被矛盾证明是错误的，因此 (+) 成立。

=> for f(n) = log(n)^m, for any finite integer m > 2, it holds that f ∈ O(n).

Answer 2

是的。如果函数是 f(n)，则表示 m 是一个参数，而 f 不依赖于它。事实上，我们每个 m.

都有不同的 f_m 函数

f_m(n) = log(n)^m

那就简单了。给定 m ∈ ℕ，重复使用 L'Hôpital's rule

        f_m(n)            log(n)^m            m * log(n)^(m-1)
limsup ──────── = limsup ────────── = limsup ────────────────── =
 n→∞      n        n→∞       n         n→∞           n

          m*(m-1) * log(n)^(m-2)                m!
= limsup ──────────────────────── = … = limsup ──── = 0
                 n                       n→∞    n

因此，f_m ∈ O(n).

当然，如果有f(m,n) = log(n)^m就不一样了。例如取 m=n,

        f(n,n)            log(n)^n
limsup ──────── = limsup ────────── = ∞
 n→∞      n        n→∞       n

然后f ∉ O(n)

Answer 3

在许多方面更直观的是，对于任何正整数 m 我们有：

x^m = O(e^x)

这表明指数增长支配多项式增长（这就是为什么指数时间算法在计算机编程中是个坏消息）。

假设这是真的，只需取 x = log(n) 并使用这样的事实，即 x 趋于无穷大当且仅当 n 趋于无穷大并且 e^x 和 log(x) 是倒数：

log(n)^m = O(e^log(n)) = O(n)

最后，由于对于任何自然数m，根函数n => n^(1/m)是递增的，我们可以将结果重写为

log(n) = O(n^(1/m))

这种写法表示 log(n) 比 n 的任何根（平方、立方等）都慢，这更明显地对应于 e^n 比 e^n 增长得更快n.

的任意幂

关于编辑：上面显示 log(n)^m = O(n) 跟在更熟悉的 x^m = O(e^x) 之后。为了将其转换为更独立的证明，我们可以直接展示后者。

从 e^x 的泰勒级数开始：

e^x = 1 + x/1! + x^2/2! + x^3/3! + ... + x^n/n! + ...

众所周知，这对所有实数都是收敛的 x。如果给出一个正整数m，让K = (m+1)!。然后，如果 x > K 我们有 1/x < 1/(m+1)!，因此

x^m = x^(m+1)/x < x^(m+1)/(m+1)! < e^x

这意味着 x^m = O(e^x)。（上面最后一个不等式是正确的，因为如果 x>0 和 x^(m+1)/(m+1)! 只是其中一项，e^x 展开式中的所有项都严格为正。）

f(n) = log(n)^m 是所有自然数 m 的 O(n)？

f(n) = log(n)^m is O(n) for all natural numbers m?

big-o