增长顺序

Question

为

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

但我仍然不知道哪一个长得更快。有人能帮我解释一下答案吗？我真的很想知道(没有计算器的，)如何才能确定哪一个增长得更快。

Answer 1

可能最容易比较它们的对数配置文件：

如果(对于某些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。

我对算法缩放没有太多的经验，所以欢迎修正。

Answer 2

我会把它分解成几个简单的，可重复使用的引理：

引理1:对于正常数k，f= O(g)当且仅当f= O(k )。

证明:假设f= O(g)。然后存在常数c和N，使得n>N的x=f(N)_x

引理2:如果h是一个正单调增长函数，f和g对于足够大的n是正的，那么f= O(g)当且仅当h(f) = O( h(g) )。

证明:假设f= O(g)。由于f和g对N > M是正的，f(n) max(N，M)，则存在常数c和N。由于h是单调增加的，所以h(f(n)) max(N，M)，最后是h(f(N))\x max(N，M)，因为h是正的。因此h(f) = O(h(g))。相反的情况类似；关键的事实是，如果h是单调增加的，那么h(a) < h( b ) => a

引理3:如果h是可逆单调增长函数，则f= O(g)当且仅当f(h) + O(g(h))。

证明:假设f= O(g)。因此，当h( N )可逆地单调增加，h( N ) > h^-1(N)时，存在常数c (N)_xN。因此，h^-1(N)是我们需要的新常数，f(h(n)) =O(g(h(N)。相反的情况也是这样，使用g的逆。

引理4:如果h(n)对于n> M，f= O(g)当且仅当f(n)h(n) = O(g(n)h(n))。

证明:如果f= O(g)，则对于N >N的常数c，N，x_f(N)_xN，因为n> M _h(N)_x是正的，x_ f(n)h(n) max(N，M)，so _f(N)h(N)= O(g(n)h(n))。相反，使用1/h(n)进行类似的操作。

引理5a: log = O(n)。

证明:设f = log n，g= n，则f‘= 1/n和g’= 1，所以对于n> 1，g的增长速度比f快，而且g(1) =1>0= f(1)，所以f(N)>1和f= O(g).

引理5b: n != O(log )。

证明:假设另有矛盾，并设f= n和g= log N，则对于某些常数c，N，x_n_nN。

设d= max(2，2c，sqrt(N+1) )。根据引理5a中的计算，自d >2> 1，log d 2d^2 > 2d(log d) >= d log d+d log 2=d (log 2d) > 2c log 2d >c log (2d^2) =c g(2d^2) =c\g(2d^2)=2d^2> N，这是一个矛盾。因此f != O(g)。

所以现在我们可以把你最初提出的问题的答案组合起来。

步骤1：

log n = O(n^a)
n^a != O(log n)

对于任何正常数a。

证明: log n= O(n)，引理5a.因此，log n= 1/a log n^a = O( 1 /a n^a) = O(n^a)是Lemmas 3 (for h(n) = n^a)，4和1。第二个事实类似地使用引理5b。

第2步：

log^5 n = O(n^0.01)
n^0.01 != O(log^5 n)

证明:第1步log n= O(n^0.002)，然后引理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。

随着实践，这些规则变得“明显”和第二天性。除非你的测试要求你证明你的答案，否则你会发现自己正在经历这些大问题。

Answer 3

去检查他们的交叉口怎么样？

Solve[Log[n] == n^(0.01/5), n]

                                       1809
{{n -> 2.72374}, {n -> 8.70811861815 10    }}

我用数学作弊

你也可以用衍生工具推理，

In[71]:= D[Log[n], n]

1
-
n
In[72]:= D[n^(0.01/5), n]

0.002
------
 0.998
n

考虑到当n变得非常大时，变化首先趋向于零，之后的函数不会失去它的导数(指数大于0)。

这告诉你哪一个理论上更复杂。然而，在实际应用领域，第一个功能将增长更快。