我过去考试中的一个问题是多项选择题:
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
最佳答案
错误的陈述是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
。
关于algorithm - 时间复杂度和 Big-O 符号特定问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6450968/