复杂性分析中对 Theta 符号的说明。 Θ(g)
Clarification for Theta notation in complexity analysis. Θ(g)
当我们谈论 Θ(g) 时，我们指的是 g(n) 的最高阶项还是指 g(n) 的原样？
例如，如果 f(n) = n3。而g(n)=1000n3+n Θ(g) 是 Θ(1000n3+n) 还是 Θ(n3)？
在这种情况下，我们可以说 f(n) 是 Θ(g) 吗？
Θ(g) 产生 组 的函数，它们的复杂度都相同 class。 Θ(1000n3+n) 等于 Θ(n3 ) 因为这两个结果是同一个集合。
为了简单起见，通常会删除不重要的项和乘法常数。低阶加法项不会改变复杂度，任何乘数也不会，因此没有理由将它们写出来。
因为 Θ(g) 是一个集合，你会说 f(n） ＆在; Θ(g).
注意：许多 CS 教师、教科书和其他资源使用不精确的符号来混淆水域。很多人说 f(n)=n3 是 O(n3)，而不是f(n)=n3 在 O(n3)。他们在表示 ∈ 时使用 =。
theta(g(n)) 介于 O(g(n)) 和 omega(g(n)) 之间
如果 g(n) = 1000n^3 + n
首先让我们找到 O(g(n)) 上限
它可能是 n^3、n^4、n^5，但我们选择最接近的 O(n^3)。
O(n^3) 是有效的，因为我们可以找到一个常数 c 使得对于 n 的某个值
1000n^3 + n < c.n^3
其次让我们看看下限的 omega(g(n))
欧米茄说 f(n) > c.g(n)
我们可以找到一个常数 c 使得
1000.n^3 + n > c.n^3
现在我们有上界 O(n^3) 和下界 omega(n^3)。
因此我们有使用相同函数限制上限和下限的 theta。
根据规则：如果 f(n) = O(g(n)) 且 f(n) = omega(g(n)) 因此 f(n) = theta(g(n))
1000.n^3 + n = theta(n^3)
当我们谈论 Θ(g) 时，我们指的是 g(n) 的最高阶项还是指 g(n) 的原样？
例如，如果 f(n) = n3。而g(n)=1000n3+n Θ(g) 是 Θ(1000n3+n) 还是 Θ(n3)？
在这种情况下，我们可以说 f(n) 是 Θ(g) 吗？
Θ(g) 产生 组 的函数，它们的复杂度都相同 class。 Θ(1000n3+n) 等于 Θ(n3 ) 因为这两个结果是同一个集合。
为了简单起见，通常会删除不重要的项和乘法常数。低阶加法项不会改变复杂度，任何乘数也不会，因此没有理由将它们写出来。
因为 Θ(g) 是一个集合，你会说 f(n） ＆在; Θ(g).
注意：许多 CS 教师、教科书和其他资源使用不精确的符号来混淆水域。很多人说 f(n)=n3 是 O(n3)，而不是f(n)=n3 在 O(n3)。他们在表示 ∈ 时使用 =。
theta(g(n)) 介于 O(g(n)) 和 omega(g(n)) 之间 如果 g(n) = 1000n^3 + n
首先让我们找到 O(g(n)) 上限 它可能是 n^3、n^4、n^5，但我们选择最接近的 O(n^3)。
O(n^3) 是有效的，因为我们可以找到一个常数 c 使得对于 n 的某个值 1000n^3 + n < c.n^3
其次让我们看看下限的 omega(g(n)) 欧米茄说 f(n) > c.g(n) 我们可以找到一个常数 c 使得 1000.n^3 + n > c.n^3
现在我们有上界 O(n^3) 和下界 omega(n^3)。 因此我们有使用相同函数限制上限和下限的 theta。
根据规则：如果 f(n) = O(g(n)) 且 f(n) = omega(g(n)) 因此 f(n) = theta(g(n))
1000.n^3 + n = theta(n^3)