前言
本系列记录我对于各种算法的理解。
本篇改自我本科课程“算法设计与分析”的笔记。本篇不通过例子讨论具体的算法。
算法复杂度分析的数学工具
算法是为了解决问题而生的，它必须有这样几个性质：可终止、有确定性、正确性、有输入/输出。算法的复杂度分析通常从两个方面来入手——时间复杂度分析和空间复杂度分析。
时间复杂度分析通常以操作的个数衡量。对于一个特定的输入来说，算法的时间复杂性是对该输入产生结果所需要的原子操作数。一个算法的时间复杂度是关于输入大小的函数，记作$T(n)$，其中$n$是输入的大小。
空间复杂度分析通常以占据的存储空间大小来衡量。对于一个特定的输入来说，算法的空间复杂度是该算法对该输入产生结果所需要的存储空间大小，记作$S(n)$。
接下来我们来讨论一下分析复杂性的工具，其实用于分析的基本工具很简单，只有这么几个：同阶函数集合、低阶函数集合、高阶函数集合和严格低/高阶函数。
对于同阶函数来说，最重要的是观察函数的主导项，比如$f(x)=x^2+3x+4$这个函数，其同阶函数集合就可以表示为$\Theta(n^2)$，因为这个函数的主要增长项是$x^2$，这个时候，要忽略低阶项和常系数。一个形式化的表达是：
$$
\Theta(g(n))=\{f(n)|\exists c_1,c_2>0,n_0,\forall n>n_0,c_1g(n)\leq f(n) \leq c_2g(n) \}
$$
低阶函数集合用于描述一个函数的上界，用$O(n)$格式来表示，其形式化定义是：
$$
O(g(n))=\{f(n)|\exists c>0, n_0, \forall n>n_0, 0\leq f(n)\leq cg(n)\}
$$
高阶函数集合用于描述一个函数的下届，在算法领域，用于描述最优情况的复杂度，用$\Omega(n)$的格式来表示。
在这个基础上，我们有一个重要的分析工具——递归方程。比如对于归并排序，就有如下的公式：
$$
T(1)=O(1)
$$
$$
T(n)=2T(\frac{1}{2}n)+O(n)
$$
这个时候，我们该如何求得$T(n)$的同阶函数集合呢？完全可以用迭代法，也就是通过数列迭代的基本关系求解，比如：
$$
T(n)=2T(\frac{1}{2}n)+cn=4T(\frac{1}{4}n)+2cn=\cdots
$$
由此可见，这个公式的结构是：
$$
T(n)=2^kT(\frac{1}{2^k}n)+kcn
$$
当$\frac{1}{2^k}n=1$时，有$k=\log_2n$，这个时候有：
$$
T(n)=n+cn\log_2n
$$
由此可知，$T(n)=\Theta(n\log n)$。
当然，也可以用主定理来快速求解，主定理的内容是，当递归方程形式为$T(n)=aT(\frac{n}{b})+f(n)$且$a\geq 1,b>1$时，若：
- 存在$\epsilon>0$，有$f(n)=O(n^{\log_ba-\epsilon})$，则$T(n)=\Theta(n^{\log_ba})$。
- 存在$\epsilon\geq0$，有$f(n)=\Theta(n^{\log_ba}\log^\epsilon n)$，则$T(n)=\Theta(n^{\log_ba}\log^{\epsilon +1}n)$。
- 存在$\epsilon > 0$，有$f(n)=\Omega(n^{\log_ba+\epsilon})$，且存在$c<1$和一个足够大的$n$，满足$af(\frac{n}{b})\leq cf(n)$，则$T(n)=\Theta(f(n))$。
分治法
分治法的基础是“划分-求解-合并”，其递归方程的格式为：
$$
T(n)=aT(\frac{n}{b})+D(n)+C(n)
$$
其中字母的含义是：将问题分解为$a$个部分，$D(n)$是划分的耗时，$C(n)$是合并的复杂度。
动态规划
动态规划所适用的问题是，大问题的计算过程中，会重复计算很多子问题，造成不必要的开销。如果从子问题求解，并记住子问题的结果，就能够节省重复计算子问题的开销，其递归方程没有一个具体的通常格式，需要根据不同问题进行分析。
贪心算法
贪心算法的核心思想是，每一步的决策都做出当前的局部最优决策。这种算法的证明通常是通过归纳法以及交换论证法证明的。交换论证法通常是假定一个最优解，然后将所谓的最优决策换为贪心决策，最终得到更优的贪心解。
后记
具体的算法流程将在后续讲述。这门课我觉得最大的收获便是算法复杂度分析的数学工具。