上一节我们聊了一下数据结构的基本概念，今天我们聊聊算法的相关的知识。同样，开始之前我们先思考以下几个问题：
什么是算法？
算法有哪些基本特征？
如何衡量一个好的算法？
算法的基本特性
有一句话几乎成了计算机行业的公知，那就是“程序=数据结构+算法”，先不辩驳这句话的正确与否，至少体现了数据结构与算法在这个行业的重要性。
我们通过一个例子来阐明算法的基本特性，不知道大家小时候有没有搬过砖，农村自家造房子，为了节约成本，通常通常吆喝自家的小孩一块，把砖搬到师傅砌墙的地方(好像暴露年龄了)。假如，早上小明他爸跟他说，把门口的砖搬到二楼，今天师傅砌墙要用。那么小明把所有的砖搬到二楼的过程就相当于一个算法的实现，眼前的一堆砖相当于输入数据，搬到二楼师傅砌墙的地方地砖相当于输出数据（算法是对特定问题求解步骤的一种描述，是指令的有限序列）。现在有以下几种情况出现：
小明同一块砖头反反复复搬到楼上又搬下来，被他爸发现揍了他一顿，因为小明这样没法完成搬砖的任务（违反了算法的有穷性，必须在有限步骤结束）
小明搬砖的思路千奇百怪，一会砖头放在隔壁二婶家，一会又藏在对面三叔家，他爸发现又揍了他一顿，因为他搬砖的位置不明确。（违反了算法的确定性，算法实现的每一个步骤不能存在歧义，相同的输入输出必须相同）
他爸想让小明早点把砖头搬完，于是和小明说，小明你给我一次搬30块，小明怒了“你大爷的你来”，根本不可能一次搬这么多。于是小明又被揍了，（违反了算法的可行性，一个算法描述的操作必须是可以实现的）
搬砖的时候，小明把隔壁的小花叫来说，你看我力气可大了，手里搬着几块砖头在小花面前秀，不利索的搬到二楼。被他爸发现又被揍了（违反了算法的输出，一个算法必须有一个以上的输出）
为了节省成本小明他爸和小明说，你直接去砖厂把砖搬回来吧，今天就不把砖拉到门口了，能节省拉砖头的钱，这就是零输入程序（算法的输入，算法可以有零个或多个输入）
以上便是一个算法五个重要特性。
算法设计的要求
为了以后搬砖顺利，小明他爸让小明先说说搬砖的方法，并给他提了几点要求：
必须把砖搬到正确的位置（算法的正确性，能够解决具体的问题）
搬砖的方法必须描述清楚，容易理解（算法的可读性，要易于理解）
搬砖的时候要注意安全戴好安全帽，防止小石子掉下来（算法的健壮性，具备处理非法数据的能力）
最好能够想个轻松又高效的法子把砖搬完（算法的时间复杂度和空间复杂度要求）
算法的时间复杂度分析
于是小明开始巴拉巴拉的说怎么实现高效轻松的搬砖，小明他爸根据小明描述的搬砖过程，评估搬砖需要的时间以及搬砖需要工具。这便是算法中的时间复杂度和空间复杂度分析。
说完了基本概念，来看看一个具体的搬砖例子，如下所示：
intmain(){MovingBricks();}voidMovingBricks(intn){inti=1;//已搬砖的块数while(i=n){printf("搬第%d块砖",i);i++;//每搬完一块砖+1}}
现在我们分析一下搬砖程序执行的次数
inti=1;//执行一次while(i=n);//执行次printf("搬第%d块砖",i);//执行次i++;//执行次
//时间开销为T(n)=1++2*
//因此时间复杂度为T(n)=1+(n+1)+2*n
我们假设小明吃了大力，每次搬砖的能力都是上一次两倍。搬砖程序如下所示：
intmain(){MovingBricks();}voidMovingBricks2(intn){inti=1;//每次搬砖的块数ints=0;//已搬砖的总数while(s=n){printf("搬第%d块砖",i);s=s+i;//每搬完一次+ii=i*2;//大力出奇迹}}
我们再分析一下这个搬砖程序执行次数
inti=1;//执行一次ints=0;//执行一次while(i=n);//执行?log2(+1)?+1次
printf("搬第%d块砖",i);//执行?log2(+1)?次
s=s+i;//执行?log2(+1)?次
i=i*2;//执行?log2(+1)?次
//时间开销为T(n)=2+?log2(+1)?+1+3*?log2(+1)?
//因此时间复杂度为T(n)=2+?log2(n+1)?+1+3*?log2(n+1)?
看上面的分析过程是不是感觉有点复杂，不过实际分析我们只考虑阶数高的部分，比如在MovingBricks中T(n)=*n+2，我们通常只考虑T(n)=*n，进一步去掉前面的常数项可得时间复杂度为T(n)=O(n)，相应的MovingBricks2中T(n)=O(log2(n))，一个程序的时间复杂度具有以下规则：
//多项相加，只保留最高阶项T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)));//多项相乘，都保留T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n));
常见时间复杂度大小关系：
算法的空间复杂度分析
我们都知道程序在执行的过程中需要占用一定的内存，除了程序本身所占有的内存之外，还需要保存一些程序执行过程中产生的中间数据，比如局部变量，函数调用信息等，以保证程序的正确执行，如下图所示。
我们再回到上面的搬砖程序，如下所示：
intmain(){MovingBricks();}voidMovingBricks(intn){inti=1;//已搬砖的块数while(i=n){printf("搬第%d块砖",i);i++;//每搬完一块砖+1}}
从上面的例子我们可以看出程序在执行过程中，只需额外申请一个局部变量，且这个变量占有的内存和输入值n无关。由此可以得出，该程序空间复杂度为S(n)=O(1)，表示方法同时间复杂度，这里不再赘述。
看看另外一个例子，假设小明吃了大力，大力出奇迹，不论你有多少砖他都能一次给你整完，具体程序如下：
intmain(){MovingBricks();}voidMovingBricks(intn){int*s=(*int)malloc(sizeof(int)*n);//搬砖的块数printf("搬砖结束");}
上面的程序我们可以发现，程序占用的内存和输入参数有关，按照时间复杂度分析的方法我们可以得出该程序空间复杂度为S(n)=O(n)，空间复杂度的分析和时间复杂度类似，因此计算时间复杂度的规则同样也适用于空间复杂的分析。
再看一个例子??假设小明要和隔壁小花表白，为了表现作为一个程序员的气质，他写了一段代码，程序和内存分布如下所示：
intmain(){LoveYou(5);}voidLoveYou(intn){if(n1){LoveYou(n-1);}printf("Iloveyou%d",n);}
我们可以看出上面的程序在不断的套娃，直到n1的时候，套娃结束，数数套娃的次数可以得出其空间复杂度，为S(n)=O(n)假如小明的电脑内存不够大，而输入参数n比较大时，由于层层的套娃，而每一次套娃都会占用一定的内存，这样就可能导致内存不足，程序无法正常执行，小明表白失败。因此我们在写程序的时候特别是使用递归(套娃)的时候要慎重考虑内存消耗问题。
衡量一个好的算法
一个好的算法是时间复杂度和空间复杂度的综合考虑，不能一味地追求时间上的高效忽略内存消耗，也不能为了节省内存而过多的牺牲时间。当空间复杂度一定的情况下，时间复杂度越低（可参考前面的大小关系），则该算法越高效。
总结
参考文献及图片引用出处
[1]数据结构：C语言版.严蔚敏等.北京：清华大学出版社，
[2]数据结构考研复习指导：王道论坛.电子工业出版社
[3]算法与数据结构：极客时间
预览时标签不可点收录于话题#个上一篇下一篇