如何证明Big O符号

本文介绍了如何证明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).