若T(n)=θ(n^2) = T(n)=0(n)？

Question

如果T(n) =θ(n^2) = O(n^2) =Ω(n^2)等于：T(n)=O(n^3)？

寻找答案但只有一次：

O(n2)，也是O(n2log n)，O(n3)，O(n4)等，但不是O(n)

然后：

大O表示算法执行的步骤不会超过给定表达式(n^2)。

Answer 1

是的，这是真的。

如果T(n) = θ(n^2)，

然后

T(n) = O(n^k)，其中k>=2

T(n) = Ω(n^k)，其中k<=2

注意，如果T(n) = θ(n^2)，T(n) != θ(n^3) as T(n) = θ(n^2)意味着n的增长率渐近等于n^2的增长率。

如果T(n) = O(n^2)，则T(n) = O(n^3)，因为T(n) = O(g(n))是指T(n)的增长率渐近小于或等于g(n)的增长率。因此，如果T(n)的增长率小于n^2的增长率，那么它将明显地小于n^3的增长率。