数学基础，包含渐进符号含义（用于算法复杂度表示），递归方程（由递归方程求解算法复杂度）。
渐进符号
-
$\Theta$
同阶函数集。
$f(n) = \Theta(g(n))$表示在$c_1g(n)$ 与 $c_2g(n)$中函数集合，且这些函数满足：$c_1$,$c_2$是存在的，且存在$n_0$，使得$ n \ge n_0$时恒有$c_1g(n) \le f(n) \le c_2g(n)$ 。我们将其记为$f(n) = \Theta(g(n))$ 。 即$f(n)$是$g(n)$的同阶函数。
上面的表示是书上的表示，我觉得并没有什么用。
用后面的的知识，我们可以认为，如果是同阶函数，则当n趋于正无穷时，两函数比值的极限为常数. 即
\(\lim_{n \to infty}\frac{f(n)}{g(n)} = c\) , $c$是一个常数。
考试中可能出题要求证明，两个函数是同阶函数
- 使用定义来证明，即对$c_1g(n) < f(n) < c_2g(n)$ , 找到合适的$c_1$ , $c_2$ ，找到临界点或者正确的点$n_0$即可。
定理（待证明） ： 对任意多项式$p(n) = \sum_{i=0}^{d}{a_in^i}$ , 其中$a_i$是常数且$a_d$为正常数，则有$p(n) = \Theta(n^d)$。直观来看，就是对于多项式函数，其同阶函数就是该变量的最高次项（忽略非最高次项，忽略最高次项的系数）。
$\Theta$符号定义了函数的上下确界。
-
$O$
低阶函数集。
$f(n) = O(g(n)) (f(n) \le cg(n))$定义了以$cg(n)$为上界的函数集。（当然是有条件的，即$c$大于0 ， $g(n)$非负）
同阶函数也可以用大O表示(取等号时)。
-
$\Omega$
高阶函数集。
$f(n) = \Omega (g(n)) ( f(n) \ge cg(n)) $ 定义了以$c g(n) $为下界的函数集。
同样包含同阶函数。可以认为$O$与$\Omega$互逆。
-
$o$
与$O$类似，但定义的是严格低阶函数（不取等号，但是在算法导论中，不是如此定义的）。
算法导论中定义，对任意的$c$ , 存在常数$n_0 > 0$ ， 使得$n > n_0$时有 $ 0 \lt f(n) \le cg(n)$ . 不知道这里取等号究竟是疏漏还是确实如此。但这个从直观上理解更好确定。就是一个严格低阶的函数集。
-
$\omega$
严格高阶的函数集。
-
条件补充
上面的集合、函数定义条件都没有说完整。这里把他的上下文说完整。
首先需要明确，不是任何两个函数都有渐近关系，都能用渐近符号表示的。算法导论上举了线性函数$n$ 与函数 $n^{1 + \sin{n}}$。由于前者随n增大线性变化，而后者由于指数在0到2间随n循环变化，值域变化太大。二者存在渐近关系。
其次，这里的函数，$f(n)$ ， $g(n)$ 都是非负的。因为这些都是由实际意义的函数（算法复杂性表示）。$c_*$也是正数。
-
渐近关系的一些性质
-
传递性 （类似 $f(n) = O(g(n)) $ , $ g(n) = O(k(n)) $ ，则有 $ f(n) = O(k(n)) $ 等）
-
自反性 $f(n) = \Theta(f(n))$ , $f(n) = O(f(n))$ , $f(n) = \Omega(f(n))$
-
对称性 只同阶函数，即$f(n) = \Theta (g(n)) iff g(n) = \Theta (f(n))$
-
转置对称性 指$O$与$\Omega$ , $o$ 与$\omega$之间的对称。如$f(n) = O(g(n)) iff g(n) = \Omega(f(n))$
-
递归方程
递归式(recurrence) : 当一个算法包含对自身的递归调用时，其运行时间通常可以用递归式来表示。
课程（书籍）主要介绍了三种递归式求解方法，分别是代换法(substitution method) , 递归树方法（recursion-tree）(或者称为循环展开方法，iteration method) ， 主方法（Master Method ， 课程中称为Master定理） 。
在求解递归式时，通常需要略去一些技术细节。例如 上取整 , 下取整 , 边界条件。
如实际的MERGE-SORT的运行时间递归式应该为：
\[T(n) = \begin{cases} \Theta(1) & n = 1 \\ T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + \Theta(n) & n \gt 1 \end{cases}\]忽略细节的条件下，可以写作：
\[T(n) = 2 T(\frac{n}{2}) +\Theta(n)\]以下将分别介绍3种求解方法。
-
代换法(substitution)
这里的代换法，不仅仅是字面上的替换之意，一般包含两个步骤：
-
猜测可能的时间复杂度（或者上下界）
-
使用数学归纳法进行证明
所以这个主要是针对一些常见形式的递归方程。当然，对于不能直接猜测的方程，我们可以先使用第二种方法——递归树方法粗略的猜测一个结果，然后使用该方法来得到确切的证明。
一个例子：
$T(n) = 2T(\frac{n}{2}) + n$
这个式子比较熟悉了，就是归并排序的递归式，我们猜测其时间复杂度为$O(n \lg n)$ , 即 $ T(n) = O(n \lg n)$
接下来就需要使用数学归纳法来证明该递归式的时间复杂度的确是$O(n \lg n)$
按照数学归纳法的一般步骤，首先要证明 初始条件（在算法中称为
边界条件，此后主要使用该称呼）需要得到满足-
证边界条件
按照常理来说，边界条件为 ： $n = 1$时，满足 $ T(1) \le c \cdot n \lg n = c \cdot 1 \cdot \lg 1 = 0 $
我们知道$T(1)$是不可能小于等于0的（一般取1），故这里证明边界条件就出现了问题！
是否是我们的猜想不对呢？
这里我们需要回到渐近符号的定义： 对任意渐近符号，满足不等式的条件都是对$n \gt n_0 , n_0 > 0$这一前提条件来说的，所以说，我们的边界条件不是 $n = 1$ ， 而是$n=n_0$ ，这里我们可以取$n_0 = 2$
$T(2) = 2T(1) + 2 = 2 + 2 = 4 \le 2\lg 2 \cdot c$ , c取大于2的数时即满足条件。
故边界条件得证。
-
证递推成立
假设$T(n) = O(n \lg n)$成立，即有$T(n) <= c \cdot n \lg n , c \gt 0$
下一个递推项为$2n$(这里注意，根据递归方程，下一项我们取$2n$ ，而不是以前数学中常取的$n+1$)
只需证明 $ T(2n) <= c \cdot 2n \lg (2n) = 2c n\lg n + 2 \lg2 \cdot c n $即可。
\[\begin{align*} T(2n) &= 2T(n) + 2n \\ &\le 2 \cdot ( c \cdot n \lg n ) + 2n \\ &= 2 \cdot n \lg n + 2n \\ \end{align*}\]要使$ 2 c n \lg n + 2 n \le 2 n \lg n + 2 \lg2 c n $
只需$ \lg2 c \ge 1 $ 即可 ， 即取$ c \ge \frac{1}{\lg2} $
证毕。
从上面的例子可以看出，在算法问题中使用数学归纳法与传统高中数学使用的数学归纳法还是有所差别的，但是，这并不是说，在算法中使用数学归纳法就不足够严谨。在上例中，改变边界条件、确定下一个递推项，都是根据实际情况做出的判断，而不是纯粹的数学推理。在实际问题中应用数学，即要保证符合实际情况，又要符合数学的严谨，这实在是很难的一个过程。
猜测的例子
对于递归式 $ T(n) = 2T(\lfloor \frac{n}{2} \rfloor + 17) + n $ , 求其复杂度。
我们要知道，渐近符号一般都是在变量趋于无穷大时才有渐近意义。故而，在该例子中，当n趋于无穷大事，$\lfloor \frac{n}{2} \rfloor + 17$ 完全可以等价于 $ \lfloor \frac{n}{2} \rfloor$ ，经过如此等价，递归式又与MERGE-SORT的递归式一致了。从而，我们给出猜测$O(n\lg n)$ ， 然后再运用数学归纳法证明（当然，在证明中其实也需要用到该约等于条件。在趋于无穷大时，该条件能够保证其严谨性）。
特殊的例子
对于递归式 $ T(n) = T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 1$ ， 我们猜测其复杂度为$O(n)$ 。
证明递推：
复杂度为$O(n) $ , 则有 $ T(n) \le c n &
递推下一项为$2n$ ,
\[\begin{align*} T(2n) &= 2T(n) + 1 \\ &\le 2 ( c n) + 1 \\ &= 2cn + 1 \end{align*}\]要使递推成立，需证明$T(2n) \le 2cn $在$c$取某值时成立。而由T(2n)的递推$T(2n) \le 2cn + 1 $ 要证 $ 2cn + 1 \le 2cn $显然对任意$c$都是不可能成立的！
我们的递推式差数学归纳法的推理结果一个常数项，我们可以尝试修改我们的数学归纳法假设。
复杂度为$O(n) $ , 则有 $ T(n) \le c n $ , 设有常数$b , b \ge 0 $ , 则有 $ T(n) \le cn - b \le cn $ , 在数学归纳法证明中，我们使用带有常数项的$T(n) \le cn - b $
即 ：
\[\begin{align*} T(2n) &= 2T(n) + 1 \\ &\le 2 ( c n －ｂ ) + 1 \\ &= 2cn + 1 - 2b \end{align*}\]要令它小于$T(2n) \le 2cn - b$ , 只需 $b \ge 1$即可。
这个是一个Trick了。
变量代换与函数代换
求递归式$T(n) = 2T(\lfloor \sqrt{n} \rfloor) + \lg n$的复杂度。
我们首先令$ m = \lg n$ ， $ n = 2^m $ ，带入原递归式中，有$T(2^m) = 2T(2^{\frac{m}{2}}) + m $ [变量代换]
接着令$ S(m) = T(2^m)$ ， 则递归式变为 $ S(m) = 2S(\frac{m}{2}) + m $ [函数代换]
易知其复杂度为$O(m\lg m)$ , 即$ T(n) = T(2^m) = S(m) = O(m \lg m) = O(\lg n \lg ( \lg n )) $
这也可以认为是一个Trick.
由上可知，代换法虽然使用数学归纳法证明，但是其中仍然包含一些Trick。
-
-
递归树方法（循环展开法）
这是一种比较直观的方法，对形如 $ T(n) = aT(\frac{n}{b}) + f(n)$ 的递推式，我们可以递归的展开等式右边的T(\frac{n}{m})项直到1，由于我们认为$T(1) = O(1)$ ， 故我们通常就能得到一个比较准确的时间复杂度。
由第一项右边的T(\frac{n}{b})展开到T(1) ， 每一次展开T内部都是除以b，直到为1 ， 则可求出展开次数为$\frac{n}{b^k} = 1$ , $k = \log_b{n}$ 。
每次展开$T(\frac{n}{m})$前面都要乘上一个$a$ ， 则到最后展开到$T(1)$时，其前面的系数为$a^{k} = a^{log_b{n}}$ ， 由对数性质，有$a^{log_b{n}} = n^{log_b{a}}$（目前还不知道如何证明的） ；
每次展开对式中的$f(x)$项，设为第t次展开，其关于$f(x)$增加的项为：前面的系数为$a^(t-1)$ , f(x)中的x为 $f(\frac{n}{b^(t-1)})$(相对于展开次数滞后一位，因为是把上次的$\frac{n}{b^(t-1)}带入本次展开得到的$) ， 则到展开为1时，全部的关于$f(x)$的项为$\sum_{t=0}^{t=\log_b{n} -1}{ a^{t} f(\frac{n}{b^{t}}) }$ (式中t从0开始，到 $k-1$ , 即$( \log_b{n} -1 )$为止)
总结起来，常见的递归式可展开为 $T(n) = \Theta(n^{\log_b{a}}) + \sum_{t=0}^{t=\log_b{a}}{a^t f(\frac{n}{b^t})}$
这样就能够得到精确的复杂度了。（事实上，第三种主方法就是在上式的基础上通过分类各条件，得到更加直观的解）
实际上，通常来说，我们在循环展开时往往不必如此的精确。我们可以粗略的递归展开，然后得出一个猜测，再使用第一种代换法来证明。
一个例子
求递归式$T(n) = 3T(\frac{n}{4}) + cn^2 $的复杂度
我们可以直接套用公式，有展开式为
$T(n) = \Theta(n^{\log_4{3}}) + \sum_{t=0}^{t=\log_4{3} -1}{3^t c (\frac{n}{4^t}})^2$
注意到后面一项是以1为初始项，$\frac{3cn^2}{16}$为比例的等比数列，极限条件下它的和为$\frac{1}{1 - \frac{3cn^2}{16}} = \frac{16cn^2}{13}$
故$T(n) = \Theta(n^{\log_4{3}}) + \frac{16c}{13}n^2 = O(n^2)$
更复杂的情况
求递归式$T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + O(n)$的复杂度
有两个不同的递归项，不能直接套公式了，所以需要重新递归求解一遍。
由于递归式中有两项，导致每次递归，项都会增多，想要求出精确的递归展开式似乎不是那么简单的事。这时，我们可以尝试粗略的递归展开。根据之前求MERGE-SORT的经验，我们可以猜测其最终的复杂度主要取决于$O(n)$项（的系数），而$O(n)$的系数又决定于递归式究竟需要多少步，才能使所有的递归项都变为T(1)。
直观的，我们可以选择每步衰减最小的方向（本式中每次衰减3/2），这决定了递归式的展开步数上限。由此有$\frac{n}{ {\frac{2}{3}}^k} = 1$ , $k = \log_{\frac{3}{2}}{n}$ , 则$O(n)$前面的系数就为 $log_{\frac{3}{2}}{n}$ , 因而决定其负责度为$O(n \log_{\frac{3}{2}}{n}) = O(n\lg n)$
由于上述的递归展开不是精确的，所以我们需要对其使用数学归纳法证明。这里不再证明了。（需要说明的是，原递归式中，有$O(n)$项，在数学归纳法证明中，我们可以将其写作$cn$ 。)
-
主方法（MASTER定理）
在方法2中，已经对形似$T(n) = aT(\frac{n}{b}) + f(n)$的递归式进行了展开，得到了精确的展开式 ：
\[T(n) = \Theta(n^{\log_b{a}}) + \sum_{t=0}^{t=\log_b{a}}{a^t f(\frac{n}{b^t})}\]MASTER定理就是在此基础上进行了归纳总结，使得结果更加的简洁和漂亮。
定理（MASTER定理）
设$a \ge 1$ 和 $ b \gt 1$为常数，设$f(n)$为一常数，$T(n)$由递归式
\[T(n) = aT(\frac{n}{b}) + f(n)\]对非负整数定义。其中$\frac{n}{b}$值$\lceil \frac{n}{b} \rceil$ 或 $\lfloor \frac{n}{b} \rfloor$ 。那么$T(n)$可能有如下的渐近界：
-
若对于某个常数$\epsilon \gt 0$ , 有 $f(n) = O(n^{\log_b{a} - \epsilon})$ ， 那么$T(n) = \Theta(n^{\log_b{a}})$
-
若 $f(n) = O(n^{\log_b{a}})$ , 则$T(n) = \Theta(n^{\log_b{a}} \lg n)$
-
若对于某个常数$\epsilon > 0$ ， 有 $f(n) = \Omega(n^{\log_b{a} + \epsilon})$ , 且对于常数$c \lt 1$ 与所有足够大的$n$ ， 有$a f(\frac{n}{b}) \le cf(n)$ ， 则$T(n) = \Theta(f(n)) $
总结一下关键点，其实就是比较$f(n)$ 与 $n^{\log_b{a}}$的大小
-
如果相等，就是情况2
-
如果$f(n)$大，且至少是$n^{\log_b{a}}$ 的 $n^{\epsilon}$倍，且满足$af(\frac{n}{b}) \le cf(n) , c \lt 1$ ， 则满足情况3
-
如果$f(n)$小，且至少小$n^{\epsilon}$倍，那么满足情况1
（PS，MASTER定理确定的渐近界都是确界，即是同阶函数！）
对于MASTER定理，可以使用图示说明。
对于MASTER定理的例子就不再列举了，一定要注意，MASTER定义不是万能的，在应用MASTER定理时需要验证条件是否得到满足。
总结了使用MASTER定理解递归方程的步骤。
-
写出 $a$ , $b$ , $f(n)$ , $\log_b{a}$ , $n^{\log_b{a}}$
-
直观的看$f(n)$与$n^{n^{\log)_b{a}}}$的大小，如果$f(n)$大，转到3；如果$f(n)$小，转到4；如果同阶，则直接写答案$T(n) = \Theta(n^{\log_b{a}}\lg n)$
-
算$\frac{f(n)}{n^{\log_b{a}}}$ ， 如果结果与$n^{\epsilon}$同阶，还要继续判断条件$cf(\frac{n}{b}) \le cf(n)$ ， 如果存在这样的c，且$c \lt 1$ ， 则写答案$T(n) = \Theta(f(n))$ ， 否则MASTER定理不能判断。如果前面不同阶，MASTER定理也不能判断。
-
算$\frac{n^{\log_b{a}}}{f(n)}$ ， 如果结果与$n^{\epsilon}$同阶，则复杂度为$T(n) = \Theta(n^{\log_b{a}})$ ， 否则MASTER定理不能解。
-
以上写了三种解递归方程的方法。无疑MASTER是最好用的，但是也必须意识到其局限性。递归展开看起来是最全能的，但也可能非常复杂。如果需要忽略某些展开式来获得一个粗略的解时，需要使用数学归纳法进行证明，而这在表面上看来就是方法1。
此外，还有生成函数这种方法来解递归方程。当然仅仅是知道这个名字，并不知道具体怎么做。
这章总算是完了，感觉真累啊…