为了
f = n(log(n))^5
g = n^1.01
是
f = O(g)
f = 0(g)
f = Omega(g)?
我尝试将两者除以 n，我得到了
f = log(n)^5
g = n^0.01
但我仍然不知道哪个增长更快。有人可以帮我解决这个问题并解释答案的原因吗？我真的很想知道（没有计算器）如何确定哪一个增长得更快。
问问题
4234 次
4 回答
8
可能最容易比较它们的对数曲线：
如果（对于某些 C1、C2、a>0）
f < C1 n log(n)^a
g < C2 n^(1+k)
然后（对于足够大的 n）
log(f) < log(n) + a log(log(n)) + log(C1)
log(g) < log(n) + k log(n) + log(C2)
两者都以 log(n) 增长为主，所以问题是哪个残差更大。log(n) 残差比 log(log(n)) 增长得快，不管 k 有多大或 a 有多大，所以 g 会比 f 增长得更快。
所以就大 O 表示法而言：g 的增长速度比 f 快，所以 f 可以（渐近地）从上面被 g 之类的函数限制：
f(n) < C3 g(n)
所以 f = O(g)。类似地，g 可以从下方以 f 为界，因此 g = Omega(f)。但是 f 不能从下面被像 g 这样的函数限制，因为 g 最终会超过它。所以 f != Omega(g) 和 f != Theta(g)。
但是 aaa 提出了一个很好的观点：直到 n 变得非常大，g 才开始支配 f。
我对算法缩放没有太多经验，所以欢迎指正。
于 2010-09-02T06:05:27.707 回答
3
我会将其分解为几个简单、可重用的引理：
引理 1：对于一个正常数 k，f = O(g) 当且仅当 f = O(kg)。
证明：假设 f = O(g)。那么存在常数 c 和 N 使得 |f(n)| < c |g(n)| 对于 n > N。因此 |f(n)| < (c/k) (k |g(n)| ) 对于 n > N 和常数 (c/k)，所以 f = O (kg)。反之亦然。
引理 2：如果 h 是一个正单调递增函数并且 f 和 g 对于足够大的 n 是正的，那么当且仅当 h(f) = O( h(g) ) 时 f = O(g)。
证明：假设 f = O(g)。那么存在常数 c 和 N 使得 |f(n)| < c |g(n)| 对于 n > N。因为对于 n > M，f 和 g 是正数，所以对于 n > max(N, M)，f(n) < cg(n)。因为 h 是单调递增的，所以 h(f(n)) < ch(g(n)) for n > max(N, M)，最后是 |h(f(n))| < c |h(g(n))| 对于 n > max(N, M)，因为 h 是正数。因此 h(f) = O(h(g))。反之亦然；关键事实是，如果 h 单调递增，则 h(a) < h(b) => a < b。
引理 3：如果 h 是一个可逆的单调递增函数，则 f = O(g) 当且仅当 f(h) + O(g(h))。
证明：假设 f = O(g)。那么存在常数 c, N 使得 |f(n)| < c |g(n)| 对于 n > N。因此 |f(h(n))| < c |g(h(n))| 对于 h(n) > N。由于 h(n) 是可逆且单调递增的，因此当 n > h^-1(N) 时，h(n) > N。因此 h^-1(N) 是我们需要的新常数，并且 f(h(n)) = O(g(h(n))。反之亦然，使用 g 的逆。
引理 4：如果在 n > M 时 h(n) 不为零，则当且仅当 f(n)h(n) = O(g(n)h(n)) 时，f = O(g)。
证明：如果 f = O(g)，那么对于常数 c, N, |f(n)| < c |g(n)| 对于 n > N。由于 |h(n)| 对 n > M 为正，|f(n)h(n)| < c |g(n)h(n)| 对于 n > max(N, M) 等 f(n)h(n) = O(g(n)h(n))。反之亦然，使用 1/h(n)。
引理 5a：log n = O(n)。
证明：设 f = log n，g = n。那么 f' = 1/n 和 g' = 1，所以对于 n > 1，g 比 f 增加得更快。此外，g(1) = 1 > 0 = f(1)，所以 |f(n)| < |g(n)| 对于 n > 1 和 f = O(g)。
引理 5b：n != O(log n)。
证明：对矛盾另作假设，令 f = n 且 g = log n。那么对于一些常数 c, N, |n| < c |日志 n| 对于 n > N。
令 d = max(2, 2c, sqrt(N+1) )。通过引理 5a 中的计算，由于 d > 2 > 1，log d < d。因此 |f(2d^2)| = 2d^2 > 2d(log d) >= d log d + d log 2 = d (log 2d) > 2c log 2d > c log (2d^2) = cg(2d^2) = c |g(2d ^2)| 对于 2d^2 > N，矛盾。因此 f != O(g)。
因此，现在我们可以汇总您最初提出的问题的答案。
第1步：
log n = O(n^a)
n^a != O(log n)
对于任何正常数 a。
证明：引理 5a 的 log n = O(n)。因此 log n = 1/a log n^a = O(1/an^a) = O(n^a) 由引理 3（对于 h(n) = n^a）、4 和 1。第二个事实通过使用引理 5b 类似地遵循。
第2步：
log^5 n = O(n^0.01)
n^0.01 != O(log^5 n)
证明：log n = O(n^0.002) 通过步骤 1。然后通过引理 2（其中 h(n) = n^5），log^5 n = O( (n^0.002)^5 ) = O(n ^0.01)。第二个事实也类似。
最终答案：
n log^5 n = O(n^1.01)
n^1.01 != O(n log^5 n)
换句话说，
f = O(g)
f != 0(g)
f != Omega(g)
证明：将引理 4（使用 h(n) = n）应用于步骤 2。
随着实践，这些规则变得“显而易见”和第二天性。除非你的测试要求你证明你的答案，否则你会发现自己在处理这些大 O 问题。
于 2010-09-02T08:17:19.780 回答
2
检查他们的路口怎么样？
Solve[Log[n] == n^(0.01/5), n]
1809
{{n -> 2.72374}, {n -> 8.70811861815 10 }}
我用 Mathematica 作弊
你也可以用衍生品推理，
In[71]:= D[Log[n], n]
1
-
n
In[72]:= D[n^(0.01/5), n]
0.002
------
0.998
n
考虑当 n 变得非常大时会发生什么，首先变化趋于零，后来函数不会失去它的导数（指数大于 0）。
这告诉你理论上哪个更复杂。但是在实际区域中，第一个功能将增长得更快。
于 2010-09-02T06:15:44.147 回答
0
这不是 100% 在数学上没有证明有关日志的东西，但他说：
f = log(n)^5
g = n^0.01
我们记录两者的日志：
log(f) = log(log(n)^5)) = 5*log(log(n)) = O(log(log(n)))
log(g) = log(n^0.01) = 0.01*log(n) = O(log(n))
从这里我们看到第一个增长渐近缓慢，因为它有一个双对数并且对数增长缓慢。为什么这种采用对数的推理是有效的，一个非正式的论据是这样的：log(n) 大致告诉您数字 n 中有多少位。因此，如果 g 的位数渐近增长快于 f 的位数，那么实际数 g 的增长速度肯定快于数 f！
于 2010-09-02T23:48:56.393 回答