如何判断一个算法的好坏？（1）

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

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

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

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

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

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

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

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

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

时间复杂度分析

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

例1：

public static void count(){
int a = 1;
int b = 2;
int sum = a + b;
}

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

例2：

public static void count(){
int sum = 0;
for(int i = 0;i<1000;i++){
        sum = sum + i;
    }
}

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

例3：

public static void count(int n){
    int sum = 0;
    for(int i = 0;i

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

例4：

public static void count(int n){
    int sum = 0;
    for(int i = 0;i

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

例5：

public static void count(int n){
    int sum = 0;
    for(int i = 1;i<=n;i=i*3){
        sum = sum + i;
    }
}

我们再来看下例5，第一行代码执行1次，没有问题。那第二行执行多少次呢？我们假设n为50，那么执行的次数为：i=1，i=3，i=9，i=27，转换一下i=30，i=31，i=32，i=33。可以看出，我们要计算的次数其实就是3的上标（X）+1。

那么接下来我们就得考虑X需要怎么计算，因为条件中存在i<=n，因此能够执行的最大次数为3×=n，通过这个公式去求解X，那么就是X=log3n。

因此最终这段代码的执行时间为（1+2*log3n）*unit_time。

通过上面的这5个例子，我们可以看出，所有代码的执行时间T（n）和所有代码的执行次数成正比。即代码的执行次数越多，所用的执行时间就越长。

而且，通过上面的例子我们也可以看出:因为代码的具体执行逻辑不同，代码的执行时间跟数据的规模n不是单纯的一元函数关系。

根据上面这两个特性，我们可以用如下公式来表示算法的时间复杂度：

T(n) = O(f(n))

其中T(n)代表代码的执行时间；n 表示数据的规模；f(n)表示代码的执行次数。O 表示代码的执行时间与代码的执行次数成正比。

用以上的公式来表示例1~例5的时间复杂度，分别为：

例1：T(n)=O(3)

例2：T(n)=O(1+2*1000)

例3：T(n)=O(1+2*n)

例4：T(n)=O(2n2+ n+1)

例5：T(n)=O(1+2*log3n)

可以看出，这种使用T(n) = O(f(n))的表示方法并不具体表示代码真正的执行时间，因为数据的规模 n 是可变的，这种表示方法表示的是代码执行时间随数据规模增长的变化趋势，所以这种表示方法又叫做渐进时间复杂度表示法。

今天，我们介绍了渐进时间复杂度表示法，下期我们将介绍分析代码时间复杂度的几个小技巧和如何分析空间复杂度。