下界和紧密界的区别是什么？

Question

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

Omega是下界，也就是算法可能花费的最短时间，我们都比较理解。而我们知道Big-O是上界，表示算法可能花费的最长时间。但是我对Theta一无所知。

Theta（紧密界）描述了算法的确切复杂度，即算法运行时间的上限和下限相同。与Big-O类似，Theta也提供了关于算法的渐进分析，但它更加严格。如要得到Theta，需要同时找到算法的上界和下界。

- Adeel Ansari

Answer 1

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 O n log n）。

- Chris Bunch

---

哦，现在“紧密界”这个术语对我来说相当容易理解了。谢谢Chris。可能是我太傻了，以至于我本来期待的是某种复杂的概念。 :) - Adeel Ansari

没错，有很多花哨的符号在其中，但一旦你掌握了它，它并不太复杂。 - Chris Bunch

这份来自弗吉尼亚理工大学的免费文档通过例子说明了不同复杂度算法之间性能的差异，并简要介绍了渐近分析。链接为：http://people.cs.vt.edu/shaffer/Book/C++3e20120102.pdf - Alan

“算法的时间复杂度为Theta(n log n)是非常优越的，因为它至少需要n log n（Omega n log n）的时间，但不会超过n log n（Big O n log n）。”这句话的意思是，算法的确切复杂度是至少为Omega(nlogn)，最多为BigO(nlogn)吗？ - Nikhil Verma

@NikhilVerma，_bill-the-lizard_下面的回答没有解决你的问题吗？ - Nikos Alexandris

简单来说，我们可以称： 上界（Big(O)）为最坏情况吗？ 紧密界限为平均情况吗？ 下界（Omega）为最佳情况吗？ - Revanth

Answer 2

Θ-符号（theta 符号）因比O-符号和Ω-符号更精确而被称为紧界符号。

如果我懒一点，那么我可以说对于已排序数组的二分查找复杂度为O(n²)、O(n³)和O(2ⁿ)，而在每种情况下我都是准确的。这是因为O-符号只指定了一个上界，而二分搜索在高端受到所有这些函数的限制，但并不十分严格。这种懒惰的估计是无用的。

Θ-符号通过结合 O-符号 和 Ω-符号来解决这个问题。如果我说二分查找的复杂度是Θ(log n)，那么这会给你更精确的信息。它告诉你该算法在两个方向上被给定函数所限制，因此它永远不会比所述的速度快或慢很多。

- Bill the Lizard

---

如果我懒得话，我可以说对于一个已排序的数组进行二分查找的时间复杂度是O(n2)，O(n3)，以及O(2n)，而在每种情况下我都是技术上正确的。看起来计算机领域的大多数人都很懒，因为他们大多只关注算法的大O复杂度。 - RBT

如果我懒的话，我可以说在已排序数组上进行二分查找是O(n2)，O(n3)和O(2n)，而且在每种情况下我都是技术上正确的。对于那种不是渐近紧小o符号的函数，使用的是小o符号。例如：2n^2 = O(n^2)是渐近紧的，但2n = O(n^2)不是。阅读更多：https://dev59.com/PXM_5IYBdhLWcg3wdzDz - Dragos Strugar

如果是这样，为什么我们更经常使用大O符号呢？是因为手动计算更容易吗？ - NoName

Answer 3

如果您有一个时间复杂度为 O(f(n)) 的东西，那意味着存在 k, g(n)，使得 f(n) ≤ k g(n)。

如果您有一个时间复杂度为 Ω(f(n)) 的东西，那意味着存在 k, g(n)，使得 f(n) ≥ k g(n)。

如果您有一个同时满足 O(f(n)) 和 Ω(f(n)) 的东西，那它的时间复杂度为 Θ(f(n))。

维基百科文章相当不错，虽然有点难懂。

- Charlie Martin

---

现在正在阅读巴赫曼-朗道符号家族。谢谢Charlie，我之前去过那里，但没有深入了解它的长度。 - Adeel Ansari

嘿，时不时地刷新博士综合考试知识还是很有好处的。 - Charlie Martin

请注意，Landau的大O符号并不仅限于算法复杂度。 - Charlie Martin

这看起来不对。第一行应该写成“如果你有一个O(g(n))的东西”，也就是说，用g代替f，其余部分可以保持不变。第二行也是同样的情况：应该是“如果你有一个Ω(g(n))的东西”。你能再检查一下吗？ - Fabio says Reinstate Monica

整个话题非常混乱，即使是有信誉的人也可能会搞错:D 开玩笑，开个玩笑，有人需要修正这个答案。这会让人们感到困惑（我非常困惑）。 - Rad

你是不是想说：“如果你有 f(n) = O(g(n))，那么存在一个 k 和 g(n)，使得 f(n) ≤ k g(n)”？ - Prid

Answer 4

渐近上界意味着给定算法在最大输入数量下执行的时间。以排序算法为例，如果数组中所有元素都是按降序排列，则对它们进行排序需要运行时间为 O(n)，表现为上界复杂度。如果数组已经排序，该值将为 O(1)。通常使用O-符号表示上界复杂度。

渐近紧密界限 (c1g(n) ≤ f(n) ≤ c2g(n)) 显示函数的平均界限复杂性，在界限限制（上界和下界）之间具有一个值，其中c1和c2是常数。

- sameenu

---

如果数组已排序，则边界仍将为O(n)。 - Arun Aravind

@ArunAravind 你能解释一下为什么吗？ - nbro

Answer 5

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

以另一个问题中被接受的答案中的数组搜索为例。在大小为n的列表中查找特定数字所需的时间在平均情况下为n/2 * some_constant。如果将其视为函数f(n) = n/2*some_constant，则它的增长速度不会超过g(n) = n，如Charlie所述。它的增长速度也不会比g(n)慢。因此，在大O符号中，g(n)实际上既是f(n)的上界，也是下界，因此线性搜索的复杂度实际上是n，即Theta(n)。

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

- PolyThinker

---

那么，我们可以说Ω是最好的情况，而O是最坏的情况吗？我们是否应该分别将其替换为最佳情况和最差情况这些术语？ - Adeel Ansari

任何问题的最佳情况是O(1)吗？ - Zach Langley

@Adeel，不，Theta和O都可以指平均情况或最坏情况。 @Zach，嗯，不完全是。感谢你指出来。 - PolyThinker

Answer 6

如果我很懒，我可以说在已排序数组上进行二分查找的时间复杂度是O(n2)，O(n3)和O(2n)，而且在每种情况下我都是技术上正确的。

我们可以使用o-notation（“小o”）来表示不是渐近紧密的上界。大o符号和小o符号类似。但是，大o符号通常用于定义渐近紧密的上界。

- Finn is missing

Answer 7

精确的下界或 $\omega$ bfon f(n) 意味着渐近小于或等于 f(n) 的函数集合，即 U g(n)≤ cf(n)，对于所有的 un≥n 和某些 c、n' $\in$ $\Bbb{N}$。

而上界或 $\mathit{O}$ 对于 f(n) 意味着渐近大于或等于 f(n) 的函数集合，数学上表示为：

g(n)≥cf(n)，对于所有的 n≥n' 和某些 c、n' $\in$ $\Bbb{N}$。

现在 $\Theta$ 是上述两个的交集。

$\theta $

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

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

- R29nb2xlIFBp

Answer 8

基本区别在于

块引用

渐近上界和渐近紧密性之间的区别。渐近上界意味着给定算法可以根据输入数量执行最长时间，例如，在排序算法中，如果所有数组（n）元素按降序排列，则将它们升序排列需要运行时间为O（n），这显示了上限复杂度，但如果它们已经排序，则只需ohm（1）即可。因此，我们通常使用“O”符号表示上限复杂度。

渐近紧密性界限显示例如（c1g（n）<= f（n）<= c2g（n））显示两个边界（上限和下限）之间的函数值，给出平均情况。

- BOBBY Z

---

如果你的答案没有为已被接受的答案添加任何内容，那么你不应该回答旧问题。 - alestanis