数据结构与算法：算法分析

渐进表示法

虽然有时我们能够确定一个算法的精确运行时间，但通常并不值得花力气来计算它以获得额外的精度，对于足够大的输入，精确运行时间中的倍增常量和低阶项被输入规模本身的影响所支配。

当输入规模足够大，使得只与运行时间的增长量级有关时，需要研究算法的渐进效率。通常渐进地更有效的某峰算法对除很小的输入外的所有情况将是最好的选择。

渐进记号

渐进记号要求每个成员都渐进非负，以下c c1 c2 均为正数常量。

• $\Theta (g(n))$是以$g(n)$为渐进确界的所有函数集合

\Theta (g(n)) = \left \{ f(n) | c_{1}\leqslant  \lim_{n \to \infty  }  \frac{f(n)}{g(n)} \leqslant c_{2} \right \}

• $O (g(n))$是以$g(n)$为渐进上界的所有函数集合

O (g(n)) = \left \{ f(n) | \lim_{n \to \infty  } \frac{f(n)}{g(n)} \leqslant c  \right \}

• $\Omega (g(n))$是以$g(n)$为渐进下界的所有函数集合

\Omega (g(n)) = \left \{ f(n) | c \leqslant \lim_{n \to \infty  } \frac{f(n)}{g(n)} \right \}

三者的关系：$f(n) = \Theta (g(n)))\Leftrightarrow f(n) = O(g(n))$且$f(n) = \Omega (g(n))$

等式中的渐进记号

等式中渐进记号的不同含义

• $f(n) = O (g(n))$：表示$f(n)$是集合$O (g(n))$的成员，等价于$f(n) \in O (g(n))$，读作“$f(n) $以 $g(n)$为上界”。

• $2n^{2} + 3n + O(n^{2}) = O(n^{2})$：表示对于等号左侧任意的匿名函数，等号右侧总存在某个匿名函数使等号成立

渐进记号运算律

实数的许多性质也适用于渐进记号，通过简单的类比实数的不等式性质可以轻松推测出对应渐进记号类似的性质：

• 基本类比

$$f(n) = \Theta (g(n)) \Leftrightarrow a = b$$ $$f(n) = O (g(n)) \Leftrightarrow a \leqslant b$$ $$f(n) = \Omega (g(n)) \Leftrightarrow a \geqslant b$$

• 传递性

$$a = b, b = c \Rightarrow a = c$$ $$f(n) = \Theta (g(n)),g(n) = \Theta (h(n)) \Rightarrow f(n) = \Theta (h(n))$$ $$a \leqslant b, b \leqslant c \Rightarrow a \leqslant c$$ $$f(n) = O (g(n))) , g(n) = O (h(n)) \Rightarrow f(n) = O (h(n))$$ $$a \geqslant b, b \geqslant c \Rightarrow a \geqslant c$$ $$f(n) = \Omega (g(n))), g(n) = \Omega (h(n)) \Rightarrow f(n) = \Omega (h(n))$$

• 对称性

$$a =b\Leftrightarrow b=a$$ $$f(n) = \Theta (g(n)) \Leftrightarrow g(n) = \Theta (f(n))$$ $$a \leqslant b\Leftrightarrow b\geqslant a$$ $$f(n) = O (g(n)) \Leftrightarrow g(n) = \Omega (f(n))$$ $$a \geqslant b\Leftrightarrow b\leqslant a$$ $$f(n) = \Omega(g(n)) \Leftrightarrow g(n) = O (f(n))$$

• 加法法则：

$$T(n) = T_{1}(n) +T_{2}(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))$$

• 乘法法则：

$$T(n) = T_{1}(n) \times T_{2}(n) = O(f(n)) \times O(g(n)) = O(max(f(n)\times g(n)))$$

常见渐进函数

• 一般渐进函数排序

$$O(1) < O(lgn) < O(n) < O(nlgn) < O(n^{2}) < O(2^{n}) < O(n!) < O(n^{n})$$

• 特殊渐进函数：

$$lg(n!) = \Theta (nlgn)$$ $$(lgn)^{b} = o(n^{a})$$

时间复杂度和空间复杂度

计算机也许是快的，但它们不是无限快；存储器也许是廉价的，但不是免费的。所以计算时间是一种有限资源，存储器中的空间也一样，你应该明智地使用这些资源。

算法的效率通常用时间复杂度和空间复杂度来度量。

时间复杂度

算法中基本运算的频度记做f(n)，取f(n)中增长最快的项并将其系数置为1作为时间复杂度的度量。

$$f(n) = 3n^{3} + n^{2}+ 5n + 10 = O(n^{3})$$

算法的时间复杂度不仅与输入规模n有关，还与输入实例的具体情况有关：

• 最坏时间复杂度：在最坏情况下，算法的时间复杂度
• 平均时间复杂度：在所有情况等概率出现的情况下，算法的期望运行时间
• 最好时间复杂度：在最好情况下，算法的时间复杂度

空间复杂度

算法中除输入和程序之外所耗费的额外空间。

原地工作：算法所需的辅助空间是常数，即$O(1)$

同样的，算法的空间复杂度不仅与输入规模n有关，还与输入实例的具体情况有关：

• 最坏空间复杂度：在最坏情况下，算法的空间复杂度
• 平均空间复杂度：在所有情况等概率出现的情况下，算法的期望空间复杂度
• 最好空间复杂度：在最好情况下，算法的空间复杂度

主定理

主定理为求解如下形式的递归式提供了一种“菜谱式”的求解方法（$a\geq 1$，$ b> 1$）：

$$T(n) = aT(n/b) + f(n)$$

该递归式描述的是这样一种算法的运行时间：它将规模为n的问题分解为a个规模为n/b的同类子问题，函数f(n)包含了分解和组合子问题解的代价。

总原则：通过比较$f(n)$与$n^{log_{b}a}$的多项式大小可直接得出T(n)的增长量级。

1. 如果$f(n）$多项式大于$n^{log_{b}a}$(相差一个$n^{\varepsilon }$)，则$T(n) = O(f(n))$
2. 如果$f(n）$多项式小于$n^{log{b}a}$(相差一个$n^{\varepsilon }$)，则$T(n) = O(n^{log{b}a})$
3. 如果$f(n) = \Theta (n^{log_{b}a}lg^{k}n)$，则$T(n) = O(f(n)lgn)$

举例：

• 折半查找（满足3）：$T(n) = T(n/2) + O(1)\Rightarrow T(n) = O(1) * lgn = O(lgn)$
• 快速/归并排序（满足3）：$T(n) = 2T(n/2) + O(n)\Rightarrow T(n) = O(n) * lgn = O(nlgn)$
• $T(n) = 2T(n/2) + nlgn\Rightarrow T(n) = O(nlgn * lgn) = O(nlg^{2}n)$