【数据结构笔记】什么样的算法才是好的算法？

什么是程序算法？

用程序解决实际问题的方法。一个问题，有多种解法，每种解法最终得到的结果都相同，可是，每种解法实现的过程使用的时间和资源是不同的。

什么是好的程序算法？

第一步，保证准确性。黑猫白猫，能抓到老鼠的都是好猫。首先，最基本的得保证程序能基本解决当前问题。

第二步，保证健壮性。程序能面对各种测试而依旧保持程序的准确性。

第三步，保证程序效率。一方面要尽可能缩短程序算法执行时间（时间复杂度），另一方面要尽可能保证程序占用尽可能少的资源（空间复杂度）。综合起来，考虑时间复杂度的同时也得考虑空间复杂度，往往两者不可兼得，视实际情况进行合理地取舍。

一个程序算法同时满足这三点应该就可以称为一个好的程序算法了。要达到每一点都需要经过很多积累与练习，每天进步一点点，加油！

时间复杂度

时间复杂度在数据结构与算法这门课中是一个很重要的概念。时间复杂度的官方定义为：

算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

通俗的说，时间复杂度主要看算法中的频度。频度是算法中使用到的循环结构中代码循环的次数。时间复杂度表示方式为：O（频度），简称大“O”计法。例子：

(1)++x; s=0;
(2) for (int i=1; i<=n; i++) { ++x; s+=x; }
(3) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }

（1）的时间复杂度为：O(1)

（2）的时间复杂度为：O(n)

（3）的时间复杂度为：O(n²)

若(1)、(2)、(3)组成一段程序，那么算法的时间复杂度为：O(n²+n+1)，可进行简化。简化的过程总结为3步：

【第一步】去掉运行时间中的所有加法常数。（例如n²+n+1，直接变为n²+n）

【第二步】只保留最高项。（n²+n变成n²）

【第三步】如果最高项存在但是系数不是1，去掉系数。（n²系数为1）

所以，最终1、2和3合并而成的代码的时间复杂度为O(n²)。

常见的时间复杂度

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

时间复杂度和空间复杂度转换

以空间换取时间：谷歌浏览器相比于其他的浏览器，运行速度要快。是因为它占用了更多的内存空间，以空间换取了时间。

例如判断某个年份是否为闰年时，如果想以时间换取空间，算法思路就是：当给定一个年份时，判断该年份是否能被4或者400整除，如果可以，就是闰年。

如果想以空间换时间的话，判断闰年的思路就是：把所有的年份先判断出来，存储在数组中（年份和数组下标对应），如果是闰年，数组值是1，否则是0；当需要判断某年是否为闰年时，直接看对应的数组值是1还是0，不用计算就可以马上知道。

资料：C语言中文网、百度百科、《数据结构与算法分析》

往期精彩推荐

关注公众号获取更多资源分享！

后台回复：C101，获取【入门C语言最好的书籍】

后台回复：C000，获取【热门C语言电子书】

后台回复：CV001，获取【郝斌C语言教程视频】

后台回复：CV000，获取【热门C语言视频教程】

后台回复：py100，获取【Python电子书】

后台回复：py001，获取【第一本python入门书】

后台回复：天气预报，获取【天气预报项目源码】

后台回复：py007，获取【机器学习视频教程】

后台回复：py006，获取【Python自动化测试教程】

后台回复：py005，获取【人工智能图像处理视频教程】

后台回复：py004，获取【Python人工智能视频教程】

后台回复：py003，获取【Python入门与进阶视频教程】

后台回复：py002，获取【机器学习经典算法视频教程】