algorithm - 时间复杂度和 Big-O 符号特定问题

Question

我过去考试中的一个问题是多项选择题:

Choose the FALSE statement: 7(log n) + 5n + n(log log n) + 3n(ln n) is

A. O(n^2)
B. Ω(n^2)
C. O(n log^2 n)
D. Ω(n)
E. Θ(n log n)

首先我得出结论，算法的运行时间必须是 Θ(n log n)，这排除了选项 E。然后我得出结论，选项 B，Ω(n^2)，是错误的，因为我知道Θ(n log n) 小于 Θ(n^2)，因此 Ω(n^2) 不可能成立。所以我认为 B 会是答案。

但我也意识到 C 也不成立，因为 Θ(n log n) 比 Θ(n log^2 n) 的运行时间更长。但不可能有 2 个答案是正确的。

那么哪个是正确的:是 B 吗？还是C？还是两者都不是？我很困惑。 :S

Answer 1

错误的陈述是omega(n^2)。
恰好是theta(nlogn)(因为3n(ln n))是“最高”，就是theta(nlogn)。
omega(n^2) 说它并不比 n^2 复杂度好，这在这里是错误的。

补充:在您的示例中，以下内容为真:
7(log n) < 5n < n(log log n) < 3n(ln n)
7logn = theta(logn), 5n = theta(n), n(loglogn) = theta (nloglog(n)), 3nln(n) = theta(nlogn)
如前所述，(nlogn) 是最高的，因此:
7(log n) + 5n + n(log log n) + 3n(ln n) = theta(nlogn)
并且都是 o(n^2)(这里故意小 o)，所以 Omega(n^2) 是错误的陈述。

编辑:澄清并添加我在评论中写的内容:
选项 C 为真，因为 O(nlogn) < O(nlog^2(n))。数学上:
nlog^2(n) = n*log(n)*log(n) > n*log(n) 对于每个 n>2。
示例:对于 n=1,000,000:nlogn = 1,000,000*20 = 20,000,000
而 n*log^2(n) = 1,000,000*20*20=400,000,000。