这个记号（notation），好处在哪里呢？和陶渊明的所说的是，不谋而合的。”好读书不求甚解“，不需要拘泥于过多的细节，分析DSA的时候，我们更应该关注于长远，比如分析的问题规模巨大时，和主流即主要的方面，换言之也就是更关注DSA的潜力，这种分析方式就是渐进分析（asymptotic analysis)。

对于这么一个函数图像，纵轴是计算成本，横轴是问题规模。我们不关心局部的变化，只在意它的长远。

引入大o记号是，为了简化度量时间成本T（n）所引进的。

对时间成本T（n），我们可以在big-o的意义下，将T（n）表示为一个f(n)

条件是，存在一个常数C>0, 当问题规模n远大于2的时候，总有T（n) 小于常数c和f(n)的乘积。

例子：

假设我们有一个这样的T（n)，简化的具体操作，实质上是将常数放大为n因为n是远大于常数的。

大O记号可以将其足够的简化。

两个大O记号的处理手法，在最下方。

所谓长远和主流，也在大O记号的处理中得到体现，一是问题规模n足够大，二是处理时会忽略细枝末节（常系数、低次项）。

相当于是在原来的函数图像中引入了BIG-O虚线，它是Tn的悲观估计，是它的upper bound 上界。

除了大O记号，我们还有其他记号如大Ω的记号，它和大O 记号的定义相反。它是存在于一个常数C，在n>>2 的时候，总有T(n)>c * f(n)。这也意味着它是T（n）的 lower bound 下界。还有一个记号叫θ记号，它是大O和大Ω的中间状态的感觉，它的定义是，存在常数c1,c2,在n>>2的时候，有：c1*f(n) > T(n) > c2*f(n)。它构成了确界

函数图像如图：

在分析DSA的时候我们也更关注悲观的情况，也就是BIG-O 的情况，除非有特定的场景，才回去讨论θ和Ω。

大O记号，明确了算法复杂度的度量标准了，如何具体分析具体算法的复杂度呢？大O记号将各个算法的复杂度由低到高划分为了若干层次的级别也可以说是” 刻度 “

高效解：

第一个刻度：O(1) 常数复杂度

常数、较大的常数、常数的四则运算甚至常数的高阶运算。我们也认为它是常数复杂度 O(1)。

什么样的代码段对应常数复杂度？

书上P12页上的取非极端元素的例子很好的说明了这一点。但是，也不是说有循环和调用、递归就一定不是O（1）

注意n>>2，对于首循环来说，步进相当于就是常数的四则运算，复杂度便是O(1),第二个循环是同理的。第三个代码段，虽然做了判断，和goto转向，但是当goto的地方是一个不可到达的地方（unreachable）,也认为是常数复杂度。第四个因为暂时没有学递归，没法解析，后续会补上。

**第二个刻度对数复杂度O(logn)，（是常数C的指代，因为输入法不能打下标）**

这种复杂度，是无限接近常数复杂度的，足够的高效，第一个刻度和第二个刻度可以认为是高效解。

ps:上面的规则，后两个借鉴了大O记号，常底数忽略，是因为，只要是常数底数，就可以乘以一个对数进行转换，既然可以随便转换所以干脆忽略。

有效解：
第三个刻度O（n*）多项式复杂度：

这一类刻度对应的算法，仍算是可解。

难解：

第四个刻度O(2的n次方)

小结

把各个刻度放在函数上，让我们对这把直尺的刻度有了直观的认识。

分析DSA

在之前的内容中，我们了解到基本的计算模型，还有以大O记号形式所表达的刻度。有了直尺和刻度，我们已然具备了分析DSA的完备工具和体系。所以开始学习如何使用它们来分析算法，包括主要的思路和方法。这一节的内容，主要

1-D 复杂度分析

分析算法，首先要明确，要完成什么任务才是完成了分析。

不变性和单调性，书中的的例子主要是起泡排序bubblesort，分析算法更关键的还是在于复杂度的分析。

复杂度的分析，我们知道是利用了计算机模型RAM来看算法的基本操作次数来确定T（n）,很幸运的是，因为有了前面引进的”刻度“，我们不用真的用ram来分析复杂度，对应不同的算法，我们会使用不同的复杂度分析方法，这个是需要重点掌握的。

值得一提的是，高级语言中的基本指令是等效RAM的，平常不引起歧义的情况下，可以借用基本指令这个说法。

我们将算法分为两类，也对应有不同的分析方法

分为迭代式的算法和递归式的算法，其中级数求和的能力是我们需要不断提高的功夫！

什么是级数：

所谓算数级数，就是从某一个数开始，以固定的间隔不断地线性递增，他们的总和就成为算数级数。对于这类的级数，引入大O记号之后，为多项式复杂度，结果总是末项平方的同阶。

对幂方级数，推广有：大O记号如下

几何级数有：

对调和级数和对数级数来说，他们是有确界θ的，这个后续会经常使用！！！要熟记。

如何分析循环

了解了级数的基础之后，我们要能利用级数分析循环。接下来会举例说明。

例1：普通的二重循环

这里算的是基本操作数，也就是循环了多少次，不难知道就是n的次方属于是算术级数。

可以把它理解为这么一个二维函数图像：

这个矩形面积实质上是T(n)。

例2：二重循环，循环变量有所勾结

i=0的时候，内循环没有循环，i=1的时候，内循环一次，i=2,的时候，内循环两次，循环次数即T（n），属于是算数级数，大O记号下的话，等同于末项的平方，忽略常系数，便是O(n*n)。

它的函数图像：

面积是例子1的一半，但是从渐进分析的角度，二者是完全相同的，都是平方的量级。

例子3：

大步进在图像上相当于压缩横轴。其他的没什么好说的

例4：步进为加倍的二重循环

i<<=1 等同于i*=2; 具体为什么是几何级数，沿用之前的分析方法就知道了。

大O记号下与末项同阶O（2^log2(n-1)）=O(n-1)=O(n)。

二维图像如下：

有了复杂度分析的方法，紧接着我们看看实例，分析一下他们的复杂度。

对一些算法进行实操复杂度分析

例1：取非极端数：

这个问题，我们从子集里面随便抽三个数，因为是集合，里面每个数都是不同的。对这三个数判断谁最大谁最小，然后把中间值取出来即可，中间值必然是这个子集的非极端元素，自然也就是它的解了。

无论问题的规模即子集有多大，只需要三步就可以得到正确的输出，复杂度是常数级即O（1）.

例2：bubblesort 起泡排序：（正确性的证明）

这个排序算法，对一组无序的数列进行非降有序排列。无序的数组中呢，必然有某个相邻之间会存在一个逆序，通过扫描交换的方式，不断重复扫描，把发现的逆序进行交换，直到最后整个扫描都没有交换，那么排序完成。

这个扫描交换，用二重循环来实现，主循环是用于扫描，子循环用于交换逆序。（这个代码看的可真是舒服，不知道什么时候才可以有这种水平）。算法比较简单，就不细说了。这个算法的复杂度是如何呢？算法必然会结束,必然是正确的吗？

1.算法必然会结束。

对于上图给的无序数组例子可以看到，第一轮扫描交换之后，7 必然会被运送到数组的末尾位置，也就是说，一轮扫描交换之后会有一个元素被安置好。则我们会有这么一个 不变性:经过扫描k轮之后，必然有k个元素各就各位。

2.算法必然是正确的。

可以看到每轮扫描交换之后，会有某一个元素被安置好，被安置好了的那个元素，已经不需要处理了，相当于每轮扫描交换之后，算法的问题规模减1。则我们会有这么一个 单调性：经过扫描k轮之后，问题规模为n-k。

而算法之所以是正确的，让我们看一下边界条件即n=k。将其代入单调性和不变性的说法里面，扫描n轮之后，n个元素各就各位，问题规模变为0。

这就是为什么在算法分析的内容里面，讲到了，算法分析我们要关注算法的正确性，而正确性被单调性和不变性所决定。

3.起泡排序的复杂度：相当于一个几何级数,n,n-1,,,,,n-n，不懂的可以看前面关于循环的复杂度分析，画出二维图像的话是一个三角形，复杂度是 O（n^2）。

封底估算(Bcak of The Envelop Caculation)：

前面的内容，我们引进了大O记号，来进行一个定界的分析，可以比较直观的比较算法的优劣。实际工作工程中，定量的分析也很重要很常用，可以帮助我们具体的了解，不同的算法，不同的硬件，处理同一个问题的时候相应的时间成本。

我们要对时间有一个我们的概念，因为我们关注时间成本嘛：

一天 = 24 * 3600 ≈（放大） 25*4000=10^5 sec

1年 = 365*10^5 ≈ 3 * 10^7 sec

一世纪=100yr = 100 * 3*10^7 = 3 * 10^9 sec

"为祖国健康工作五十年" = 1.6 * 10^9 sec

“三生三世” = 300yr ≈10^10 sec

目前家用的PC，CPU一秒的主流处理次数是10^9 .

举例说明：

问题：对全国人口数据进行排序（十几亿人口看作10^9）,问题规模即n=10^9 .

mergesort 是归并排序，后续会讲，图中可以看出来算法的威力是显而易见的。封底估算，从这个实例也能看出来它的意义。

1-E 迭代与递归

之前的内容已经讲了如何分析迭代算法的复杂度，也就是应用级数求和的方法进行判断。接下来我们就需要关注递归算法。

这节我们要关注的问题是，在我们已经会评判算法复杂度前提下，要如何设计出高效的DSA。

这节的重点在于学会如何将大问题拆解为一个子问题，和平凡问题，也就是要学会减而治之（decrease and conquer)这一技巧。

下面举一例说明：

算法很简单，用于检验自己所学，从而分析算法的复杂度，并将分析方法推广到其他的DSA。

对时间复杂度，不难有Tn=1+n+1=O(n)。

空间复杂度，是累加器sum 和控制变量i ，也就是int sum 和 int i 。是常数复杂度O（1）。

回到代码本身，其中蕴含的设计策略是怎么样的呢？把输入n当作是问题的规模，当累加器执行一次加和的时候也就是循环一次，那么有一个数就被统计完毕了，相当于有效问题规模n-1.这种不断蚕食问题规模的算法策略，就是

减而治之（核心是有效问题规模的递减）

平凡的子问题，意思是可以直接求解而出，规模缩减的子问题和原问题的差别仅在于规模的缩减，其他和原问题无区别。把两个子问题治后再合并（相加）也就是原问题的解。

对数组求和写成递归的形式有：

对这个算法，我的个人理解：对 A[ n] 数组不断拆分为一个规模缩减的子问题和平凡问题，即sum(A,n-1) 和A[ n -1 ] ，同时不断递归的求解sum(A,n-1) ，最后不断地return 两个子问题的解的和就相当于是 “合”过程，当问题规模缩减的足够小，我们认为问题规模到达了递归基, 返回0.

递归基实际上解决了一个什么问题呢？,个人理解是使得函数在问题的有效规模为0的时候，使得递归结束，关于这点，在待会的例2数组倒置中会提及。

这样函数的调用就不是无限的。

那么这个递归算法的时间复杂度是多少呢？

这里要用到我们分析递归算法复杂度的第一个技巧：

递归跟踪（recursion trace)

简单来说，对于每个递归实例，我们可以通过列一个线性图表来表示整个递归过程（问题规模不断削减的过程，从n 变到最后 0）

如图所示，递归求解问题，生成子问题，直至问题规模变为0，抵达递归基，此时开始逐一返回。箭头表示了这一过程。

对于这个算法，它的时间复杂度取决于递归实例的数量，在看算法的时候我们要有一个直觉习惯：将sum(A,n-1) 这一项递归实例的语句给忽略掉。那么算法可以看成只负责返回一个平凡子问题，那么问题规模为n的时候不难知道递归实例的数量为n, 那么这个时间复杂度为O（n)。

也不难看出，递归跟踪（recursion trace)这种方法其实还是比较有限的，当递归的形式不那么简单的时候，不是什么sum(A,n-1)这种形式，甚至是极其复杂的时候。

为了应对更难的递归问题，接下来我们提出另一个方法：

递归方程

还是基于之前数组求和的例子来理解这个技巧。

可以理解为求解sum(A,n)的时间成本T（n），需要T（n-1)的时间求解sum(A,n-1) ，和O(1)的时间累加A[ n-1]；同时递归基的实例也要O（1）的时间。

由上述的分析有递推方程。现在的状态其实更像是一个亟待求解的隐式表达，像是求微分方程。把这一隐式表达和边界条件（递归基）联立起来，通常情况下便可以得到唯一的解，也就是显性的表达。

通过求解，我们也可以得到T（n)=O（n)

接下来再举一个例子来说明decrease and conquer ：数组倒置

递归版的算法如图所示。使用的策略是减而治之，原因就在于，每次做交换之后，会有两个组元被安放好，也就是有效的问题规模会每次减去2。同时，每次减去2的话不会改变数组本身元素个数的奇偶性，邓老师对此留了个思考题，问这个if语句隐含的else return这一递归基是否足以应对算法所需，原因又是什么。

要解答这个问题，就要理解什么是递归基

递归基的存在，就是给与递归一个停止的条件，是递归的边界。在有效问题规模被削减为0的时候，函数返回0值，递归停止。

可以看这个教程来理解。

回到例子本身，为什么老师说需要两个递归基，而if .......else return 0，这一个语句就可以满足呢？

假设有两个数组一个是奇数个的：[ 1,2,3 ] 一个是偶数个的[ 1, 2,3,4]。

奇数数组的递归基是什么？它有效问题规模最小的情况应该是只有一个元素的时候。对奇数数组做一个模拟运算看Lo和Hi的情况，不难发现，因为终止条件是LO<HI,当递归终止，问题的有效规模是是0，奇数数组抵达了它的递归基：只有一个元素。

同理，递归终止条件LO<HI 也可以使得在问题的有效规模缩减至0的时候，让偶数数组抵达它的递归基：0个元素。

这就是为什么邓老师说，他这样设置终止条件之后，可以满足两个递归基。

除了减而治之，还有一种算法策略:

分而治之（divide and conquer)

用数组求和的问题，举一个例子：

mi的计算用了右移计算符，值相当于是lo+hi/2^1。

效果如下，把lo,hi的问题不断对折，并把递归求解后的递归实例加和。

接下来我们要用递归追踪和递归方程来分析这一算法的时间复杂度，用数组[0,7] 举例，

递归追踪有：

那就相当于每层的总数加和，有一几何级数：

复杂度应为末项的同阶也就是底层的递归实例数，则有O(n）。也可以认为是，数组有多少个元素，复杂度就是多少。

递归方程

master theorem 大师定理（用于求解递归方程）

很多时候，求分而治之的递归方程的隐式表达在你熟练之后会比较简单。但是求解可能会成为一个困扰，对于这点，

对于上图的内容，这里面我们要关注两个式子的关系

他们之间的严格小于的情况，渐进的情况，严格大于的情况，会对应有不同的显式表达。

nlog 大于f(n)的情况：

nlog小于f(n)的情况：

nlog 渐进于f(n)的情况：

小结：

简单来说，谁大取谁。

这两个式作比较，谁大，时间复杂度就是谁。渐进的情况，主要是要记好表达式。

1-F动态规划

迭代和递归的区别

动态规划的定义：

动态规划是DSA设计和优化的重要手段，之前的课已经提到过，数据结构的学习，是一个螺旋式的，以前总是说“迭代乃人工，递归方神通”，那么我们现在要重视的是，如何将递归转化为迭代。动态规划就是这种编程思想的体现，我们会先通过递归，找出算法的本质，并且给出一个初步的解的时候，将其等效的转化为迭代的形式。

动态规划的意义（fib数列举例说明）：

那么，递归到底有什么不好呢，为什么非要用迭代呢？以下，我们将举例1：斐波那契数列有关的的程序去说明：

例1：求斐波那契数列第n项的数。

对于题目，写出递归形式的程序是:

这个程序只要理解了数列，不难写出。而这个程序在n比较大的时候，他的计算速度变得很慢，为了了解原因，我们肯定要分析这个递归的时间复杂度。

递推方程：

先根据复杂度，写出边界条件，和递归不断进行拆分的核心：。

整理有：

带入边界条件

当然，你自己算s(2) 、 s(3)的时候也吻合上面边界条件所得出的结果。有：

所以S（n）的复杂度和fib（n)划等号，所以S（n)的时间复杂度是

整理一下有T(n)：

做一个封底估算，让我们直观的了解一下这个递归程序的运行速度：

首先有T（5）的情况，要计算十次。

那么当我们计算第67项的时候有时间复杂度T(67)：

从上述的封底估算，我们可以了解递归的效率有时候是非常让人窒息的，毕竟DSA好不好最重要就是看快不快。

接下来我们用递归追踪的方式看一下，递归为什么这么慢。

递归追踪：

拿第五项来看：

递归低效的原因也就一目了然了，同时，递归除了大量重复调用导致时间复杂度惨不忍睹以外，由于它还会定义每一个递归实例，它的空间复杂度是O(n)，也十分的占据空间。

要优化程序，设计一个好的DSA，我们就要考虑如何减少不必要的重复调用。两个办法，一个是记忆法（memoization），还有一个是动态规划法（自底而上）。

动态规划思想（重点）：

前期铺垫很久了，现在才是重头戏。求解上到某一级楼梯，只能一次走一级或者走两级，要用多少种方法，其实就是斐波那契数列。这是因为，比如：当上到第六级楼梯的时候，在最后一步的时候，要么在第四级楼梯，走两级；要么在第五级楼梯的时候，走一级。这是契合斐波那契数列的，如果说递归是因为从顶到下而产生了许多不必要的调用，那么我们是否可以像走楼梯一样，自底而上的通过迭代的方式，不断更新我们每级要走的楼梯来求解这个问题呢？

思路：

设定初始的相邻的“阶梯”，较低的梯级 f 和较高的梯级 g，每次“爬楼梯”（迭代）将 f 和 g更新，并且最后输出较高的梯级 g

值得注意的是，这里你输入的n，是什么意思呢？n可以理解为你输入的你还要爬几级楼梯，如果输入n=3，意味着还要迭代三次，而因为你初设 f = 0 , g =1 也就是第0 级和第 1 级楼梯被设定好了，再爬三级，则是位于第五级会返回 g = 3。

PS：我自己更喜欢写成下面这个迭代形式，方便我自己理解的。

另一个动态规划策略的应用实例：求解最长公共子序列的长度。

简单介绍一下序列的相关概念：

所谓序列（sequenece),实质是由若干个字符构成的，比如下面这个computer.

而相对于序列，那就会由子序列（subsequenece)的概念，也就是从序列中随意挑出字符并按照原来的相对次序重新拼成一个序列，比如上图中C U T E 是computer的子序列,并且挑选出的字符和原序列的字符的连线，不存在交叉。

最长公共子序列：是相对于两个序列而言的。

对于最长公共子序列会有两种情况。

可能有多个情况：

这两个序列的最长公共序列是 D A T A & D A N A （T和N的连线交叉了，所以他们不能合并起来，要注意长度可不是5），并且是两个，即可能有多个。

可能有歧义：

子序列的来源不确定，有分歧。

以上的两种可能的情况，只是作为补充介绍，回到我们这个DSA，我们只需要求出最长的子序列的长度即可。依照设计优化算法的思路，我们应先用递归这一强有力的武器，得到一个正确的能工作的算法，再进行优化。

那么求解LCSlen递归的形式有：（仅供参考,自己按照题意大概写的）

LCSlen求解DSA（递归）


#include<stdio.h>
#include<string.h>
 
int LCS(char A[],int lena, char B[], int lenb);
int max(int a,int b){
	if(a>b)
		return a;
	if(b>a)
		return b;
}
	
int main(){
	int cnt;
	char A[]={"hello"};
	char B[]={"heeemmo"};
	int lena=strlen(A);
	int lenb= strlen(B);
	
	cnt = LCS(A,lena,B,lenb);
	printf("%d",cnt);
	return 0;
}
int LCS(char A[],int lena, char B[], int lenb){
	if(lena==0||lenb==0){
		return 0 ;
	}
	else if( A[lena-1]==B[lenb-1]){
		return  LCS(A,lena-1, B,lenb-1)+1;
	}
	else
		return max(LCS(A,lena,B,lenb - 1), LCS(A,lena-1,B,lenb));
}

对于这个递归，它的时间复杂度也是指数级的，想更了解可以看课。

关于如何用动态规划求出LCS的length，这个我看老师的课我其实没看懂，不过看了这个视频之后我就明白原理了：LCS-动态规划

以下是求length的自底而上的代码。

LCSlen求解DSA（动态规划）


#include<stdio.h>
#include<string.h>
int LCSlen(char A[],int lena,char B[],int lenb);
int max(int a, int b);
 
int main(){
	char A[]={"BDCABA"};
	char B[]={"ABCBDAB"};
	int lena=strlen(A);
	int lenb= strlen(B);
	int output;
	
	output=LCSlen(A,lena,B,lenb);
	printf("%d",output);
	return 0;
}
 
int LCSlen(char A[],int lena,char B[],int lenb){
	int i,j;
   //定义一个二维数组，并且初始化
	int c[lenb+1][lena+1];
	for(i=0;i<=lenb;i++){
		for(j=0;j<=lena;j++){
			c[i][j]=0;
		}
	}
//应用填表的逻辑，字符数组相同的时候要如何，不同的时候要如何
	for(i=1;i<=lenb;i++)
		for(j=1;j<=lena;j++){
			if(B[i-1]==A[j-1]){
				c[i][j]=c[i-1][j-1]+1;
			}
			else 
				c[i][j]=max(c[i-1][j],c[i][j-1]);
		}
	int ret = c[lenb][lena];
	//下面是调试用的代码，可以输出整张表 。 
	/*for(i=0;i<=lenb;i++){
		for(j=0;j<=lena;j++){
			printf("%d ",c[i][j]);
		}
		printf("\n");
	}*/
	return ret;
}
int max(int a, int b){
	if(a>=b){
		return a;
	}
	else
		return b;
}

代码的核心思路就是视频的填表的思路。看懂视频就可以看懂我的代码。

我们要有一个二维数组去存放数值，但是要注意二维数组的行数和列数，上图这个表的二维数组是 八行七列，而不是七行六列 .

这个DSA的时间复杂度就是这个图表的面积是 O（m*n)

1-XA 缓存 cache

这节课我感觉只能算是一个扩展的内容，以循环移位这个问题来作为引子。给出两种解法，一种是非蛮力的迭代的方式，并且时间复杂度为O(1.5n）；另一种是倒置法时间复杂度是O(3n)。而在应用实际中，倒置法的虽然时间复杂度大，但是由于cache的机制，它的速度会比迭代的方式快特别多。用这个问题，讲述了编程的时候也要注意访问数据的次序，尽量让其紧邻。

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/1019437

绪论（数据结构-邓俊辉）_邓俊辉数据结构

1-A计算

算法的基本要素：

计算和算法的关系

引入度量的尺子和刻度

1-B计算模型（尺子）

①如何度量单个算法

②涉及多个算法的时候，如何比较？

如何用好这些尺子，有何技巧，有何技巧。

1-C大o记号（定义直尺刻度）