NJU 南京大学 算法设计与分析 期末复习

# 算法设计与分析 期末 [TOC] ## 算法的抽象分析 ### 证明正确性 肯定用**数学归纳法** ### 性能指标 最坏情况时间复杂度 平均情况时间复杂度：$A(n)=\sum_{I\in D_n} Pr(I)\cdot f(I)$，$I$是输入，$f(I)$是该输入的具体时间复杂度 ## 算法中的数学 ### 渐进增长率 $$ f(n)=O(g(n)) \text{ iff } \lim_{n\to \infty}\frac{f(n)}{g(n)} = c<\infty,c>0 \\ f(n)=o(g(n)) \text{ iff } \lim_{n\to \infty}\frac{f(n)}{g(n)}=0 $$ 两个都说明了f(n)增长率不如g(n)，但$o(g(n))$强调f与g间存在实质性的差距（更不如g了） $$ f(n)=\Theta(g(n)) \text{ iff } \lim_{n\to \infty}\frac{f(n)}{g(n)} = c,0<c<\infty \\ f(n)=\Theta(g(n)) \text{ iff } f(n)=O(g(n))\and f(n)=\Omega(g(n)) $$ 说明f和g同级 $$ f(n)=\Omega(g(n)) \text{ iff } \lim_{n\to \infty}\frac{f(n)}{g(n)}=c>0,c\text{可以为}\infty\\ f(n)=\omega(g(n)) \text{ iff } \lim_{n\to \infty}\frac{f(n)}{g(n)}=\infty $$ 两个都说明了f(n)增长率优于g(n)，但$\omega(g(n))$强调f与g间存在实质性的差距（更胜于g了） ### 求解分治与递归 #### 替换法 （期中考过） 利用数学归纳法，归纳证明$T(n)$的复杂度也小于等于$cO(n)$，$c$是某常数。 例如，求$T(n)=2T(n/2)+n$，猜测为$O(n\log n)$，步骤如下： 1. 假设对于小于$n$的参数都成立 2. 证明$n$也成立，如： $$ \begin{aligned} T(n)=&2T(n/2)+n\\ \leq&2c\frac{n}{2}\log \frac{n}{2}+n\\ =&cn\log \frac{n}{2}-c'n+n\\ \leq&cn\log n(c\ge 1) \end{aligned} $$ #### 递归树 用不上 如果一定要用就点了吧 #### 主定理 有式子$T(n)=aT(\frac{n}{b})+f(n)$，其中$a>=1,b>1$ 根据$n^{\log _b a}$与$f(n)$的大小关系分以下3种情况： 1. $f(n)=\Omega(n^{\log _b a-\epsilon})$，其中$\epsilon >0$ 表明$f(n)$的影响力不如递归 $T(n)=\Theta(n^{\log _b a})$ 2. $f(n)=\Theta(n^{\log _b a}\log^\epsilon n)$，其中$\epsilon \ge0$ 注意$n$的次方没有减去$\epsilon$，表明同级（但不完全同）。$\epsilon$可以为$0$表明$\log$项可以没有 $T(n)=\Theta(n^{\log _b a}\log^{\epsilon+1} n)$ 3. $f(n)=\Omega(n^{\log _b a+\epsilon})$，其中$\epsilon >0$，并且存在$c<1,n\to \infty, af(\frac{n}{b})\le cf(n)$ 后面那个条件不知道什么意思，反正考试也不会考没法用主定理的，所以直接忽视 $f(n)$占支配地位 $T(n)=\Theta(f(n))$ ## 蛮力算法 憨憨查找、选择排序、插入排序 ~~狗都会~~ ## 分治 in 排序 ### 快速排序 ``` Func Partition(A[], low, high) pivot = A[low] while low < high: while low < high && A[high] >= pivot: high-- A[low] = A[high] while low < high && A[low] <= pivot: low++ A[high] = A[low] A[low] = pivot return low Func QuickSort(A[], low, high) if low < high: pivot = Partition(A, low, high) QuickSort(A, low, pivot - 1) QuickSort(A, pivot + 1, high) ``` ### 归并排序 $$ W(n)=2W(\frac{n}{2})+O(n) $$ #### 决策树 引入决策树，说明算法结果需要一步一步走到叶节点，从而证明，比较排序的最坏情况时间复杂度的下界： $$ \Omega(n\log n) $$ #### 逆序对及计数 计算逆序对数，可以在归并排序中顺便完成 ```c++ long long merge_count(long long array[], long long start, long long end) { if (start == end) return 0; long long mid = (start + end) / 2; long long lcount = merge_count(array, start, mid); long long rcount = merge_count(array, mid + 1, end); long long p1 = mid, p2 = end; long long* copyarray = new long long[end - start + 1]; long long copy_index = end - start; long long count = 0; while (p1 >= start and p2 >= mid + 1) if (array[p1] > array[p2]) count += p2 - mid, copyarray[copy_index--] = array[p1--]; else copyarray[copy_index--] = array[p2--]; while (p1 >= start) copyarray[copy_index--] = array[p1--]; while(p2 >= mid+1) copyarray[copy_index--] = array[p2--]; for (long long i = 0; i < end - start + 1; i++) array[start + i] = copyarray[i]; return lcount + rcount + count; } ``` ## 分治例子 ### 整数乘法 长度都为$n$的$x y$相乘，直接计算复杂度为$O(n^2)$ $$ x=x_1\cdot 2^{n/2}+x_0,y=y_1\cdot 2^{n/2}+y_0\\ $$ 那么计算变为： $$ \begin{aligned} xy&=(x_1\cdot 2^{n/2}+x_0)(y_1\cdot 2^{n/2}+y_0)\\ &=x_1y_1\cdot 2^n+(x_1y_0+x_0y_1)\cdot 2^{n/2}+x_0y_0\\ &=x_1y_1\cdot 2^n+[(x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_0]+x_0y_0 \end{aligned} $$ 将问题分解为$x_1y_1$ $(x_1+x_0)(y_1+y_0)$ $x_0y_0$三个子问题 $$ W(n)\le3W(\frac{n}{2})+O(n) $$ 不知道为什么是小于等于 根据主定理 $$ W(n)=O(n^{\log_2 3}) $$ ### 检测异类 期中考过 列出所有情况组合，每次都只做降低规模至一半的操作 $$ W(n)\le \frac{n}{2}+\frac{n}{2^2}+\cdots\\ W(n)=O(n) $$ ## $O(\log)$时间算法 ### 二分查找 有序下二分查找、峰值查找、$\sqrt{N}$计算 ~~狗都会~~ ### 红黑树 红黑树性质如下： - 节点颜色只有红色或黑色 - 根节点必黑，叶节点必黑 - 节点若有子节点，必有2子；或者节点完全无子节点 - 红色节点不能连续出现 - 所有外部节点的黑色深度（到根路径上除根的黑色节点数）相等，称为黑色高度 准红黑树即根节点是红色，但其他性质都满足 **不存在$ARB_0$** 对于$h\ge1$，红黑树$RB_h$左右子树分别为$RB_{h-1}$或$ARB_h$ 对于$h\ge1$，准红黑树$ARB_h$左右子树都为$RB_{h-1}$ **假设$T$为一个有$n$个内部节点的红黑树，则红黑树的普通高度不超过$2\log (n+1)$，基于红黑树的查找代价为$O(\log n)$** ## $O(n)$线性选择k阶元素 > 想要找到阶为k的元素，最笨的方法是每次$O(n)$找最小（或最大）并取出，找$k$次即可，用时$O(kn)$ ### 期望情况 期望下，使用快速排序的Partition每次规模减半，可在$O(n)$内找到 ``` Func Partition(A[], low, high) pivot = A[low] while low < high: while low < high && A[high] >= pivot: high-- A[low] = A[high] while low < high && A[low] <= pivot: low++ A[high] = A[low] A[low] = pivot return low ``` 一顿期望的数学计算后，反正是$O(n)$ ### 最坏情况 考虑最坏情况，每次都精准地选出最小或最大数作为基准，那么每次规模只$-1$，那么$T(n)=T(n-1)+O(n)$，退化成$O(n^2)$ 通过将数据分组，用选出基准**组**的方式来避免过于不平衡。已知，5个一组最好（期中考过，必不可能再考） 算法SELECT-WLINEAR： 1. 所有元素分5组，凑不齐一组的元素暂放（也可按课本的分为一组） 2. 找出每组中位数，共$\lfloor \frac{n}{5}\rfloor$个 3. 对这$\lfloor \frac{n}{5}\rfloor$个中位数递归地使用SELECT-WLINEAR找出其中的中位数$m*$（同时调整好了组的位置） 4. 基于$m*$的大小对所有元素（含第1步凑不齐一组的元素）进行划分，假设有$x-1$个元素小于$m*$ 5. 若$k=x$，返回$m*$；若$k<x$，对小于$m*$的元素调用SELECT-WLINEAR找阶为$k$的元素；若$k>x$，对大于$m*$的元素调用SELECT-WLINEAR找阶为$k-x$的元素 $$ W(n)\le W(\lceil \frac{n}{5} \rceil)+W(\frac{7}{10}n+6)+O(n) $$ 第1项是找组中的中位数的中位数 第2项是划分结果。在所有$\lceil \frac{n}{5} \rceil$组中，至少有一半的小组要贡献3个比$m*$大的元素，其中不包括$m*$所在组以及最后凑不满的组，那么至少也淘汰掉$3(\frac{1}{2}\lceil \frac{n}{5} \rceil-2)\ge \frac{3n}{10}-6$个元素，子问题最大也不过$n-(\frac{3n}{10}-6)=\frac{7}{10}n+6$ 第3项是杂七杂八的用时 ## DFS ### DFS树 - 树边Tree edge - 回边Back edge - 子嗣边Descendant edge - 跨边Cross edge 有向图4种边都有 **无向图没有Cross edge**，证明如下： > 反设遍历点u时，发现一条边指向v，uv是CE（即u与v无祖先后继关系） > > 首先，v不是白色，否则uv是TE；v不是灰色，否则u与v有祖先后继关系，uv是BE；那么v应该是黑色。 > > 那么