数据结构 复杂度分析

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

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

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

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

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

在大学刚学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),简称时间复杂度。

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则:总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

  1. O(1)
  2. O(logn)、O(nlogn)
  3. 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 )