What is the difference between lower bound and tight bound?

大 O 是上界，而 欧米茄是下界。西塔既需要大 O 又需要欧米茄，所以这就是为什么它被称为 束缚得很紧(它必须是上界和下界)。

例如，采用 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) ，因此具有很大的优先性。

如果你有 O (f (n))这意味着有 K，G (n)这样的 f(n) & le; k g(n)。

如果你有 (f (n))这意味着有 K，G (n)这样的 F (n) & ge; K g (n)。

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

维基百科文章还不错，只是密度有点大。

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

在另一个问题的可接受答案中使用数组搜索作为示例。在大小为 n 的列表中找到一个特定数字所需的时间平均为 n/2 * some _ Constant。如果你把它当作一个函数 f(n) = n/2*some_constant，它的增长速度不会快于 g(n) = n，在查理给出的意义上。此外，它的增长也不慢于 g(n)。因此，g(n)实际上既是大 O 符号 f(n)的上界，也是下界，所以线性搜索的复杂度是 没错 N，这意味着它是 Θ (n)。

在这方面，对另一个问题的解释是不完全正确的，它声称 O (n)是上界，因为算法可以在固定的时间内运行一些输入(这是我上面提到的 最好的情况，这不是我们真正想知道的运行时间)。

- 符号 (Theta 符号)被称为紧界，因为它比 O 符号和 & Omega;-符号(omega 符号)更精确。

如果我懒惰的话，我可以说排序数组上的二进制搜索是 O (n²)、 O (n³)和 O (2^N) ，在任何情况下，我在技术上都是正确的。这是因为 O 符号只指定 上界，而二进制搜索被所有这些函数限制在较高的范围内，只是不是非常接近。这些懒惰的估计将是 没用。

Θ-notation solves this problem by 结合 O-notation and Ω-notation. If I say that binary search is Θ(log n), that gives you more precise information. It tells you that the algorithm is bounded on both sides by the given function, so it will never be significantly faster or slower than stated.

两者之间的基本区别

引用原文

渐近上界和渐近紧 上界是指一个给定的算法，它可以根据输入的数量以最大的时间执行，例如在排序算法中，如果所有的数组(n)元素都是降序的，那么对于升序，它将需要一个 O (n)的运行时间，这显示了上界的复杂性，但是如果它们已经排序，那么它将需要欧姆(1)。所以我们通常用“ O”表示上限复杂度。

Asym. tightbound bound shows the for eg(c1g(n)<=f(n)<=c2g(n)) shows the tight bound limit such that the function have the value in between two bound (upper bound and lower bound),giving the average case.

渐近上界 意味着给定的算法在最大时间量内执行，这取决于输入的数量。

Let's take a sorting algorithm as an example. If all the elements of an array are in descending order, then to sort them, it will take a running time of O(n), showing upper bound complexity. If the array is already sorted, the value will be O(1).

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

渐近紧界 (c₁g (n) & # x2264; f (n) & # x2264; c₂g (n))显示函数的平均绑定复杂度，具有界限(上界和下界)之间的值，其中 c₁和 c₂是常数。

If I were lazy, I could say that binary search on a sorted array is O (n2) ，O (n3) ，和 O (2n) ，从技术上讲，我在每个 案件。

我们可以使用 o 符号(“ little-oh”)来表示不是渐近紧的上界。大哦和小哦都很相似。但是，big-oh 可能用于定义渐近紧上界。

正是下界或 $omega $bfon f (n)指渐近小于或等于 f (n)的函数集，即 U G (n)≤ cf (n) $for all $‘ un ≥ n’ 对于一些 c，n’$in $bb { N } $

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

$g (n) ge cf (n) for all n ge n’$，for some c，n’$in $$bb { N } $。

现在 $Θ $是上面写的两个的交叉点

$\theta $

比如，如果一个算法类似于“恰好 $Omega left (f (n) right $”，那么最好说它是 $Theta left (f (n) right) $。

Or , we can say also that it give us the actual speed where $ Ω $ 给了我们最低的限制