下界和紧束缚的区别？
参考这个答案 ，什么是Theta（紧束缚）？
欧米茄是一个algorithm可能花费的最小时间，它的下界是相当明白的。 我们知道Big-O是上限，意味着algorithm可能需要的最大时间。 但是我不知道Theta。
大O是上界，而欧米茄是下界。 Theta需要大O和Omega，所以这就是为什么它被称为一个紧密的界限 （它必须是上下限）。
例如，采用Omega(n log n)的algorithm至less需要n log n时间，但没有上限。 采用Theta(n log n)的algorithm是非常优先的，因为它至less需要n log n （Omega n log n） 且不超过 n log n （Big O n log n）。
Θ-符号 （θ符号）被称为紧束缚，因为它比O-符号和Ω-符号（欧米茄符号）更精确。
如果我懒惰，我可以说sorting后的数组的二进制search是O（n 2 ），O（n 3 ）和O（2 n ），而且在任何情况下，技术上都是正确的。 这是因为O-notation只指定了一个上限 ，而二进制search被所有这些函数限制在较高的一边，只是不是非常接近。 这些懒惰的估计是没用的 。
Θ-符号通过组合 O-notation和Ω-notation来解决这个问题。 如果我说二分查找是Θ（log n），那么给你更精确的信息。 它告诉你，algorithm在给定函数的两边都是有界的，所以它不会明显比声明更快或更慢。
如果你的东西是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）） 。
维基百科的文章是体面的，如果有点密集。
渐近上界意味着给定的algorithm在最大时间内执行，取决于input的数量。
我们以一个sortingalgorithm为例。 如果一个数组的所有元素都是按降序排列的，那么对它们进行sorting就需要O(n)的运行时间，performance出上限的复杂度。 如果数组已经sorting，则值为O(1) 。
通常， O-notation用于上限复杂度。
渐近紧束缚 （c 1 g（n）≤f（n）≤c 2 g（n））表示函数的平均束缚复杂度，其值在界限（上界和下界）之间，其中c 1和c 2是常数。
最短时间和最长时间短语在这里有点误导。 当我们谈论大O符号时，并不是我们感兴趣的实际时间，而是当我们的input量变大时，时间是如何增加的。 这通常是我们谈论的平均或最坏的情况，而不是最好的情况 ，这对解决我们的问题通常是没有意义的。
以另一个问题的接受答案中的数组search为例。 在大小为n的列表中查找特定数字所需的时间平均为n / 2 * some_constant。 如果你把它看作一个函数f(n) = n/2*some_constant ，那么它的增长速度不会快于g(n) = n ，就像查理给出的那样。 而且，它也不会比g(n)慢。 因此， g(n)实际上既是Big-O表示法中f(n)的上界和下界，线性search的复杂度正好是 n ，意味着它是Theta（n）。
在这方面，对另一个问题的接受答案的解释是不完全正确的，它声称O（n）是上界的，因为algorithm可以在一些input的恒定时间内运行（这是我上面提到的最好的情况 ，这实际上并不是我们想知道的关于运行时间）。
如果我是懒惰的，我可以说sorting后的数组上的二进制search是O（n2），O（n3）和O（2n），在技术上我都是正确的。
我们可以使用o-notation（“little-oh”）来表示不是渐近紧的上界。 大哦，小哦，是相似的。 但是，大哦可能用来定义渐近紧上界。
之间的基本区别
大段引用
渐近上界和渐近严格Asym.perperbound意味着一个给定的algorithm，它可以根据input的数量以最大的时间执行，例如在sortingalgorithm中，如果所有的数组（n）元素都是递减的，然后递增，将花费O（n）的运行时间来显示上限复杂度，但是如果它们已经被sorting，那么将花费欧姆（1）。因此，我们通常使用“O”符号来表示上限复杂度。
ASYM。 （c1g（n）<= f（n）<= c2g（n））表示严格界限，使得函数具有两个界限（上界和下界）之间的值，给出平均情况。
