大 O 表示法和渐近学
让
d
p(n) = Σ ai n^i
i=0
哪里广告> 0 是 n 的 d 次多项式，设 k 为常数。使用渐近符号的定义来证明以下性质。
a) if k >= d, then p(n) = O(n^k)
还有另外 4 个对应于 Omega、theta、小 o 和小 omega 属性，但如果我能知道如何开始，我可以自己找出其他属性。
Let
d
p(n) = Σ ai n^i
i=0
where ad > 0 is a degree-d polynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.
a) if k >= d, then p(n) = O(n^k)
There are also 4 more correspoding to the Omega, theta, small o and small omega properties but if I could get an idea on how to start I can figure the other ones out on my own.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这很简单。在这里查看 Big O 表示法的正式定义： http://en.wikipedia.org/wiki/Big_o_notation #Formal_definition，尤其是该部分末尾的公式，
limsup。你想要证明的是，当 n 达到（正）无穷大时 p(n)/n^k 的极限是一个实数。如果k> d、极限为零。如果k=d，则极限为a_d。为什么？因为它是 n^k 上的简单多项式（d 阶），这也是 n^k 上的多项式（k 阶）。查看多项式极限的计算。It's pretty simple. Look at the Big O Notation formal definition here: http://en.wikipedia.org/wiki/Big_o_notation#Formal_definition, especially at the formula at the end of the section,
limsup. What you're trying to prove is that the limit of p(n)/n^k as n goes to (positive) infinity is a real number. If k > d, the limit is zero. If k=d, then the limit is a_d. Why? Because it's a simple polynomial (of an order of d) over n^k, which is also a polynomial (of an order of k). Look at calculating limits of polynomials.如果这是真的，那么存在 N、A 和 B，使得：
对于所有 n >= N
存在这样的 N、A 和 B，例如：
如果您认为这足够有洞察力，您可以保留它，或者实际上通过归纳证明 N、A 和 B 的选择确实使该陈述有效。
If this is true, then there exist N, A and B such that:
for all n >= N
Such N, A and B exist, take for instance:
You can leave it at that, if you think that's insightful enough, or actually proof by induction that this choice of N, A and B indeed makes the statement valid.