有人知道如何进行这样的计算吗?
O(n^2) + THETA(n) + OMEGA(n^3) = ?
或者
O(n^2) * THETA(n) * OMEGA(n^3) = ?
通常情况下,如何添加和乘以不同的渐近符号?
有人知道如何进行这样的计算吗?
O(n^2) + THETA(n) + OMEGA(n^3) = ?
或者
O(n^2) * THETA(n) * OMEGA(n^3) = ?
通常情况下,如何添加和乘以不同的渐近符号?
O
表示一个上限;
Ω
表示一个下限;
Θ
表示一个渐进上界;
维基百科有一张好图来解释这些概念。
因此,它们通常不可比较。
对于第一个情况,
O(n^2) + Θ(n) + Ω(n^3)
O
。第一个术语告诉我们 O(n^2)
,第二个术语告诉我们 O(n)
。仅基于这两个,我们知道我们有一个上限为 O(n^2)
。然而,第三个术语对于上限没有任何信息!因此,我们真的无法得出关于 O
的任何结论。O
和 Θ
只提供有关 O
的信息,Ω
和 Θ
只提供有关 Ω
的信息。这是因为 Θ(g(n))
意味着 O(g(n))
和 Ω(g(n))
,所以我们可以根据给定的分析将 Θ
转换为适用于 O
或 Ω
中的任何一个。O
和 Ω
,都会让你感到茫然,因为 O
和 Ω
都不意味着关于另一个的任何信息。您不能。假设您知道a > 0
和b < 10
。那么您对a+b
没有任何信息。它可以是任何值。
对于函数,大O符号和大Ω符号的作用类似。
虽然我上面的答案对于一般函数和界限是正确的,但在计算机科学中,我们通常只考虑正函数。因此在你的第一个例子中,我们有:
O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)
这源于函数都是正数的假设。也就是说,所有函数都是 Omega(1)
。