这可能是一个微不足道的/数学概念，我似乎无法理解。那么如果某个算法的处理时间 T(n) 既是 Ω(n) 又是 O(n^3)，我如何证明 T(n) 是 Θ(n^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) 中。所以我们不能从两个弱约束中推断出强约束。因此，该说法是错误的。
关于algorithm - 大O/时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25198368/