This maybe a trivial/ mathematical concept that I cant seem to work my head around. So if the processing time T(n) of a certain algorithm is both Ω(n) and O(n^3), how can i prove that the T(n) is Θ(n^2) is either correct or not?
问问题
151 次
2 回答
2
让我们比较一下这三个符号的定义。
(1) Ω(n) 表示（对于足够大的 n）：n * k1 <= T(n)
(2) O(n^3) 意味着（对于足够大的 n）：n^3 * k2 >= T(n)
(3) Θ(n^2) 表示（对于足够大的 n）：k3 * n^2 <= T(n) <= k4 * n^2
给定 (3)，我们可以推断 T(n) 在 Ω(n) 和 O(n^3) 中，因为对于大数 n，n * k1 总是小于 n^2 * k2，如果我们只是提供 k1=k2（但也适用于 k1、k2 的任何其他组合）。这同样适用于 O(n^3)。
这基本上意味着 Θ(n^2) 是比 Ω(n) 和 O(n^3) 更强的约束。
但是，反过来也行不通。如果 (1) 和 (2) 成立，T(n) 也可能是 T(n)=n，这显然不在 Θ(n^2) 中。所以我们不能从两个弱约束中推断出强约束。因此，该说法是错误的。
于 2014-08-08T08:12:14.410 回答
1
于 2014-08-08T08:06:55.050 回答