前言

上一章中，主要学习可数据结构的基本概念，但是
程序 = 数据结构 + 算法
因此，这一节就来了解算法是个什么玩意。

算法的基本概念

1.算法定义
解决某个问题的具体步骤
2.算法的特性

• 输入
  有0个或者多个输入
• 输出
  至少一个输出
• 有穷性
  有限的步骤执行完毕
• 确定性
  每一个步骤都是确定的，不会产生歧义
• 可行性
  每一步都是可行的，执行有限次数能完成

3.算法时间复杂度的定义
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。
算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。其中f(n)为n的某个函数。

用大写O()来体现时间复杂度，成为大O记法

4.时间复杂度的分析方法
也称为推导大O阶方法

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
这样得到的结果就是大O阶

• 常数阶
  无论顺序结构的代码还是分支结构的代码，其时间复杂度都是O(1).
• 线性阶
  关键就是要分析循环结构的时间复杂度，
  一重循环时间复杂度为O(n)
• 对数阶

int count = 1;
while (count < n)
{
  count = count * 2;
}

由于每次count乘以2以后，就距离n更近了。也就是说，有多少个2相乘后大于n，就会退出循环，由2^x=n,x=log2n,
则时间复杂度为O(logn).

• 平方阶
  双重循环的时间复杂度为O(n^2)
  如果外循环改完m，那么时间复杂度就是O(n*m).

算法的空间复杂度
就是算法所需要的存储空间。
记作：S(n) = O(f(n));其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。