渐近表示法:找到两个常数,使得 n >= n0



这里有一个渐近表示法问题:

设g(n(=27n^2+18n,设f(n(=0.5n^2−100。求正常数n0、c1和c2,使得对于所有n≥n0,c1f(n(≤g(n(≥c2f(n。

这是θ的解吗?我是否证明27n^2+18n=Ω(0.5n^2−100(,然后证明(27n^2+18n(=O(0.5n^ 2−100(?

在这种情况下,c1和c2不是分别是1和56吗?n0会是我发现的两个n0中的较高值吗?

有无限多的解决方案。我们只需要摆弄代数就能找到一个。

首先要注意的是,对于所有n≥15,g和f都是正的。特别地,g(15(=6345,f(15(=12.5。(n的所有较小值都使f<0。(这意味着n0=15可能与任何较大值一样适用。

下一个音符g'(n(=54n+18和f'(n

由于f(15(<g(15(和f’(n(<g'(n(对于所有n>=15,选择c1=1。

证明这是一个不错的选择:

0.5n^2−100≤27n^2+18n<=>26.5n^2+18n+100≥0

对于所有n≥15,显然成立。

c2呢?首先,我们希望c2*f(n(的生长速度至少与g:c2f'(n(≥g`(n(一样快,或者对于n≥15,c2*n≥54n+18。所以选择c2≥56,这显然是真的。

不幸的是,当n0=15时,c2=56不太适用。还有另一个标准需要满足:c2*f(15(≥g(15(。因此,56还不够大:56*f(15(只有700;g(15(要大得多。

通过上面关系式中的替换和更多的代数,结果证明c2=508起到了作用。

证明:

27n^2+18n≤508*(0.5n^2−100(
<=>27n^2+18n≤254n^2−50800
<=>227n^2-18n-50800≥0

当n=15时,通过简单的替换,这是真的。对于n的所有较大值,请注意,对于所有n≥15,lhs导数454n-18是正的,因此函数在该域上也是不递减的。这也使得这种关系成立。

总之,我们已经证明n0=15、c1=1和c2=508是一种解决方案。

相关内容

  • 没有找到相关文章

最新更新