下界和紧界之间的区别？

在这个答案的参考下,什么是Theta(紧束缚)？

Omega是下限,很明白,算法可能需要的最短时间.我们知道Big-O代表上限,意味着算法可能需要的最长时间.但我不知道Theta.

1> Chris Bunch..：

---

大O是上限,而欧米茄是下限.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).

---

哦..现在,"紧束缚"一词对我来说非常自我解释.谢谢克里斯.愚蠢的我,也许我期待一些复杂的想法.:)

---

是的,有很多花哨的符号被抛出,但是一旦你掌握了它就不会太复杂.

---

这篇来自弗吉尼亚理工大学的免费文档通过实例解释了不同复杂度算法之间的性能差异,并简要解释了渐近分析:http://people.cs.vt.edu/shaffer/Book/C++3e20120102.pdf

2> Bill the Liz..：

---

Θ-符号(theta符号)称为紧束缚,因为它比O符号和Ω符号(ω符号)更精确.

如果我很懒,我可以说在排序数组上的二进制搜索是O(n ²),O(n ³)和O(2 ⁿ),在每种情况下我都是技术上正确的.这是因为O符号只指定了一个上限,而二进制搜索在所有这些函数的高端都是有限的,只是不是非常接近.这些懒惰的估计将毫无用处.

Θ-表示法通过组合 O符号和Ω 符号来解决这个问题.如果我说二进制搜索是Θ(log n),那么可以为您提供更精确的信息.它会告诉你,该算法是上界都面由给定的功能,所以它决不会比陈述显著更快或更慢.

---

`如果我很懒,我可以说在排序数组上的二进制搜索是O(n2),O(n3)和O(2n),在每种情况下我在技术上都是正确的 - 似乎大多数人在计算机世界里只是懒惰,因为每个人大多只谈论大O的复杂性.

3> Charlie Mart..：

---

如果你有一个 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).

在维基百科的文章是体面的,如果有点密集.

4> 小智..：

---

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

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

通常,O-notation用于上限复杂度.

---

渐近紧绑定(C ₁ G(N)≤F(N)≤Ç ₂ G(N))表示的函数的平均复杂度界限,具有结合的极限之间的值(上限和下限),其中c ₁和c ₂是常数.

---

@ArunAravind你能解释一下原因吗？