数据结构与算法 1. 概论 2021-07-03 浏览量 1381 暂无评论 记:清华大学邓俊辉老师[数据结构与算法](https://www.bilibili.com/video/BV1jt4y117KR?from=search&seid=9699712924056767689)视频学习笔记。 [TOCM] # 1. 概论 ## 1.0 知识点 **5个问题:** 1. 什么是计算--课程的目标 2. 什么是好的计算--评判DSA优劣的参照 3. 度量DSA性能的尺度--渐进复杂度,不需要太精细 4. 怎么度量--DSA性能度量的方法 5. DSA的设计及其优化 **2个拓展:** 1. 理论模型与实际性能的差异 2. DSA优化的极限(下界) ## 1.1 计算 对象:规律、技巧 目标:高效、低耗 ### 1.1.1 例子 绳索计算机:垂线 尺规计算机:三等分,包含重复使用的子程序(做平行线) ### 1.1.2 算法 输入:问题 输出:答案 正确性 确定性:由基本操作组成的序列 可行性:可实现,可在常数时间内完成 有穷性:对任何输入,经过有穷次基本操作,都可以得到输出 ### 1.1.3 有穷性 序列Hailstone ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210416225210172.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 不能证明它是有穷的,也没有反例证明它是无穷的 写程序时经常写出死循环,栈溢出。 ### 1.1.4 好算法 **正确:** 符合语法,能够编译、链接,能够处理简单的、大规模的、一般性的、退化的、任意合法的输入 健壮:能辨别不合法的输入并做适当处理,而不致非正常退出 **可读:** 结构化 + 准确命名 + 注释 **效率:** 速度尽可能快,存储空间尽可能少 >Algorithms + Data Structures = Programs >(Algorithms + Data Structures) x Efficiency = Computation ## 1.2 计算模型 正确性:不好数学证明 **成本:** 运行时间 + 所需存储空间 **特定算法 + 不同实例** 如果用$$T_A(P)$$表示算法A求解问题实例P的计算成本,意义不大,因为可能出现的问题实例太多; 如果用$$T_A(n)$$表示算法A求解某一问题规模为n的实例所需的计算成本,仍然存在同一问题等规模的不同实例的计算成本不同(最好情况,最坏情况),应该首先考虑最坏情况; **特定问题 + 不同算法** 如果仅用实验统计,表面上很直接,但不足以准确反映算法的真正效率,因为算法的效率与输入规模、类型,使用的语言、编译器、体系结构、操作系统的状态有关; 所以需要抽象出一个理想的平台或模型:图灵机(Turing Machine)、Random Access Machine(RAM),一般计算工具的简化与抽象,独立于具体的平台,**将算法的运行时间转换为算法需要执行的基本操作次数。** ## 1.3 大O **渐进分析:大O记号** >$$T(n)=O(f(n)), iff \exists c > 0$$ ,当$$n >> 2$$时,有$$T(n) < cf(n)$$. $$\sqrt{5n[3n(n+2)+4]+6} < \sqrt{5n[6n^2+4]+6}< \sqrt{35n^3+6} < 6n^{1.5} = O(n^{1.5})$$. 与$$T_A(n)$$相比,$$f(n)$$更简洁,$$f(n)$$的常系数可忽略,低次项可忽略。 **渐进分析:其他记号** 最好情况(下界):$$T(n)=\Omega(f(n))$$. 中间情况:$$T(n)=\Theta(f(n))$$. **刻度:** 1.$$O(1)$$:2 = 2013 = 2013 x 2013 = O(1). 2.$$logn$$:常底数、常次幂、对数多项式都可以通过数学变换忽略掉 3.$$O(n^c)$$:多项式复杂度,只看最高次 4.$$O(n)$$:线性复杂度 5.$$O(2^n)$$:指数,通常认为不可忍受 ![复杂度](https://img-blog.csdnimg.cn/20210417215204191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **一个指数复杂度的例子:** S包含n个正整数,$$\sum{S}=2m$$,S是否有子集T,满足$$\sum{T}=m$$? NP-complete问题 ## 1.4 算法分析 **去粗存精地估算** 两个主要任务 = 正确性(不变性 x 单调性)+ 复杂度 在计算复杂度的时候,真的需要将算法描述为RAM的基本指令,再统计累计的执行次数吗? 不必哦!只要渐进,在渐进的意义下,C++等高级语言的基本指令等效于常数条RAM的基本指令。 **主要方法:** 1. 迭代:级数求和 2. 递归:递归跟踪 + 递推方程 3. 猜测 + 验证 ### 1.4.1 级数 1. 算术级数:与末项平方同阶 ```math \displaystyle T(n)=1+2+3+...+n=n(n+1)/2=O(n^2) ``` 2. 幂方级数:比幂次高出一阶(**咋求的呀**) ```math \displaystyle T_2(n)=1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6=O(n^3) ``` ```math \displaystyle \sum{_{k=0}^n} \approx \int{_0^nx^{d+1}dx}= \frac{1}{d+1}x^{d+1}|_0^n=O(n^{d+1}) ``` 3. 几何级数:与末项同阶 ```math \displaystyle T_a(n)=a^0+a^1+a^2+...+a^n=(a^{n+1}-1)/(a-1)=O(a^n) ``` 4. 收敛级数 O(1) 5. **调和级数** ```math \displaystyle h(n)=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\Theta(logn) ``` 6. **对数级数** ```math \displaystyle log1+log2+log3+...+logn=log(n!)=\Theta(nlogn) ``` ### 1.4.2 循环 vs. 级数 可以用画图的方法帮助计算 - 算术级数 ```math \displaystyle \sum{_{i=0}^{n-1}}n = n+n+n+...+n=O(n^2) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418210037255.png) ```cpp for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) O1Operation(i, j); ``` - 算术级数 ```math \displaystyle \sum{_{i=0}^{n-1}}i = 0+1+2+...+(n-1)=\frac{n(n-1)}{2}=O(n^2) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418210120406.png) ```cpp for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) O1Operation(i, j); ``` - 几何级数 ```math \displaystyle 1+2+4+...+2^{log_2(n-1)}=O(n) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418210207859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp for (int i = 0; i < n; i <<= 1) for (int j = 0; j < i; j++) O1Operation(i, j); ``` - 几何级数 ```math \displaystyle 0+0+1+2*2+3*4+4*8+...=\sum{_{k=0...logn}(k*2^{k-1})}=O(logn*2^{logn})=nlogn ``` ```math \displaystyle \sum{_{k=0}^n}\lceil log_2k \rceil=O(nlogn) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418212709925.png) ```cpp for (int i = 0; i < n; i++) for (int j = 0; j < i; j += j) O1Operation(i, j); ``` ### 1.4.3 取非极端元素 给定整数子集S,|S| >= 3,找出其中既不是最大值,又不是最小值的元素。 常数时间复杂度 ### 1.4.4 冒泡排序 初始版本 ```cpp // 外循环的终止条件是啥?没错,就是sotred,赋值的同时也充当判断条件 void bubblesort(int A[], int n) { for (bool sorted = false; sorted = !sorted; n--) for (int i = 1; i < n; i++) if (A[n-1] > A[i]) { swap(A[i-1], A[i]); sorted = false; } } ``` **分析:** 不变性:经k轮扫描交换后,最大的k个元素必然就位 单调性:经k轮扫描交换后,问题规模缩减至n-k 正确性:经至多n趟扫描惠普,算法必然终止,且能给出正确解答 ## 1.4.5 封底估算(Back-of-the-Envelope) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021041822493534.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 1.5 迭代与递归 > `迭代乃人工,递归方神通` 但是递归的效率通常不是最佳的,迭代体现出更强的优势 ### 1.5.1 数组求和:迭代 ```cpp int sumI(int A[], int n) { int sum = 0; // O(1) for (int i = 0; i < n; i++) // O(n) sum += A[i]; // O(1) return sum; // O(1) } ``` 分析: > 时间复杂度:O(n),空间复杂度(除输入本身):O(2) > 每循环一次,规模缩小1 > 引出`减而治之` ### 1.5.2 数组求和:线性递归(减而治之) ```cpp sum(int A[], int n) { return (n < 1) ? 0 : sum(A, n-1) + A[n-1]; // 缩减问题 + 平凡问题:可直接求解 } ``` 递归跟踪分析: > ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210419193519188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) > 时间复杂度:O(n),所有递归实例时间的总和,缩减问题的时间并入子问题 递推方程分析: > T(n) = T(n-1) + O(1) > T(0) = O(1) > 求解: > T(n) - n = T(n-1) - (n-1) = ... = T(2) - T(1) = T(1) - 1 = T(0) ### 1.5.3 数组倒置(减而治之) ```cpp // 递归版 void reverse(int* A, int low, int high) { // 问题规模的奇偶性不变,因为每次变化2,那最后的情况有两种: // 剩最小的奇数1,最小的偶数0,需要两个递归基,low==high,不用变,low > high,不用变 if (low < high) { swap(A[low], A[high]); // 平凡问题 reverse(A, low+1, high-1); // 缩减问题 } } // 迭代原始版 next: if (low < high) { swap(A[low], A[high]); low++; high--; goto next; } // 迭代精简版 while (low < high) swap(A[low++], A[high--]); ``` ### 1.5.4 分而治之 将大规模问题划分为若干个子问题(通常两个),规模**大体相当**,合并子问题的解。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210419200731410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 数组求和:二分递归 ```cpp sum (int A[], int lo, int hi) { if (lo == hi) return A[lo]; // 递归基 int mi = (lo + hi) >> 2; return sum(A, lo, mi) + sum(A, mi + 1, hi); } ``` 递归跟踪分析: > ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210419202123110.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) > 所有递归实例时间总和(去掉递归调用本身的时间去掉) > $T(n)=O(1) * (2^0, 2^1, 2^2, + ... + 2^{logn})=O(1) * (2^{logn+1}-1)=O(n)$ > 几何级数的总和与末项同阶 递推方程分析: > 递推基:sum(A, lo, lo) > $T(0)=2*T(n/2)+O(1)$,O(1)为归并时间 > $T(1)=1$,为什么这里不是T(0)?因为递推基的规模为1呀 > $$ > T(n) = 2*T(n/2) + c_1 \\ > T(n) + c_1 = 2(T(n/2)+c_1)=2^2*(T(n/4)+c_1) > =... > =2^{logn}(T(1)+c_1) > =2nc_1\\ > =>T(n)=O(n) > $$ ### 1.5.5 Max2 找出数组中最大的两个元素,比较次数尽可能少 迭代1,比较2n-3次 ```cpp void max2(int A[], int lo, int hi, int & x1, int & x2) { for (x1 = lo, int i = lo + 1; i < hi; i++) // 扫描A[lo, hi) if A[x1] < A[i] x1 = i; for (x2 = lo, int i = lo + 1; i < x1; i++) // 扫描A[lo, x1) if A[x2] < A[i] x2 = i; for (int i = x1 + 1; i < hi; i++) // 扫描A(x1, hi) if A[x2] < A[i] x2 = i; } ``` 迭代2,双指针,妙啊,比较次数:最好n-1,最坏2n-3 ```cpp void max(int A[], int lo, int hi, int & x1, int & x2) { if (A[x1 = lo] < A[x2 = lo + 1]) swap(x1, x2); for (int i = lo + 2; i < hi; i++) if (A[x2] < A[i]) if (A[x1] < A[x2 = i]) swap(x1, x2); } ``` 递归 + 分治 ```cpp void max2(int A[], int lo, int hi, int & x1, int & x2) { if (lo + 2 == hi) x1 = (A[lo] > A[lo + 1]) ? A[lo] : A[lo + 1]; if (lo + 3 == hi) { if (A[lo] > A[lo + 1]) { if (A[lo + 1] > A[lo + 2]) { x1 = A[lo]; x1 = A[lo + 1]; } else { if (A[lo] > A[lo + 2]) { x1 = A[lo]; x2 = A[lo + 2]; } else {x1 = A[lo + 2]; x2 = A[lo];} } else { if (A[lo] > A[lo + 2]) { x1 = A[lo + 1]; x2 = A[lo]; } else { if (A[lo + 1] > A[lo + 2]) { x1 = A[lo + 1]; x2 = A[lo + 2]; } else {x1 = A[lo + 2]; x2 = A[lo + 1];} } } } } int mi = (lo + hi) / 2; int x1L, x2L; max2(A, lo, mi, x1L, x2L); int x2R, x2Rl max2(A, mi, hi, x1R, x2R); if (A[x1L] > A[x1R]) { x1 = x1L; x2 = (A[x2L] > A[x1R]) ? x2L : x1R; } else { x1 = x1R; x2 = (A[x1L] > A[x2R]) ? x1L : x2R; } } ``` 分析: > 递推基:问题规模的奇偶性不变,两个递推基: > 1. 大于等于2的最小偶数,2,(为什么要大于2呢?因为要求解两个数呀) > 2. 大于等于2的最小奇数,3 > > 最差情况剩两组大小为3的数组: > $T(n) + 2 = 2(T(n/2)+2)<=2^{log(n/3)}(T(3)+2)=5n/3=>T(n)=5n/3-2$ ## 1.6 动态规划 通过递归找出算法的本质,给出初步解,再将其转化为等效的迭代形式。 ### 1.6.1 FIB **fib():递归** $fib(n)=fib(n-1)+fib(n-2):{0, 1, 1, 2, 3, 5, 8, ...}$ ```cpp int fib(n) { return (n < 2) ? n : fib(n-1) + fib(n-2); } ``` 当n稍微大点(如64)时,运行速度很慢,为什么呢? 直觉上看,它是将一个规模大的问题分解成两个规模小的子问题,这两个子问题有交集,其中一个子问题是另一个问题的子问题。 **递推方程分析:** > 递推基:$T(0) = T(1) = 1;$ > 方程:$T(n) = T(n-1) + T(n-2) + 1$ > 求解:令$S(n)=[T(n)+1]/2$,则$S(0)=1=fib(1),S(1)=1=fib(2)$ > 故$S(n)=S(n-1)+S(n-2)=fib(n+1)$, > $T(n)=2*S(n)-1=2*fib(n+1)-1=O(fib(n+1))=O(\Phi^n)=O(2^n)$ **封底估算:** >$\Phi^{36}=2^{25}, \Phi^{43}=2^{30}={10^3}^3=10^9flo=1sec$ >$\Phi^{5}=10,\Phi^{67}=10^{14}flo=10^5sec=1day$ **递归跟踪:** >![在这里插入图片描述](https://img-blog.csdnimg.cn/20210420192030818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) >有大量重复的递归实例,能不能每个实例只计算一次? >类比:爬楼梯,每次只能爬1、2阶,到第6阶有几种走法? **fib()回归迭代** 1. 记忆法:将已计算过的实例的结果制表备查 2. 动态规划 颠倒计算方向,由自顶向下递归变为自底向上迭代 两个变量记录当前相邻的两个数,滚动向前 ```cpp f = 0; g = 1; while (0 < n--) { g = g + f; f = g - f; } return g; ``` ### 1.6.2 最长公共子序列LCS **LCS:递归** A[0, n]; B[0, m] 递归基:n = -1 or m = -1, LCS is "" ```cpp if (A[n] == A[m] == 'X') LCS(A[0, n], B[0, m]) = LCS(A[0, n), B[0, m)) + 'X'; // 减而治之 else LCS = max(LCS(A[0, n), B[0, m]), LCS(A[0, n], B[0, m)) // 分而治之 ``` **分析:** >同一个递归实例会被多次唤醒,但实例个数共n+m,其实只需要计算n+m次 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630154346234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **改进:** 颠倒计算方向,从LCS(A[0], B[0])出发依次计算出所有项 ```cpp vertor vecA, vecB; int length[n+1][m+1] = {0}; for (int i = 0; i < n; i++) vecA.push_bask(A[i]); for (int i = 0; i < m; i++) vecA.push_bask(B[i]); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (vecA.at(i) == vecB.at(j)) length[i+1][j+1] = length[i][j] + 1; else length[i+1][j+1] = max(length[i][j+1], length[i+1][j]); } ``` 赞赏 微信支付 支付宝支付