现在我们知道了什么是算法
下一个问题就是：什么是好的算法
解决同一个问题的时候，我们通常会有很多种不一样的算法
区别就在于，有的算法比较笨，有的算法比较聪明
那我们怎么去衡量它们谁好谁坏呢？我们通常有下面的两个指标
一个是“空间复杂度”，我们把它记成S(n)，就是“Space"
它是根据算法写成的程序在执行的时候”占用存储单元的长度“
另外一个指标叫“时间复杂度”，T(n)，也就是“Time"的缩写
就是根据算法写成的程序在执行的时候“耗费时间的长度”
为什么要把它们写成是一个 n 的函数呢？
因为这两个指标，其实跟我们要处理的数据的规模，是直接相关的
举个例子说，我如果让你打印十个整数
你那个程序可能瞬间就给出结果了
如果我让你打印十万个整数呢？你就要多等一会儿了
所以这个程序运行的时间，跟我要你处理的数据是十个还是十万个
跟这件事情是相关的
这个“十”或者“十万”，就是我们要处理的数据的规模
我们把它叫做 n，是一个变量的话
那么我们这个程序所用的时间和空间都跟这个 n 是有直接关系的
解决一个问题有很多种不同的方法
你在设计这个方法的时候，一定要把这两个要素考虑清楚
一不小心，如果空间复杂度太大的话
呃…… 你那个程序可能就直接爆掉了，非正常中断
一会儿我们会来具体地看一个例子
时间复杂度如果太大的话，你就可能等了太长的时间都等不出结果
有可能等到世界末日的时候，你仍然等不到这个结果
那接下来我们来看两个例子
这个例子是我们在前面看过的一个
就是打印 N 个整数的，递归写出来的那个程序
我们说递归的这个程序在运行 N 等于十万的时候
在我的机器上它就非正常跳出了
到底发生了什么事情呢？我们这儿来仔细地看一下
假设在内存里面我们有这么一块空间，是这个程序可以用的
我们开始调用这个PrintN，然后把100000作为参数传给它
这个时候程序做了一件什么事情呢？
这个 N 传进来，它判断了一下，这个 N 不得零
于是它递归调用PrintN，传进去的参数是99999
调用这个函数之前
你的系统需要把当前的这个函数所有的现有的状态
都存存存……存到系统内存的某一个地方
我在这儿写十万，并不是说它占了十万个格
而是说这块空间是为了PrintN(100000)这个程序而存储的
把它当前状态先存下来，然后我们再去执行PrintN(N-1)这个函数
执行完了以后，系统会把这些存储的状态再恢复回来
接着执行这个函数的下一句
因为它是个递归调用的，于是这个情况就变成了什么？
下一步我们要调用PrintN(99999)
然后进去以后我们发现先得调用PrintN(99998)
于是这个程序所有的变量要被存一下
然后我们调用PrintN(99998)
然后继续存，继续存……
一直到最后什么时候可以返回了呢？
到我们调用PrintN(0)的时候，可以返回
那么在调用PrintN(0)之前呢，我们必定调用了PrintN(1)
所以最后存在系统里面的一块内容，应该是PrintN(1)这个函数所有的当前的状态
于是我们就发现，它在内存里面占用的空间的数量
实际上是跟我这个原始的 N 的大小成正比的
也就是说空间复杂度做为一个 N 的函数的话，是一个常数乘以 N
也就是说随着 N 来做线性增长
当这个 N 非常非常大的时候，你的程序可以用的空间是有限的
它把它有限的空间用爆掉了，所以它就非正常退出了
那我们再去回想一下，那个循环实现的程序它有没有这个问题呢？
在那个程序里面，它只用了临时变量和一个for循环
它没有涉及到任何程序调用的问题
所以不管那个 N 有多大，它占用的空间始终都是一个固定的
它占用的空间的量不会随着 N 的增长而增长
所以它的空间占用始终是一个常量。所以它永远是没问题的
而这个递归函数就会是有问题的
接下来的一个例子呢，我们再回顾一下，前面说“求多项式的值”
我们说有一个函数特别傻，有一个函数很聪明
而事实上我们转了一下，也发现第二个函数比第一个函数快很多
那么具体为什么会这样呢？
在分析一个函数运行效率的时候
在一个这么简单的函数里面，因为它只有加减乘除嘛
机器运算加减法的速度比乘除法的速度要快很多
所以我们基本上就是在数函数到底做了多少次乘除法
加减法可以忽略不计
那我们现在就来具体地数一下，它到底做了多少次乘法
先来看第一个函数
第一个函数看上去我们只看到了一个乘号
这一个乘号出现在一个for循环里面，这个for循环一共执行了n次
但是不要忘了这个pow函数，这个算的是 x 的 i 次方
用一个简单计算累乘的方法的话，我们算 x 的 i 次方要做几次乘法呢？
(i-1)次，对不对？
然后再加上这一次跟前面的系数相乘
所以呢，每一次循环里面执行的是 i 次乘法
于是乘法的总次数就是从 1 一直加到 n
最后就得到 (n^2+n)/2 这么多次乘法
那我们再来看第二个程序，第二个程序就简单多了
第二个程序里面真的是，每一个循环里面就只有 1 次乘法
一共执行了 n 次循环，所以非常简单，我们一共只做了 n 次乘法
所以当我们用时间复杂度这个概念去描述它的时候呢，我们会说
第一个函数它的时间复杂度作为 n 的函数，是一个常数乘以 n 平方，加上另一个常数乘以 n
而对第二个函数来说，它的时间复杂度应该就是一个常数乘以 n
好了我们仔细来看一下，这两个函数的比较
虽然常数C1、C2和C到底是什么
这个其实每台机器上跑起来可能都不太一样
但是，不管这三个常数是什么
我们知道当 n 充分大的时候，当 n 很大很大的时候
那个 n 平方，它其实是远远超过了 n 的
这就意味着当 n 很大的时候，第二个程序一定会跑得比第一个程序快很多很多
我们之前只试验了 n 等于9的时候
你试一下90？试一下1000？会怎么样？
继续回到我们那个关于“什么是好算法”这个话题上来哈
一般来说我们在分析算法的效率的时候，通常关心的是下面两种复杂度
一个是”最坏情况的复杂度“
我们给T加一个下标叫worst，就是“最坏情况”
另外一个我们叫“平均复杂度”
是一个average，缩写成avg，给T加这么一个下标
那么很显然地我们知道，平均复杂度肯定是比最坏情况复杂度要小
但是我们在分析的时候，比较喜欢分析的是这个最坏情况复杂度
为什么呢？因为什么叫“平均”经常不是一个很容易搞定的问题
所以呢，分析这个平均复杂度会非常之难
我们拣容易的做，我们最关心的就是最坏情况复杂度