如何证明Big O符号 [英] How to prove Big O notation

问题描述

在我的算法课程中，我们正在讨论大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符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！