如何证明3n + 2log n = O(n)

Question

如何使用big-O的定义证明3n + 2log n = O(n)？

C应该是6,k是1,但我不知道如何找到它.非常感谢很多帮助.

Answer 1

要正式证明这个结果,你需要找到n ₀和c 的选择

对于任意的n≥Ñ ₀:3N + 2log N≤CN

要开始此操作,请注意,如果您有任何n≥1,则记录n <n.因此,如果你认为任何n≥1,你就有

3n + 2log n <3n + 2n = 5n

因此,如果你选择n ₀ = 1和c = 5,你就有了

对于任何n≥n0:3n + 2log n <3n + 2n =5n≤cn

因此3n + 2 log n = O(n).

更一般地说,当给出这样的问题时,尝试识别主导项(这里是n项)并试图找到n _0的一些选择,使得非显性项被主导项淹没.一旦你完成了这个,剩下要做的就是选择正确的常数c.

希望这可以帮助!