algorithm - 函数的大 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)。