算法基础之复杂度表示

今天聊聊算法，算法作为开发过程中重要的一份子，是我们编码的基础，遇到问题如果没有好的算法解决，程序也就没有好的性能可言了。所以好的算法，能让代码更省时间和空间，那怎么去计算算法所占用的时间和空间呢？这也就是我们今天要重点说的东西了——空间复杂度和时间复杂度。

当然，面试的过程中也少不了对算法的考察。有人就很奇怪，这不就是很明显的面试造火箭，实战拧螺丝吗？也许你平时工作中涉及到算法的地方比较少，但是作为面试方也就是公司来说，算法却是一个很平等公正的考察程序员基本逻辑的一种有效办法。

而且，长远来看，一个程序，一个项目，能实现也许不难，但是要保证它的性能优良，扩展性较好就需要去深入数据结构与算法，并运用到实际项目中。

★掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。 ”

所以，后续我们也会不定时发一些算法考察题及算法知识的讲解，和大家一起去学习算法。

今天，就从算法的基础知识—复杂度说起。

复杂度作用

如果不分析复杂度的前提下，我们也可以通过实际的监控得出算法执行所占用的时间空间，但是这种做法有几点缺陷：

• 依赖测试环境

因为我们只在我们一台设备上测试，那么这个结果就很依赖我们这台设备的性能了，假如我换一个CPU更强的设备肯定结果是不一样的。

• 依赖实验规模

另一方面来说，就算在同一台设备上测试，由于测试的样本不同，那么测试的结果肯定也会不同。比如排序，有的数组本来就是有序的，那么得到的执行时间肯定是比较快的。

所以我们就需要一把尺子，针对每个算法必须有个公平公正的衡量标准。

复杂度表示

这把衡量复杂度的尺子就是我们的大O时间复杂度表示法，相关公式如下：

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

• T(n)表示代码执行的时间
• n表示数据规模大小，一般指每行代码所执行的时间
• f(n) 表示每行代码执行的次数总和
• O就表示T(n)与f(n)之间的一个正比关系

按照上面的表达式，我们可以推算出一段代码的时间或空间的复杂度，但是这个复杂度并不是真正代码执行的时间，只是用来表示一个渐进关系。

比如时间复杂度，其实是用来表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度。空间复杂度同理。

那我们找个例子实验下：

    private int getSum(int n) {
1        int sum = 0;
2        int i=1;
3        for (; i <= n; i++) {
4            sum = sum + i;
        }
    }

一个简单的求和算法，假设每一行代码的执行时间是lineTime，分析下这段代码的耗时：

• 第一行：lineTime
• 第二行：lineTime
• 第三行，第四行的循环计算：由于这两行都执行了n次，所以总时间为lineTime * 2n

所以总时间就是：（2n+2） * lineTime

根据上述的大O复杂度表示法应该写成：

T(n) = O(2n+2)

一般公式中的低阶、常量、系数三部分并不影响增长趋势，所以都可以忽略，那么这段代码的时间复杂度就可以表示为：

T(n) = O(n)

时间复杂度

这里有两段代码，代表了两种时间复杂度的计算方式，大家看下：

加法法则

    private int getSum(int n) {
        //第一段代码
        int sum = 0;
        int a=1;
        for (; a <= n; a++) {
            sum = sum + a;
        }

        //第二段代码
        int sum2 = 0;
        int i=0;
        int j=0;
        for (; i <= n; i++) {
            for (; j <= n; j++) {
                sum2 = sum2 + i*j;
            }
        }
        return sum2;
    }

我们在刚才的案例中，又加了一段代码，然后分析下两端代码分别的时间复杂度：

• 第一段代码，刚才说过，复杂度为O(n)。
• 第二段代码，按照刚才的算法，应该为O(2n²+2n+3)，

由于在一个复杂度分析中，常量低阶都可以忽略，所以第二段代码中的2n和常量2，3都可以被忽略，就是取复杂度中循环次数最多的一段计算代码即可。

所以第二段复杂度代码可以写成O(n²)。

这里涉及到一个知识点就是：

★我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。 ”

所以整段代码的复杂度为O(n)+O(n²)，等等哦，还不够，这样很明显还不够简便。所以在复杂度计算中还有一个公式就是：

★总的时间复杂度就等于量级最大的那段代码的时间复杂度，写成公式就是：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))). ”

所以两个复杂度取更复杂（量级更大）的那个复杂度，也就是整段代码的最终复杂度表示为：

O(n²)

乘法法则

有时候我们可能会遇到复杂度相乘的场景，比如：

    private int getSum1(int n) {
        int sum = 0;
        int a=1;
        for (; a <= n; a++) {
            sum = sum + getSum2(a);
        }
        return sum;
    }

    private int getSum2(int n) {
        int sum = 0;
        int i=1;
        for (; i <= n; i++) {
            sum = sum + i;
        }
        return sum;
    }

上述例子可以看到如果不计算getSum2(a)的情况下，getSum1方法的时间复杂度为O(n)，getSum2方法的时间复杂度为O(n)，所以getSum1方法的复杂度应该是O(n) * O(n)。

这里就涉及到乘法计算了：

★如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)). ”

怎么理解呢？

因为时间复杂度，其实是用来表示代码执行时间随数据规模增长的变化趋势，所以涉及到比如嵌套情况，需要用到乘法的时候，里面的n变化关系应该也进行相乘。

所以getSum1方法的时间复杂度应该为：

O(n2)

空间复杂度

有了上面时间复杂度的理解，空间复杂度也就可以直接类比下：

★空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系 ”

    public static int call(int n) {
1        int sum = 0;
2        int i = 0;
3        int[] m = new int[n];
        for (; i < n; ++i) {
            m[i]= i;
        }
        return sum;
    }

• 第一行第二行，虽然申请了空间存储变量，但是它是常量，跟数据规模n没有关系，所以可以忽略。
• 第三行，申请了一个大小为n的int类型数组。

所以这段代码的空间复杂度就是：

O(n)

案例分析

实际情况中，空间复杂度比较简单，一般涉及到O(1)、O(n)、O(n2 )，但是时间复杂度就比较复杂了，下面举几个案例：

案例一

    private int call(){
        int i=1;
        return i+1;
    }

可以看到，这段代码跟n没有关系，没有涉及到n的增长趋势，所以它的时间复杂度为Ο(1)。

★一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。 ”

案例二

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

我们直接举例每次i的值：

第一次：2的0次方第二次：2的1次方第x次：2的x次方

当2的x次方 <= n，即循环结束。所以我们一共运行了x次，那么这个x为多少呢？

2^x=n —> n=log2n

所以，这段代码的时间复杂度为O(log2n)。（2为底数）

由于系数可以忽略，所以最终的复杂度为O(logn)

案例三

刚才我们的案例都是跟一个系数n有关，如果我们有多个系数呢？

    private int call(int n, int m) {
        int sum = 0;
        int a = 1;
        for (; a <= n; a++) {
            sum = sum + a;
        }

        int sum2 = 0;
        int a2 = 1;
        for (; a2 <= m; a2++) {
            sum2 = sum2 + a2;
        }
        return sum + sum2;
    }

这段代码与两个参数有关，m和n。复杂度计算应该为：

O(m+n)

★也就是当系数不同时，加法法则会将两个复杂度正常相加，也就是T1(m) + T2(n) = O(f(m) + g(n)) ”

总结

常见的时间复杂度量级有：

常数阶O(1)对数阶O(logN)线性阶O(n)线性对数阶O(nlogN)平方阶O(n²)立方阶O(n³)K次方阶O(n^k)指数阶(2^n)

参考

https://time.geekbang.org/column/article/40036