我们已经讨论了渐近分析 和 最差、平均和最佳情况。渐近分析的主要思想是衡量算法的效率，这些算法不依赖于特定于机器的常数，并且不需要实现算法和比较程序所花费的时间。渐近符号是表示渐近分析算法时间复杂度的数学工具。以下3种渐近符号主要用于表示算法的时间复杂度。
1) Θ 表示法： theta 表示法从上方和下方界定一个函数，因此它定义了精确的渐近行为。
获得表达式的 Theta 符号的一种简单方法是删除低阶项并忽略前导常量。例如，请考虑以下表达式。
3n 3 + 6n 2 + 6000 = Θ(n 3 )
去掉低阶项总是没问题的，因为总会有一个数(n) 之后 Θ(n 3 ) 的值高于 Θ(n 2 )，而不管常数如何涉及。
对于给定的函数 g(n)，我们表示 Θ(g(n)) 跟随一组函数。
Θ(g(n)) = {f(n)：存在正常数 c1、c2 和 n0， 使得 0 <= c1*g(n) <= f(n) <= c2*g(n) 对于所有n >= n0}
上面的定义意味着，如果 f(n) 是 g(n) 的 theta，那么对于较大的 n 值 (n >= n0)。theta 的定义还要求 f(n) 对于大于 n0 的 n 值必须为非负值。
2) Big O 表示法： Big O 表示法定义了一个算法的上限，它只从上面限定一个函数。例如，考虑插入排序的情况。在最好的情况下需要线性时间，在最坏的情况下需要二次时间。我们可以有把握地说，插入排序的时间复杂度是 O(n^2)。请注意，O(n^2) 也涵盖线性时间。 如果我们使用 Θ 表示法来表示插入排序的时间复杂度，我们必须对最好和最坏情况使用两个语句：
- 插入排序的最坏情况时间复杂度是 Θ(n^2)。
- 插入排序的最佳情况时间复杂度是 Θ(n)。
当我们只有算法时间复杂度的上限时，大 O 表示法很有用。很多时候，我们只需查看算法就可以轻松找到上限。
O(g(n)) = { f(n)：存在正常数 c 和 n0，使得 0 <= f(n) <= c*g(n) 对于 所有 n >= n0}
3) Ω 表示法： 正如大 O 表示法提供函数的渐近上限一样，Ω 表示法提供渐近下界。
当我们对算法的时间复杂度有下限时，Ω 表示法会很有用。正如在前一篇文章中所讨论的，算法的最佳性能通常是没有用的，Omega 表示法是三者中使用最少的表示法。
对于给定的函数 g(n)，我们用 Ω(g(n)) 表示函数集。
Ω (g(n)) = {f(n)：存在正常数 c 和 n0，使得 0 <= c*g(n) <= f(n) 对于 所有 n >= n0}。
让我们在这里考虑相同的插入排序示例。插入排序的时间复杂度可以写成 Ω(n)，但这并不是关于插入排序的一个非常有用的信息，因为我们通常对最坏情况感兴趣，有时对平均情况感兴趣。
渐近符号的属性： 在我们已经完成了这三个符号的定义之后，让我们现在讨论这些符号的一些重要属性。 1. 一般属性：
如果 f(n) 是 O(g(n)) 那么 a*f(n) 也是 O(g(n)) ；其中 a 是常数。
示例： f(n) = 2n²+5 是 O(n²)
然后 7*f(n) = 7(2n²+5) = 14n²+35 也是 O(n²) 。
类似地，此属性同时满足 Θ 和 Ω 表示法。
我们可以说 如果 f(n) 是 Θ(g(n)) 那么 a*f(n) 也是 Θ(g(n)) ；其中 a 是常数。
如果 f(n) 是 Ω (g(n)) 那么 a*f(n) 也是 Ω (g(n)) ；其中 a 是常数。
2. 传递属性：
如果 f(n) 是 O(g(n)) 并且 g(n) 是 O(h(n)) 那么 f(n) = O(h(n)) 。
示例：如果 f(n) = n，g(n) = n² 且 h(n)=n³
n 为 O(n²) 且 n² 为 O(n³)，
则 n 为 O(n³)类似地，此属性同时满足 Θ 和 Ω 表示法。
我们可以说
如果 f(n) 是 Θ(g(n)) 并且 g(n) 是 Θ(h(n)) 那么 f(n) = Θ(h(n)) 。
如果 f(n) 是 Ω (g(n)) 并且 g(n) 是 Ω (h(n)) 那么 f(n) = Ω (h(n))
3. 反身属性：
自反属性在传递之后总是很容易理解的。
如果给定 f(n)，则 f(n) 为 O(f(n))。由于*f(n) 的最大值将是 f(n) 本身！*
因此 x = f(n) 和 y = O(f(n) 总是以自反关系联系在一起。
例子： f(n) = n² ; O(n²) 即 O(f(n))
类似地，此属性同时满足 Θ 和 Ω 表示法。
我们可以说：
如果给定 f(n)，则 f(n) 是 Θ(f(n))。
如果给定 f(n)，则 f(n) 是 Ω (f(n))。
4. 对称性：
如果 f(n) 是 Θ(g(n)) 则 g(n) 是 Θ(f(n)) 。
示例：f(n) = n² 和 g(n) = n²
然后 f(n) = Θ(n²) 和 g(n) = Θ(n²)
此性质仅满足 Θ 表示法。
5. 转置对称属性：
如果 f(n) 为 O(g(n))，则 g(n) 为 Ω (f(n))。
示例： f(n) = n , g(n) = n²
然后 n 是 O(n²) 并且 n² 是 Ω (n)
此属性仅满足 O 和 Ω 符号。
6. 更多属性：
1.) 如果 f(n) = O(g(n)) 并且 f(n) = Ω(g(n)) 那么 f(n) = Θ(g(n))
2.) 如果 f(n) = O(g(n)) 并且 d(n)=O(e(n))
那么 f(n) + d(n) = O( max( g(n), e (n) ))
例： f(n) = n 即 O(n)
d(n) = n² 即 O(n²)
然后 f(n) + d(n) = n + n² 即 O(n²)
3.) 如果 f(n)=O(g(n)) 并且 d(n)=O(e(n))
那么 f(n) * d(n) = O( g(n) * e(n) ) )
示例： f(n) = n 即 O(n)
d(n) = n² 即 O(n²)
然后 f(n) * d(n) = n * n² = n³ 即 O(n³)
