算法分析 | 第三套（渐近符号）

我们已经讨论了渐近分析 和 最差、平均和最佳情况。渐近分析的主要思想是衡量算法的效率，这些算法不依赖于特定于机器的常数，并且不需要实现算法和比较程序所花费的时间。渐近符号是表示渐近分析算法时间复杂度的数学工具。以下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) 也涵盖线性时间。 
如果我们使用 Θ 表示法来表示插入排序的时间复杂度，我们必须对最好和最坏情况使用两个语句：

1. 插入排序的最坏情况时间复杂度是 Θ(n^2)。
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³)