复杂度分析（上）

+文本内容是对王争《数据结构与算法之美》课程的笔记， 如果有任何侵权行为， 请联系博主删除

为什么需要复杂度分析？

很多人对复杂度分析有疑问, 认为直接在机器上跑一遍, 就可以得出时间和空间复杂度. 对于这种说法, 我们认为是正确的, 并且很多书籍将其称为事后统计. 但是, 这种方法有很大的局限性.

• 测试结果依赖于测试环境

  不同的硬件对测试结果影响较大

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

  数据规模的大小和有序度, 对测试结果影响较大

所以, 我们需要一个不用具体的测试数据来测试, 就可以粗略地估计算法的执行效率的方法.

大复杂度表示法

以一段代码为例来估计算法的执行时间

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

由于是粗略估计, 假设每行代码执行的时间都一样, 为. 第2、3行代码分别需要1个的执行时间, 第4、5行都运行了遍, 所以需要的执行时间, 所以这段代码总的执行时间就是. 可以看出来, 所有的代码执行时间与每行代码的执行次数成正比.

再看一段代码

int cal(int n) {
    int sum = 0;
    int i = 1;
    int j = 1;
    for(; i <= n; ++i){
        j = 1;
        for(; j <= n; ++j){
            sum = sum + i * j;
        }
    }
}

根据以上思路, 可以得出.

从中我们可以总结得到一个非常重要的规律, 所有代码的执行时间与每行代码的执行次数成正比

其中表示代码执行的时间; n表示数据规模的大小; 表示每行代码执行的次数总和. 公式中的, 表示代码的执行时间与表达式成正比.

所以, , 这就是大时间复杂度表示法. 大时间复杂度实际表示的是代码执行时间随数据规模增长的变化趋势, 所以, 也叫做渐进时间复杂度, 简称时间复杂度.

当很大的时候, 我们只需记录一个最大量级就可以了, 例如; .

时间复杂度分析

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

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

总的时间复杂度为

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

    int cal(int n){
        int sum_1 = 0;
        int p = 1;
        for(; p < 100; ++p){
            sum_1 = sum_1 + p;
        }
  
        int sum_2 = 0;
        int q = 1;
        for(; q<n; ++q){
            sum_2 = sum_2 + q;
        }
  
        int sum_3 = 0;
        int i = 1;
        int j = 1;
        for(; i<=n; ++i){
            for(; j<=n; ++j){
                sum_3 = sum_3 + i * j;
            }
        }
  
    return sum_1 + sum_2 + sum_3;
    }

总的时间复杂度为

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

    int cal(int n){
        int ret = 0;
        int i = 1;
        for(; i<n; ++i){
            ret = ret + f(i);
        }
    }

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

总的时间复杂度为

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

复杂度量级(按数量级递增)

• 常量阶
• 对数阶
• 线性阶
• 线性对数阶
• 平方阶、立方阶次方阶
• 指数阶
• 阶乘阶

将上述时间复杂度错略的分为两类：多项式量级和非多项式量级. 其中, 非多项式量级只有两个: 和.

我们把时间复杂度为非多项式量级的算法问题叫做NP问题(Non-Deterministic Polynomial, 非确定多项式).

当数据规模越来越大时, 非多项式量级算法的执行时间会急剧增加.

因此, NP问题不是我们讨论的重点. 接下来, 我们主要来看几种常见的多项式时间复杂度.

1. 

   只是常量级时间复杂度的一种表示方法, 并不是指只执行了一行代码.

int i = 8;
int j = 6;
int sum = i + j;

只要代码的执行时间不随的增长而增长, 这样代码的时间复杂度都记作. 一般情况下, 只要算法中不存在循环语句、递归语句, 即使有成千上万行代码, 其时间复杂度也是.

2. 、

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

从代码中可以看出, 变量的值为:

通过求解, 就可以知道代码的执行次数. 所以其为.

因为就等于, 所以, 其中是一个常量. 因此, 在对数时间复杂度的表示方法里, 忽略对数的"底", 统一表示为.

如果一段代码的时间复杂度是, 循环遍, 时间复杂度就是.

3. 、

    int call(int m, int n){
        int sum_1 = 0;
        int i = 1;
        for(; i<m; ++i){
            sum_1 = sum_1 + 1;
        }
   
        int sum_2 = 0;
        int j = 1;
        for(; j<n; ++j){
            sum_2 = sum_2 + j;
        }
        return sum_1 + sum_2;
    }

从代码中可以看出, 和是表示两个数据规模, 我们无法评判谁的数量级大, 所以, 时间复杂度就为.

乘法类似.

空间复杂度

空间复杂度全程就是渐进空间复杂度, 表示算法的存储空间与数据规模之间的增长关系.

void print(int n){
    int i = 0;
    int[] a = new int[n];
    for(i; i<n; ++i){
        a[i] = i*i;
    }

    for(i=n-1; i>=0; --i){
        print out a[i];
    }
}

第行代码中, 我们申请了一个空间存储变量, 但是它是常量阶, 跟数据规模没有关系, 所以忽略. 第行申请了一个大小为的类型数组, 除此之外, 剩下的代码都没有占用更多的空间, 所以整段代码的空间.

常见的空间复杂度就是、、.

学习关键

多练