复杂度 类 个例子
Complexity classes examples
我想知道我对以下陈述的回答是否确实正确：
3(n^3) + 5(n^2) + 25n + 10 = BigOmega(n^3) -> T
->以等于或更慢的速度增长
3(n^3) + 5(n^2) + 25n + 10 = Theta(n^3) -> T
-增长速度正好等于
3(n^3) + 5(n^2) + 25n + 10 = BigO(n^3) -> T
- 增长速度等于或更快
谢谢！！！
O 符号的正式定义是：
f(n) = O(g(n)) means that there exists some constant c and n0 that
f(n) <= c*g(n) for n >= n0.
f(n) = Ω(g(n)) means that there exists some constant c and n0 that
f(n) >= c*g(n) for n >= n0.
f(n) = Θ(g(n)) means that there exists some constants c1 and c2 and n0
that f(n) >= c1*g(n) and f(n) <= c2*g(n) for n >= n0.
O 的证明：
3(n^3) + 5(n^2) + 25n + 10 < 3*n^3 + n^3 + n^3 = 5*n^3
您可以看到对于 n >= 10 这个公式是正确的。
所以存在c = 5和n0 = 10，所以是O(n^3).
Ω 的证明：
3(n^3) + 5(n^2) + 25n + 10 > 3*n^3
所以c = 3和n0 = 1，因此是Ω(n^3)。
因为 O 和 Ω 都适用，所以 Θ 的第 3 个陈述也为真。
我想知道我对以下陈述的回答是否确实正确：
3(n^3) + 5(n^2) + 25n + 10 = BigOmega(n^3) -> T ->以等于或更慢的速度增长
3(n^3) + 5(n^2) + 25n + 10 = Theta(n^3) -> T -增长速度正好等于
3(n^3) + 5(n^2) + 25n + 10 = BigO(n^3) -> T - 增长速度等于或更快
谢谢！！！
O 符号的正式定义是：
f(n) = O(g(n)) means that there exists some constant c and n0 that f(n) <= c*g(n) for n >= n0.
f(n) = Ω(g(n)) means that there exists some constant c and n0 that f(n) >= c*g(n) for n >= n0.
f(n) = Θ(g(n)) means that there exists some constants c1 and c2 and n0 that f(n) >= c1*g(n) and f(n) <= c2*g(n) for n >= n0.
O 的证明：
3(n^3) + 5(n^2) + 25n + 10 < 3*n^3 + n^3 + n^3 = 5*n^3
您可以看到对于 n >= 10 这个公式是正确的。
所以存在c = 5和n0 = 10，所以是O(n^3).
Ω 的证明：
3(n^3) + 5(n^2) + 25n + 10 > 3*n^3
所以c = 3和n0 = 1，因此是Ω(n^3)。
因为 O 和 Ω 都适用，所以 Θ 的第 3 个陈述也为真。