算法分析与设计

数学基础(了解)

指数和对数

指数的基本性质

$e^xe^y=e^{x+y}$
$\frac{e^x}{e^y}=e^{x-y}$
$(e^x)^y=e^{x+y}$

对数的基本性质

$x^a=b$ 当且仅当 $\log_x{b}=a$
$\log_a{b} = \frac{\log_c{b}}{\log_c{a}}$ 其中 $a,b,c>0,a\ne1$
$\log_x{AB}=\log_x{A}+\log_x{B}$
$\log_x{\frac{A}{B}}=\log_x{A}-\log_x{B}$
$\log_x{A^B}=B\log_x{A}$
$a^{\log_b c}=c^{\log_b a}$
$\log_b (1/a) = -\log_b a $
$A \gt 0$ 时， $\log_x{A}<X$

常见对数

$log$ 是以 2 为底的对数

$log 1=0$
$log 2=1$
$log 1024=10$
$log 1048576=20$

级数

几何级数（等比数列的前 n 项和）
$\sum_{i=0}^N A^i=\frac{A^{N+1}-1}{A-1}$
$S_n = a_1 \frac{1-q^n}{1-q}$
当 $-1 < A < 1$ 时，级数收敛 $S=\sum_{i=0}^{\infty} A^i=\frac{1}{1-A}$
算术级数(等差数列的前 n 项和)： $\sum_{i=1}^N i = \frac{N(N+1)}{2} \approx \frac{N^2}{2}=O(N^2)$
平方和： $\sum_{i=1}^N i^2 = \frac{N(N+1)(2N+1)}{3} \approx \frac{N^3}{3}=O(N^3)$
k 次方和： $\sum_{i=1}^N i^k \approx \frac{N^{k+1}}{|k+1|}=O(N^{k+1}) (k\ne-1)$
调和级数
$H_N=\sum_{i=1}^N{\frac{1}{i}}\approx\ln{N}$ ，其中误差 $\gamma \approx 0.57721566$ ，这个数值称为 欧拉常数 。
对数级数
$\log 1 + \log 2 + \log 3 +...+ \log n = \log{n!} = \Theta(n \log{n})$

算法概述

算法的特点

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法的评价指标

正确性：算法应满足具体问题的需求；
可读性：算法应该好读，以有利于读者对程序的理解；
健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。

复杂度的表示法

大 $O$ 表示法（用得最多）

如果存在正常数 $c$ 和 $n_0$ ，当 $N \ge n_0$ 时， $T(N) \le cf(N)$ 则称 $T(N)=O(f(N))$ 。此时称 $f(N)$ 为 $T(N)$ 的上界， $T(N)$ 为 $f(N)$ 的下界。

此时， $T(N)$ 的增长速率比 $f(N)$ 慢或相同。这一般表示 最糟糕的情况 。

$\Omega$ 表示法

如果存在正常数 $c$ 和 $n_0$ ，当 $N \le n_0$ 时， $T(N) \ge cf(N)$ 则称 $T(N)=\Omega(f(N))$ 。

此时， $T(N)$ 的增长速率比 $f(N)$ 快或相同。它一般表示 最好的情况 。

$\theta$ 表示法

$T(N) = \theta(f(N))$ ，当且仅当 $T(N)=O(f(N))$ 且 $T(N)=\Omega(f(N))$ 。

此时， $T(N)$ 的增长和 $f(N)$ 相同，称 $T(N)$ 和 $f(N)$ 同阶。

这一般表示 平均的情况 。

小 $o$ 表示法

如果对于任意的 $c$ 存在 $n_0$ ，当 $N \geq n_0$ 时， $T(N) \lt cf(N)$ 则称 $T(N)=o(f(N))$ 。

一般表示复杂度时，对精确度要求不高，可以忽略常数、低次幂、对数的底数。
对于空间复杂度，不考虑输入数据。

可以使用 $O(N^2)$ 来代替 $O(2N^2)$ 和 $O(N^2 + N)$ 这两种表示。

复杂度的运算法则

若 $T_1(N) = O(f(N))$ 且 $T_2(N) = O(g(N))$ ，则：
1. $T_1(N)+T_2(N) = O(f(N)+g(N))$
2. $T_1(N)\times T_2(N) = O(f(N) \times g(N))$
若 $T(N)$ 是一个 $k$ 次多项式，则： $T(N) = \Theta(N^k)$
对任意常数 $k$ ，有 $\log^k{N}=O(N)$ 。它告诉我们对数增长非常缓慢。
极限确定复杂度：
$\lim_{N\rightarrow \infty} \frac{f(N)}{g(N)} = \begin{cases} 0 & f(N)=o(g(N)) \\ c\ne 0 & f(N)=\theta(g(N)) \\ \infty & g(N)=o(f(N)) \\ \end{cases}$
对于递归表达式 $f(n)=af(n/b)+g(n),a>1,b>1$ ，对应的时间复杂度为 T(n)，设 $k=\log_b {a}$ 。
- 若 $g(n)=\theta(n^p)$ ，且 $p \neq k$ 则 $q=\max \{p,k\},T(n)=\theta(n^q)$
- 若存在 $c \geq 0$ 有 $g(n)=\theta(n^k \times \log^c n)$ ，那么 $T(n)=\theta(n^k \times \log^{c+1} n)$

注： 2. 第二条实际上是主定理的拓展。原描述：若存在 $c \geq 0$ 有 $g(n)=O(n^k)$ ，那么 $T(n)=O(n^k \times \log n)$ 3. 上面的结论只是为了一般情况下的算法分析而做的一些简化，主定理的严格的公理化定义见下：

（重要）两个函数渐进界的判断

定义法
极限法（结合洛必达法则）

$f(n)= \log {n^2},g(n)= \log n + 5$

因为 $\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)}=\lim_{n\rightarrow \infty} \frac{2 \log n}{\log n + 5} = \lim_{n\rightarrow \infty} \frac{1}{1+5/\log n}=1$

所以 $f(n)=\theta (g(n))$

$f(n)= n,g(n)= \log^2 n$

因为

\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = \lim_{n\rightarrow \infty} \frac{n}{log^2 n}

=\lim_{n\rightarrow \infty} \frac{1}{2 \times \log n \times 1/n}

=\lim_{n\rightarrow \infty} \frac{n}{2 \times \log n}

=\lim_{n\rightarrow \infty} \frac{n}{2}=+\infty

所以 $f(n)=O(g(n))$

$f(n)= \log n,g(n)= \log^2 n$

解

当 $n \geq 2$ 时，有 $f(n) \geq 1,g(n) \geq 1$ 。
又因为 $g(n)=(f(n))^2$ ，且 $x \geq 1$ 时, $x^2 \geq x$ ，
所以当 $n \geq 2$ 时 $g(n) \geq f(n)$ ，即 $f(n)=O(g(n))$

（重要）递归方程复杂度的计算

主定理法
递归树法

主定理法
递归树法

大整数乘法中，时间复杂度的定义如下：

T(n)=\left\{\begin{matrix} O(1) & n=1 \\ 3T(n/2)+O(n) & n>1 \end{matrix}\right.

解

因为， $k=\log 3,g(n)=O(n),p=1$

所以 $k \neq p$ ， $T(N)=O(n^{log 3})$

分析

第一步，计算 $k$ ： $k=\log_a b$ ，分母为底数。结果为 $\log_2 3$

第二步，观察非递推部分的时间复杂度，发现是 $O(n)$ ，所以指数 $p$ 为 1。

第三步，比较 $p$ 和 $k$ ,两个不等，取最大的作为结果中 $n$ 的幂 $O(n^{\log_2 3})$

若 $p$ 和 $k$ 两个相等，那么 $T(n)=O(n^k \times \log n)$

如果非递归部分的时间复杂度不是多项式，那么主定理有可能不满足，此时建议采用递归树法来做。

大整数乘法中，时间复杂度的定义如下：

T(n)=\left\{\begin{matrix} O(1) & n=1 \\ 3T(n/2)+O(n) & n>1 \end{matrix}\right.

这个递归方程的的递归树如下：

其中，每个节点表示每个子问题非递归部分的时间复杂度，可以发现，只需要将所有节点的时间复杂度加起来，就可以得到整个问题的时间复杂度。

那么，这个递归的深度是多少？可以发现，子问题的规模是原来问题规模的 $1/2$ ，那么，第 $i$ 层( $i$ 从 0 开始)子问题的规模为 $\frac{n}{2^{i}}$ ，第 $i$ 层子问题的个数为 $3^{i}$ ，那么，这一层所有子问题的时间复杂度之和为 $O(\frac{3^{i}}{2^{i}}n)$ 。

令子问题的规模 $\frac{n}{2^{i}}=1$ ,可以求出递归深度 $d=\log n + 1$

注意，这个方程的解求的是最后一层的下标，但是这里深度是从 0 开始的，所以递归深度需要在解的基础上加 1。

由于最后一层，单个子问题时间复杂度是 $O(1)$ 而不是 $O(n)$ 。所以对于最后一层，节点个数为 $3^{\log n}$ ，这一层的时间复杂度为 $O(3^{\log n})=O(n^{\log 3})$

实际上，即使最后一层，单个子问题的时间复杂度为 O(n)，那么这一层的时间复杂度仍然为 $O(n^{\log 3})$

所以，整个问题的时间复杂度

T(n)= O(\sum_{i=0}^{\log n-1} (\frac{3}{2})^i \times n + n^{\log 3})

= O(n \times \sum_{i=0}^{\log n-1} (\frac{3}{2})^i + n^{\log 3})

= O(2n \times (\frac{(3/2)^{\log n}}{3/2}-1) + n^{\log 3})

= O(\frac{4}{3} n^{\log 3}-2n + n^{\log 3})

=O(n^{\log 3})

注：这里用到了对数的运算性质以及等比数列的求和公式。

分析

画出一个递归树（可选）
求出树的每一层的问题规模、子问题的个数，进而求出这一层的复杂度之和。（递归树深度从 0 开始）
计算整个问题的复杂度，即将每一层的时间复杂度加起来。

常见的复杂度

函数	名称
$1$	常数
$\log{N}$	对数（高效解）
$\log^k{N}$	对数的 k 次方
$N$	线性（有效解）
$N\log{N}$
$N^2$	平方级
$2^N$	指数级（难解）
$N!$	阶乘级

各种复杂度的增长规模：

(源: Big O Cheat Sheet. )

递归与分治

递归

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的 运行效率较低 ，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

概念

将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

适用条件

该问题的规模缩小到一定的程度就可以容易地解决
（前提）该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构 性质
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

求解步骤

分解：将主问题分解为多个子问题
解决：解决各个子问题
合并：将子问题的解合并为主问题的解

动态规划

特点

最优子结构：该问题可以分解为若干个规模较小的相同问题
重叠子问题：每次产生的子问题并不总是新问题，有些子问题被反复计算多次
备忘录方法：用数组保存子问题的答案

比较

与递归分治比较

相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

求解步骤

找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。

0-1 背包问题

给定 $n$ 种物品和一个背包。物品 $i$ 的重量是 $w_i$ ，其价值为 $v_i$ ，背包的容量为 $C$ 。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

设 ${dp}(i,j)$ 表示前 i 个物品放入一个容量为 $j$ 的背包时，前 $i$ 个物品的最大总价值。其中 $0<i\leq n,0<j \leq C$ 。

要得到 $dp(i,j)$ ，有两种办法：

如果第 $i$ 个物品的重量 $w_i$ 大于等于剩余容量 $j$ ，那么这个物品就不能放进去了，此时: $v_1=dp(i,j)=dp(i-1,j)$
如果第 $i$ 个物品的重量 $w$ 小于剩余容量 $j$ ，那么这个物品就可以放进去，此时是否

如果不打算放进去，则其总价值就是 $v_1$

如果打算放进去，那么：

放进去之前，物品的数量减一，总价值减去 $w_i$ : $dp(i-1,j-w_i)$
放进去之后，物品的总价值根据由放进去之前的总价值加上物品本身的总价值: $v_2=dp(i-1,j-w_i)+v_i$

此时选择放进去之前和放进去之后，总价值最大的情况。

dp(i,j)=\max \{v_1,v_2 \}

当 $i=1$ 时，即选择第一个物品时，若 $j < w_i$ ，则 $dp(1,j)=v_i$ ,否则 $dp(1,j)=w_i$ 。

递归方程：

dp(i,j)=\left\{\begin{matrix} dp(i-1,j) & w_i>j \\ \max\{dp(i-1,j-w_i),dp(i-1,j)\} & w_i \leq j \end{matrix}\right.

算法的时间复杂度： $O(N^2)$

算法的空间复杂度： $O(N^2)$

优化空间复杂度
观察发现，要得到 dp(i,j)，只需要 dp(i-1,j) 和 dp(i-1,j-w_i) 两个状态，也就是说，在设计的时候，二维数组只需要相邻的两部分，因此可以将二维数组降维一维，然后，改变内层循环的方向即可将空间复杂度降为 O(N)

贪心算法

特点

贪心选择：局部最优解能够得到整体最优解。（通常需要证明）
最优子结构：该问题可以分解为若干个规模较小的相同问题

比较

与动态规划

共同点：

都需要最优子结构性质，
都用来求有优化问题。

不同点：

动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。

动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。

动态规划：自底向上求解；
贪心方法：自顶向下求解。

可用贪心法时，动态规划方法可能不适用；
可用动态规划方法时，贪心法可能不适用。

搜索(回溯法和分支限界法)

回溯法

概念

回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

解题步骤

针对所给问题，定义问题的解空间
确定易于搜索的解空间结构
以深度优先方式搜索解空间，并在搜索过程中用 剪枝函数 避免无效搜索

分支限界法

概念

这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

和回溯法的差别

求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

两种类型

队列式分支限界
优先级队列式分支限界

求解步骤

(1)针对所给问题，定义问题的解空间（对解进行编码）；
(2)确定易于搜索的解空间结构（按树或图组织解）；
(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。