algorithm - 为给定的运行时函数 f(n)=O(n^2)+nlog(n) 寻找可能的大 theta？

Question

Suppose that f(n) = O(n²) + n log n. Which of the following are possible?

1. f(n) = Θ(log n)
2. f(n) = Θ(n)
3. f(n) = Θ(n²)
4. f(n) = Θ(n³)

我对运行时函数有点困惑，因为包含了 O(n²)。我相信答案是 2 和 3，因为它们中的每一个都可以乘以一个数以达到 O(n²)。具体来说，Θ(n²)可以乘以1达到上限O(n²) , 并且 Θ(n) 可以乘以 n 达到上限 O(n²)。

我说的对吗？

Answer 1

我想唯一正确的答案是 (3)。 O(n^2) 是任何增长与 n^2 一样快或更慢的函数。 n log n = O(n^2)，所以 O(n^2) + n log n 是任何渐近“介于”n log 之间的函数n 和 n^2。在您问题中的所有 Theta 中，只有第三个符合这些界限。