大O符号证明 [英] Big O notation proving

问题描述

在我的算法类中，我们讨论大O符号&我陷入证明这个示例问题

In my algorithm class we are discussing big O notation & I am stuck proving this example problem

验证f（n）= 3n lg n + 10n + lg n + 20 = O（n lg n）

Prove 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).

这篇关于大O符号证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！