1.2 算法的基本概念和算法评估

本篇内容主要是算法的基本概念和算法评估的方法，话不多说，上正文。

什么是算法？

俗话说得好“程序=数据结构+算法”！那什么是算法呢？算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，是计算机操作指令的集合。数据结构的作用是将数据信息化并实现对数据的基本操作；算法则是使用已经实现的数据操作，处理数据并解决问题的步骤或方案，任何算法都是为了解决问题而存在的。

算法的要素

一个算法需要以下五个要素

• 输入：一个算法需要0个或多个输入，多个输入很好理解，多个参数嘛，0个输入也很好理解，一个printf操作需要个鬼的输入[doge]
• 输出：一个或多个输出，算法嘛，最后总要有个计算结果出来，没有结果的佛系算法emmmm出门右转好吧
• 有穷性：包括两个方面，第一算法的步骤要有穷，一个执行不完的算法，我找谁要结果？第二算法执行的时间要有穷，想一想一个算法跑了两百年没跑完……emmmm算法测试完成日，家祭无忘告乃翁。敲黑板，虽然算法要有穷，但是程序可以是无穷的，比如服务器程序又或者一些while(true)
• 确定性：算法的每一条指令的含义必须清晰，不存在二义性。同样是一句话“这周日你有空吗？”理解错了你就凉了好吧
• 可行性：算法中所有的操作都可以通过已经实现的基本运算执行有限次完成。搞一个现在还没办法实现的算法出来，概念算法嘛？算法是解决实际问题的。

好的算法的特质

• 正确性：算法要能正确的解决问题
• 可读性：算法要有良好的可读性，帮助人的理解，重要的是无歧义的描述算法的步骤
• 健壮性：出现非法的数据输入时，算法能适当的反应和处理，不会有奇奇怪怪的输出
• 高效率和低存储量需求：执行速度快，时间复杂度低；不占用过多内存，空间复杂度低，执行时间长了用户受不了，存储占用高了成本受不了

谈下一话题，算法的评估。

算法的评估

算法的评估主要两个方面，时间复杂度和空间复杂度。
时间复杂度
计算时间复杂度是一个实践性的东西，详细的计算方法网上太多了，我就不再写一遍了，直接给总结的内容

• 时间复杂度就是讨论指令执行次数与问题规模n之间的关系
• 如果计算所得只有常数项则时间复杂度为O(1)
• 如果存在n或n的高阶项，则舍弃常数项
• 在n的相关项中只保留最高阶项
• 将最高阶项的系数化为1

关于时间复杂度的大小比较（上图标红部分）
O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
总是分不清几个复杂度关系，提供两种办法
数学证明

log₂n为n的高阶无穷小，也就是说，当n→∞，n的增长速度比log₂n更快。

画图

空间复杂度
空间复杂度的计算方式与时间复杂度类似 上图

• 依据上图而言，对于普通程序，只需要关注程序执行中的变量所占用的空间和问题规模n之间的关系
• • 当变量所占空间固定，与问题规模无关时，变量所占空间会改变表达式中的常数项，只有变量空间与而当问题规模n相关时（如声明一个长度为n的数组）才纳入空间复杂度的考虑范围，比如一维数组空间复杂度为n，二维数组空间复杂度为n²等
• 当计算递归程序的空间复杂度时，结合空间占用和问题规模n之间的关系，考虑递归调用的次数即可

本篇完