函数的大 O 阶

Question

我正在做一些关于大 O 表示法的练习题，遇到了这个问题。函数 () = ^2 + log2() + log2() 的大 O 顺序是什么。展示你的作品。

我的答案是 O(n^2) 因为它是度数最高的一项。但是，我不确定如何显示它。我说必须像这样证明是对的吗 -> f(n) 是 O(n^2) 的一个元素。到目前为止，我只做了像 n^2 + 2n + 1 这样的问题，我必须找到 c 和 k 值。我不太确定该怎么做。任何人都可以帮我吗？

谢谢

Answer 1

让c := 3和k := 1。让n >= k，即n >= 1。我们得到

f( n ) = n*n + n*log(n) + log(n)  // definition of f
      <= n*n + n*n      + n      // n >= k = 1
      <= n*n + n*n      + n*n    // n >= k = 1
       = 3*n*n
       = c*n*n

表示f \in O(n*n).

函数的大 O 阶

Big O order of a function

algorithm

big-o

analysis