数据结构复杂度分析

发表于 2020-07-18 更新于 2022-05-29 分类于 basic 阅读次数： Waline：本文字数： 4k 阅读时长 ≈ 4 分钟

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。

(1) 为什么需要复杂度分析

把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？

这种评估算法执行效率的方法是正确的，叫事后统计法。但是，这种统计方法有非常大的局限性。

测试结果非常依赖测试环境

测试结果受数据规模的影响很大

在大学刚学C语言的时候，老师交给我们一个任务，根据高斯公式计算π的值，分别精确到第六位、第七位、第八位 …，下课后直接在图书馆写代码计算，计算结果精确到第六位的时候特别快，刚点运行就计算完了，花费几ms，计算第七、八、九位也很快，不超过3s，但是精确到第十位的时候，运行了30s后，听到电脑风扇呼呼地响了。


/**
 * <pre>
 *
 *
 *   计算π
 *
 *    无穷级数法
 *      莱布尼兹级数：π/4 = 1- 1/3 + 1/5 - 1/7 + 1/9 … (收敛很慢)
 *      马青公式：π/4 = 4(1/5-(1/5)³/3+(1/5)^5/5-(1/5)^7/7+……)+(1/239-(1/239)³/3+(1/239)^5/5-(1/239)^7/7+……)(du收敛较快，每计zhi算一项可得到π的1.4位十进制精度)
 *
 *
 *
 *   含圆周率的公式列表- 维基百科，自由的百科全书  zh.wikipedia.org › zh-hans › 含圆周率的公式列表   https://zh.wikipedia.org/zh-hans/%E5%90%AB%E5%9C%86%E5%91%A8%E7%8E%87%E7%9A%84%E5%85%AC%E5%BC%8F%E5%88%97%E8%A1%A8
 *  【并行计算】六种方法计算圆周率  http://littledva.cn/article-16/
 *   http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/piforms.html
 *
 *   Java小程序计算圆周率代码  http://www.uxys.com/html/JavaKfjs/20170911/15192.html
 *   π后100位的计算PI https://blog.csdn.net/zhanbiane/article/details/56488694
 *
 * </pre>
 *
 * @author weikeqin
 * @date 2020-07-18 09:09
 */
public class CalculatePiApproximation {

    /**
     * @param args
     */
    public static void main(String[] args) {

        CalculatePiApproximation c = new CalculatePiApproximation();
        double preciseCount = 1E-10;
        c.caclPi1(preciseCount);

    }

    /**
     * <pre>
     *
     *     利用公式 π/4 ≈ 1 - (1/3) + (1/5) - (1/7) + ... ，
     *     编写程序计算π的近似值，
     *     直到最后一项的绝对值小于0.000001
     *
     *       精确到小数点后几位
     *        1e-6 = 1 * 10^(-6)
     *
     *    无穷级数法
     *      莱布尼兹级数：π/4 = 1- 1/3 + 1/5 - 1/7 + 1/9 … (收敛很慢)
     *      马青公式：π/4 = 4(1/5-(1/5)³/3+(1/5)^5/5-(1/5)^7/7+……)+(1/239-(1/239)³/3+(1/239)^5/5-(1/239)^7/7+……)(du收敛较快，每计zhi算一项可得到π的1.4位十进制精度)
     *
     * </pre>
     *
     * @param preciseCount 精确到小数点后几位 1E-6
     * @return
     */
    public double caclPi1(double preciseCount) {
        long t1 = System.currentTimeMillis();
        int symbol = 1;
        // 当前分数
        double term = -1.0;
        double pi = 0.0;
        int i = 1;
        int count = 0;

        while (Math.abs(term) > preciseCount) {
            count++;

            // 1/1  1/3  1/5
            term = 1.0 * symbol / i;
            // 1 -1
            symbol = -symbol;
            // 1 - 1/3 + 1/5 - 1/7
            pi += term;
            i += 2;

        }

        pi *= 4;

        long t2 = System.currentTimeMillis();

        System.out.println("pi：" + pi);
        System.out.println("loop count：" + count);
        System.out.println("cost " + (t2 - t1) + " ms");
        return pi;
    }

}

(2) 时间复杂度

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

/**
 * 两数之和
 *
 * @param x
 * @param y
 * @return
 */
public int add(int x, int y) {
    return x + y;
}

/**
 * @return
 */
public int sum() {
    int x = 0;
    int y = 1;
    return x + y;
}

/**
 * 等差数列的求和
 * 公差为1
 *
 * @param x
 * @return
 */
public int seqSum(int x) {
    int sum = 0;
    for (int i = 0; i < x; i++) {
        sum += i;
    }
    return sum;
}

/**
 * @param x
 * @return
 */
public int sum2(int x) {
    int sum = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < x; j++) {
            sum += j;
        }
    }
    return sum;
}

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

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

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

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

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

O(1)
O(logn)、O(nlogn)
O(m+n)、O(m*n)

复杂度量级

O(1) 常数阶
O(logn) 对数阶
O(n) 线性阶
O(nlogn) 线性对数阶
O(n^2) 平方阶
O(n^3) 立方阶
O(n^k) k次方阶

O(2^n) 指数阶
O(n!) 阶乘阶

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

我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

(3) 空间复杂度

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

/**
 *
 */
public int[] memory1() {
    int i = 1;
    int[] arr = new int[1];
    arr[0] = 1;
    return arr;
}

可以看到，申请了一个变量i的存储空间，并且申请了 arr的存储空间。但是它是常量阶的，跟数据规模 n 没有关系，所以空间复杂度是O(1)

/**
 *
 */
public int[] memory2(int n) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = 1;
    }
    return arr;
}

可以看到，申请了一个变量i的存储空间，并且申请了 arr的存储空间。arr的大小和n有关系，所以空间复杂度是O(n)

/**
 *
 */
public int[][] memory3(int n) {
    int[][] arr = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            arr[i][j] = 1;
        }
    }
    return arr;
}

可以看到，申请了一个变量i的存储空间，并且申请了 arr的存储空间。arr的大小和n有关系，因为是两个循环，所以空间复杂度是O(n^2)

空间复杂度就是 O(1)、O(n)、O(n^2)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

References

[1] 《算法基础》 Richard Neapolitan (作者) 贾洪峰 (译者)
[2] 03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？
[3] 04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
[4] [算法的时间复杂度和空间复杂度-总结( https://blog.csdn.net/zolalad/article/details/11848739 )