我们在编写程序的时候往往需要寻找最为合适的算法来解决特定问题，怎么衡量一个算法是合适的算法呢？
我们来举个例子：
有两个Coder，小灰和大黄，用各自的代码实现了同一个功能。
小灰使用的算法运行一次需100分钟，占用10MB内存；
大黄使用的算法运行需100毫秒，占用10KB内存。
显然大黄的代码不但运行速度快，而且节省空间，他所采用的算法是最为合适的。
从上面的例子可以看出，检验一个算法是否适合主要取决于两个条件，一个是算法运行所消耗的时间长短，一个是算法运行所占用的内存大小。
一个算法运行需要花费多长时间，占用多少内存，不只是取决于算法本身，也取决于运行算法的计算机硬件配置，以及算法所要处理的数据量。
我们在老旧的个人电脑上运行一段程序和在最新的超级计算机上运行一段程序，所花费的时间肯定是不一样的。
我们处理1MB的数据和处理1TB的数据，所占用的内存空间也是不一样的。
既然如此，我们怎么能检验算法本身的快慢和占用的空间呢？
这里就引入检验算法的重要指标：
- 时间复杂度
- 空间复杂度
时间复杂度
并不是一个明确的执行时间，而是一个函数。
这个函数描述了某种算法随着输入数据量的提升，执行时间随之上升的幅度。
可能这样说有些抽象，我们列举一些生活中的场景，来做一个简单的类比：
- 10寸长的面包，每三天吃掉一寸，几天吃完？ 答案是：3X10 = 30天 。如果用函数来表述这个相对时间：T(n) = 3n
- 16寸长的面包，每五天吃掉剩余长度的一半，几天吃完？ 答案是： 5Xlog16 = 5X4 = 20天。 记作：T(n) = 5logn
- 10寸长的面包和一个鸡腿，每两天吃掉一个鸡腿，几天吃完鸡腿？ 答案自然是：2天。记作：T(n) = 2
像T(n)这样的函数，既可以统计吃面包的时间，也可以统计计算机程序的相对执行时间，有了函数T(n)，是否就可以分析和比较一段代码的运行时间了呢？
还是有一定困难的，比如算法A的相对时间是T(n) = 100n，而算法B的相对时间是T(n)=5n^2，这两个到底谁的运行时间更长一些？
这就要看n的取值了，为了能够更准确地做出判断，计算机科学家发明了一个重要概念，叫作渐进时间复杂度，简称时间复杂度。
时间复杂度的官方定义：
若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度。
时间复杂度用大写O来表示，所以也被称为大O表示法。
如何推导出时间复杂度：
- 如果运行时间是常数量级，用常数1表示
- 只保留时间函数中的最高阶项
- 如果最高阶项存在，则省去最高阶项前面的系数
时间复杂度的比较：
O(1) < O(logn) < O(n) < O(n²)
空间复杂度
如果说时间复杂度是衡量算法执行的时间成本，那么空间复杂度就是衡量算法执行的空间成本。
为什么算法要占用额外的存储空间：
因为在运行一段程序的时候，我们不止要执行各种运算指令，同时也会根据需求存储一些临时的中间数据，以便后续指令可以更方便地继续执行。
什么是空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，使用大O表示法。
程序占用空间大小的计算公式记作S(n)=O(f(n))，其中n为问题的规模，f(n)为算法所占存储空间的函数。
常见的空间复杂度
- 常量空间O(1)：算法的存储空间大小分配固定和输入规模没有直接关系的情况
- 线性空间O(n)：算法分配的空间是一个线性的集合并且集合大小和输入规模n成正比
- 二维空间O(n²)：算法分配的空间是一个二维数组集合并且集合的长度与宽度都和输入规模n成正比
- 递归空间O(n)：所需的内存空间和递归的深度成正比
时间和空间的取舍
- 时间换空间(回溯法)
- 空间换时间(字典法)