二、如何分析、统计算法的执行效率和资源消耗？

一、前言

我们都知道，代码的执行时间和执行需要消耗的内存是衡量代码执行效率的重要指标。这两个指标就是时间复杂度和空间复杂度。所以复杂度分析也就尤其的重要了。

二、什么是复杂度分析？

• 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
• 2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
• 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
• 4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

三、为什么要进行复杂度分析？

• 1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
• 2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

四、如何进行复杂度分析？

eg.比如如下代码，第三四行代码的执行次数为n，假设每次执行时间是一样的,都是t，则总的执行时间为 n * t。

public int getSum(int n) {
        int sum = 0;
        for (int i =0; i<n; i++) {
            sum = sum + i;
        }
        return sum;
    }

eg. 如下，假设每次执行时间还是t，则第四五行执行时间为 n * n * t

int getTotal(int n) {
        int total = 0;
        for (int i = 1; i <= n;  i++) {
            for (int j = 1; j <= i; j ++) {
                total = total + i * j;
            }
        }
        return total;
    }

所以从上面知道，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

时间复杂度.png

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

五、时间复杂度分析的几个常见方法

1. 只关注循环执行次数最多的一段代码

当代码执行次数足够大的时候，其实代码执行次数最多的就是时间复杂度比较好的一个参考。

public int getSum(int n) {
        int sum = 0;
        for (int i =0; i<n; i++) {
            sum = sum + i;
        }
        return sum;
    }

比如上面说的案例，执行次数最多是是三四行。这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

综合代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n2)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。
那我们将这个规律抽象成公式就是：如果 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))).

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

比如一段代码内部嵌套了代码，那么复杂度就是内外代码的乘积，最简单的例子就是嵌套for循环。

六、几种常见时间复杂度实例分析

对于刚罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)。

我们主要来看几种常见的多项式时间复杂度。

只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

七、 空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

八、复杂度分析法则

1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

九、常用的复杂度级别？

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。
包括：O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^{2)（平方阶）、O(n}3)（立方阶）

非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。
包括：O(2^n)（指数阶）、O(n!)（阶乘阶）

十、小结

下图可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。

image.png