大O符号和渐近

让大O符号和渐近

 d  
p(n) = Σ ai n^i 
     i=0

其中广告> 0是n的一个度d多项式，并且令k为一个常数。使用渐近符号的定义来证明以下属性。

a) if k >= d, then p(n) = O(n^k)

也有4个correspoding到欧米茄，θ，小O和小欧米茄属性，但如果我能得到关于如何启动我可以计算其他的人自己出去的想法。

来源

2011-02-26 Thomas Parisi

你应该在这个网站上发布问题（你可能会得到最好的答复）：http://math.stackexchange.com/ – 2011-02-26 22:04:51

-1：“使用渐近符号的定义来证明以下属性“。这句话会导致你对这不是作业的陈述。 – 2011-02-26 22:14:07

他可以修改的考试... – 2011-02-26 22:16:48

这很简单。看看大O记法正式定义在这里：http://en.wikipedia.org/wiki/Big_o_notation#Formal_definition，尤其是在部分limsup结束公式。你要证明的是，当n（n）/ n^k到（正）无穷大时，p（n）/ n^k的极限是一个实数。如果k> d，则限制为零。如果k = d，那么极限是a_d。为什么？因为它是一个简单的多项式（阶数为d），它也是一个多项式（阶数为k）。看看计算多项式的极限。

来源

2011-02-26 22:09:53

啊，我知道那完全不过我需要什么，我不知道如何去这样做一般，这就是我的问题，你有没有在它这方面的任何提示？ – 2011-02-27 01:33:52

你一般是什么意思？计算极限是一般的解决方案。 – 2011-02-27 10:44:00

a) if k >= d, then p(n) = O(n^k)

如果这是真的，则存在N，A和B使得：

p(n) <= A + B*n^k

对于所有n> = N

这种N，A和B存在，采取例如：

 d  
B = Σ ai n^i 
    i=0 


A = 1 
N = 1

你可以在那离开它，如果你认为这是有见地不够，或者实际归纳法证明，这一选择的N，A和B我ndeed声明有效。

来源

2011-03-01 00:59:51 markijbema

这真的不能证明任何东西。看到这[链接]（http://en.wikipedia.org/wiki/Proof_by_example） – rgbrgb 2012-02-01 07:36:48

它错过了'因为一切都是武断的，这成立'。这并不是一个例子，因为我没有选择一个具体的例子，而是一个任意的例子。 – markijbema 2012-02-01 10:36:10

大O符号和渐近

回答

相关问题