114

参考这个答案，什么是 Theta（紧界）？

Omega 是下限，很容易理解，是算法可能花费的最短时间。我们知道 Big-O 是上限，表示算法可能花费的最长时间。但我对Theta一无所知。

4

8 回答 8

175

Big O是上限，而Omega是下限。Theta需要 Big O 和 Omega，所以这就是为什么它被称为紧密界限（它必须同时是上限和下限）。

例如，一个算法Omega(n log n)至少需要n log n时间，但没有上限。算法采用Theta(n log n)是非常优先的，因为它至少 n log n需要(Omega n log n)且不超过 n log n(Big On n log n)。

于 2009-01-21T04:26:22.670 回答
126

Θ 表示法（theta 表示法）被称为紧界，因为它比O 表示法和Ω 表示法（omega 表示法）更精确。

如果我是懒惰的，我可以说对排序数组的二分查找是 O(n 2 )、O(n 3 ) 和 O(2 n )，并且在每种情况下我在技术上都是正确的。那是因为 O-notation 只指定了一个上限，而二分搜索在所有这些函数的上限上都有界，只是不是很接近。这些懒惰的估计是没有用的。

Θ-notation 通过结合O-notation 和 Ω- notation 解决了这个问题。如果我说二分搜索是 Θ(log n)，那会为您提供更精确的信息。它告诉您算法在给定函数的两侧都有边界，因此它永远不会比规定的更快或更慢。

于 2009-01-22T23:32:08.097 回答
19

如果你有 O(f(n))的东西，这意味着有k，g(n)使得f(n) ≤ kg(n)。

如果你有 Ω(f(n))的东西，这意味着有k，g(n)使得f(n) ≥ kg(n)。

如果你有一个O(f(n)) 和 Ω(f(n))的东西，那么它就是Θ(f(n)。

维基百科的文章是不错的，如果有点密集。

于 2009-01-21T04:30:14.953 回答
5

渐近上限意味着给定算法在最长时间内执行，具体取决于输入的数量。

我们以排序算法为例。如果一个数组的所有元素都按降序排列，那么对它们进行排序，运行时间为O(n)，显示了上限复杂度。如果数组已经排序，则值为O(1).

通常，O-notation用于上限复杂度。

渐近紧密界(c 1 g(n) ≤ f(n) ≤ c 2 g(n)) 显示函数的平均界复杂度，其值介于界限（上限和下限）之间，其中 c 1和c 2是常数。

于 2012-11-18T16:06:57.020 回答
4

短语最小时间和最大时间在这里有点误导。当我们谈论大 O 符号时，我们感兴趣的不是实际时间，而是当我们的输入大小变大时时间如何增加。这通常是我们谈论的平均或最坏情况时间，而不是最佳情况，这通常对解决我们的问题没有意义。

以另一个问题的已接受答案中的数组搜索为例。在大小为 n 的列表中找到特定数字所需的时间平均为 n/2 * some_constant。如果你把它当作一个函数f(n) = n/2*some_constant，它的增长速度不会快于g(n) = n，在查理给出的意义上。此外，它的增长速度不会比g(n)两者都慢。因此，g(n)实际上是 Big-O 表示法的上限和下限f(n)，所以线性搜索的复杂度正好是 n，这意味着它是 Theta(n)。

在这方面，另一个问题的已接受答案中的解释并不完全正确，它声称 O(n) 是上限，因为对于某些输入，算法可以在恒定时间内运行（这是我上面提到的最好的情况，这并不是我们真正想知道的关于运行时间的信息）。

于 2009-01-21T04:45:11.400 回答
0

如果我是懒惰的，我可以说对排序数组的二分查找是 O(n2)、O(n3) 和 O(2n)，并且在每种情况下我在技术上都是正确的。

我们可以使用 o-notation（“little-oh”）来表示一个不是渐近紧的上界。big-oh 和 little-oh 都是相似的。但是，big-oh 很可能用于定义渐近紧上界。

于 2017-10-28T20:03:28.353 回答
0

确切地说，下界或 $\omega $ bfon f(n) 表示渐近小于或等于 f(n) 的函数集，即 U g(n)≤ cf(n) $\for all $`un≥ n ' 对于某些 c, n' $\in $ $\Bbb{N}$

f(n) 的上界或 $\mathit{O}$ 表示渐近大于或等于 f(n) 的函数集，从数学上讲，

$ g(n)\ge cf(n) \for all n\ge n' $ ，对于一些 c,n' $\in $ $\Bbb{N}$。

现在 $\Theta $ 是上面写的两个的交集

$\theta $

就像如果一个算法就像“正是 $\Omega\left( f(n)\right$ ”，那么最好说它是 $\Theta\left(f(n)\right)$ 。

或者，我们也可以说它给$ \omega $了我们最低限度的实际速度。

于 2019-06-06T15:34:43.087 回答
-1

之间的基本区别

块引用

渐近上界和渐近紧密 Asym.upperbound 表示一个给定的算法，它可以根据输入的数量在最长时间内执行，例如，在排序算法中，如果所有数组 (n) 元素都按降序排列，则将其升序将花费 O(n) 的运行时间，这显示了上限复杂度，但如果它们已经排序，那么它将花费 ohm(1)。所以我们通常使用“O”表示法来表示上限复杂度。

不对称。紧密边界显示例如（c1g（n）<=f（n）<=c2g（n））显示紧密边界限制，使得函数具有两个边界（上限和下限）之间的值，给出平均情况。

于 2012-05-18T07:29:36.293 回答