代码之家 › 专栏 › 技术社区 › Bad Request

如何确定函数f是否在θ(g)中

big-theta

4

Bad Request · 技术社区 · 14 年前

充分披露:这是一个家庭作业问题。我真的有点吓坏了,当它看起来如此简单的时候,我已经逃避了这么久。

问题是,f(n)=n^2*log(n),g(n)=n^2.1。f在θ(g)中吗?

_1个 ,丙 _2个所以过了某个n _0个 _1个 g(n)<=c f(n)。但我甚至不确定f是否在θ(g)中。我很困惑。

2 回复 | 直到 14 年前

1

MahlerFive 14 年前

根据我的记忆,要证明f(n)在θ(g(n))中,可以采用两种不同的方法:

证明f在O(g)中,证明g在O(f)中。

2

0

I GIVE CRAP ANSWERS 14 年前

首先注意措辞。”是f在θ(g)中。这意味着他们希望你首先对这是否是真的做出一个有根据的猜测。

反问题:θ(n)是否与θ(n*log(n))相同?我们知道答案。。。不,它们不是(例如,否则基于比较的排序将是线性的)。这对你的问题有什么建议?

为了证明这一说法,请遵循MahlerFive的另一个答案。为了完整性,为了反驳这个说法,假设敌人提出了常数c1和c2。现在我们的目标是显示,尽管敌人已经出现了什么常数(即,对于所有c1和c2),但没有n0满足边界。换言之,表明您无法选择c1和c2。在你的例子中,技巧可能集中在f函数中的log(n)因子上。对数(n)是单调递增的,这表明我们可以通过插入一个较大的n值使该因子任意增大。