本文介绍了如何证明Big O符号的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
在我的算法课程中,我们正在讨论大O表示法,但我坚持证明了这个示例问题:
In my algorithm class we are discussing big O notation and I am stuck proving this example problem:
证明f(n) = 3n lg n + 10n + lg n + 20 = O(n lg n)
详细信息将不胜感激.
推荐答案Big O表示法是渐近表示法,它全都与案件的近似值(最差,最佳和中级)有关. 在您的示例中,nlgn的增长速度快于n和lgn,而且常量值无关紧要,因此可以近似地忽略. 因此,其复杂度为O(nlgn).
Big O notation is an asymptotic notation and it's all about approximation of cases (worst, best and mid one). In your example, nlgn grows faster than both n and lgn, moreover constant values are not relevant and can be ignored in such an approximation. Because of that, it follows that the complexity is O(nlgn).
更多推荐
如何证明Big O符号
发布评论