算法好坏怎么判断？快不快、省不省，测试跑一跑有局限

回答这个问题之前，我们先来看下，什么是算法？

我们先来看下百度百科的定义：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

用我们听的懂的话来说，算法其实就是一段的代码。通常我们用这段代码来处理大规模的数据。既然是用来的处理大规模数据的代码，那要评判一个算法的好坏，当然就是要看这个算法执行的快不快，算法在执行过程中使用的空间省不省。

因此我们再回到刚刚这个问题，如何判断一个算法的好坏？也就意味着，如何判断这个算法运行的快不快？如何判断这个算法使用的空间省不省？

有人会说，这难道还不简单吗？快不快，省不省，测试环境跑一跑就知道了啊。确实，测试环境跑一跑的确能够通过监控来获取算法执行的时间和占用的内存大小。但是这种跑一跑的方法有很大的局限性。

首先，测试环境执行算法的结果依赖于测试环境的配置。测试环境的各类硬件设备都可能影响测试结果，比如 CPU、内存、网络、存储等等。

其次， 测试结果受数据规模的影响很大。比如有些算法，它的执行效率随着数据规模呈指数级的下降，如果你只是拿小批量的数据去测试，然后得出了这个算法执行效率非常好的结论，那显然是不适合的。

因此我们需要一种可以不依赖物理环境，可以粗略的估算出算法执行效率的方法，也就是我们今天要聊的时间、空间复杂度分析方法。

时间复杂度分析方法用来分析算法快不快。空间复杂度分析方法用来分析算法省不省。

时间复杂度分析

既然算法就是一段代码，那么我们通过分析代码的复杂度，就自然能够得出算法的复杂度。我们通过一些例子来看一下，代码的时间复杂度怎么分析：

例1：

void count(){

int a = 1;

int b = 2;

int sum = a + b;

这段代码只有 3 行，每行执行一次。因为只是要粗略的估算代码的执行时间，因此我们假设：屏蔽掉硬件的影响，每行代码执行的时间都是相同的，都为1个时间单位。那么基于这个假设，上面这段代码的执行时间就为3*。

例2：

void count(){

int sum = 0;

for(int i = 0;isum = sum + i;

我们可以看到这段代码中，第一行代码只执行了一次，执行时间为1*。而第二行、第三行代码是一个循环，需要循环1000次，因此第二行、第三行的代码执行时间为：2*1000*。这段代码执行的总时间为：(1+2*1000)*。

例3：

void count(int n){

int sum = 0;

for(int i = 0;isum = sum + i;

这段代码跟例 2 相比，我们把固定的 1000，换成了不固定的参数 n，按例 2 的方式计算，这段代码执行的总时间为：（1+2*n)*。

例4：

void count(int n){

int sum = 0;

for(int i = 0;ifor(int j = 0;jsum = sum + i*j;

我们再来分析下例4，第一行代码执行了1次，执行时间为1* ，第二行代码执行了n次，执行时间为n*，第三、四行代码执行n*n次，执行时间为2n2*，最终这段代码的执行时间为(2n2+n+1)* 。

例5：

void count(int n){

int sum = 0;

for(int i = 1;i

代码 时间 算法 执行 int 我们