# 算法
此为数据结构篇章的算法介绍篇，不会深入学习。
毕竟程序设计 = 数据结构 + 算法。
# 算法定义
算法: 解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
# 比较两种算法
题目: 求1+2+3+·······+100的结果。
大多数人的写法如下:
int i, sum = 0, n = 100;
for (i = 1; i <= n; i++) {
sum = sum + i;
}
printf("%d", sum);
第二种高斯的算法如下:
int i, sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);
第一种算法需要执行100次才能得到结果，而第二种只需1次。
假设加到10万，第一种算法需要10万次，而第二种还是只需要1次，算法的意义就在于此。
# 算法的特性
算法具有五个基本特性: 输入、输出、有穷性、确定性和可行性。
# 输入输出
输入和输出比较好理解。
算法具有零个或多个输出，绝大多数的算法输入参数都是必要的。
算法至少有一个或多个输出，算法一定需要输出的，否则要这个算法干嘛？
# 有穷性
有穷性: 指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
否则一个算法，死循环一直算，没有个边界，那就没有意义了。
# 确定性
确定性: 算法的每一步骤都具有确定的含义，不会出现二义性。
算法在一定条件下，只有一条执行路径，相同的输出只能有唯一的输出结果。
算法的每个步骤被精准定义而无歧义。
# 可行性
可行性: 算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。
# 算法的设计要求
好的算法应该具有正确性、可读性、健壮性、高效率和低存储量的特征。
# 正确性
正确性: 指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
算法的正确性大致有以下四个层次:
- 算法程序没有语法错误
- 算法程序对于合法的输入数据能够产生满足要求的输出结果
- 算法程序对于非法输入数据能够得出满足规格说明的结果
- 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
层次1要求最低，算不上好算法，而层次4最困难，几乎不可能逐一验证所有的输入都能得到正确结果。
所以一般情况下，满足层次3即可作为一个算法是否正确的标准。
# 可读性
可读性: 算法设计的另一目的是为了便于阅读、理解和交流。
我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了自己都不知道写了些什么。
可读性是算法好坏很重要的标志。
# 健壮性
健壮性: 当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。
彩蛋
在《编写可维护的JavaScript》一书中提到: 程序是给人读的，只是偶尔让计算机执行一下
# 时间效率高和存储量低
好的算法还应该具备时间效率高和存储量低的特点。
时间效率: 指算法的执行时间，同一个问题，如果多个算法能够解决，执行时间短的算法效率高，时间长的效率低。
存储量: 指算法在执行过程中需要的最大存储空间（运行时占用的内存或外部硬盘存储空间）越低越好。
设计算法应该尽量满足时间效率高和存储量低的需求。
# 算法效率的度量方法
设计算法要提高效率，这里的效率主要指算法的执行时间。
# 事后统计方法
事后统计方法: 这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
但是这个方法有很大缺陷:
- 必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法，不是竹篮打水一场空吗？
- 时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。老电脑和现在最新的电脑在处理算法的运算速度上，是不能相提并论的，就算同一台机器，cpu使用率和内存的占有率不同也会造成细微的差异。
- 算法的测试数据设计苦难，并且程序运行时间往往还与测试数据的规模有很大关系。
基于事后统计方法有以上缺陷，一般不予考虑此方法。
# 事前分析估算方法
事前分析估算方法: 在计算机程序编制前，依据统计方法对算法进行估算。
一般高级程序语言在计算机上运行时所消耗的时间取决于下列因素:
- 算法采用的策略、方法
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
第1条当然是算法好坏的根本，第2条需要软件支持，第4条需要看硬件性能。
抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题输入的规模。
所谓的问题输入规模是指输入量的多少。
最终，在分析程序的运行时间时，最重要的是把程序看成独立于程序设计语言的算法或一系列步骤。
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项(最高阶项)的阶数。
# 算法时间的复杂度
# 定义
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记住: T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
一般用大写的O()来表示算法时间复杂度的记法，我们称之为大O记法。
# 推导大O阶方法
以下是推导大O阶的方法:
推导大O阶:
* 用常数1取代运行时间中的所有加法常数
* 在修改后的运行次数函数中，只保留最高阶项
* 如果最高阶项存在且不是1，则去除与这个项相乘的常数
得到的结果就是大O阶。
# 常见的时间复杂度
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | o(n) | 线性阶 |
| 3n²+2n+1 | O(n²) | 平方阶 |
| 5log2(n)+20 | o(logn) | 对数阶 |
| 2n+3nlog2(n)+19 | o(nlogn) | nlogn阶 |
| 6n³+2n²+3n+4 | O(n³) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
时间复杂度所耗费的时间从小到大依次是:
O(1) < O(logn) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)
# 最坏情况与平均情况
最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。
一般没有特殊说明的情况下，都是指最坏的时间复杂度。
# 算法空间复杂度
写代码时，完全是可以通过空间来换取时间，只是看你如何权衡。
算法的空间复杂度通过计算算法所需的存储空间实现。
算法空间复杂度的计算公式记作: S(n)= O(f(n))。
其中，O为问题的规模，f(n)为语句关于n所占存储空间的函数。
若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。