增长的顺序

Question

对于

f = n(log(n))^5
g = n^1.01

是

f = O(g)
f = 0(g)
f = Omega(g)?

我尝试将两者分开,我得到了

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有多小或多大,因此g将比f增长得更快.

所以就big-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.

我没有很多算法扩展的经验,所以欢迎更正.