复杂度分析（上）

2018-11-07 本文已影响0人 scc123

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

为什么需要复杂度分析？

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

测试结果依赖于测试环境

不同的硬件对测试结果影响较大
测试结果受数据规模的影响很大

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

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

大 $O$ 复杂度表示法

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

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

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

再看一段代码

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;
        }
    }
}

根据以上思路, 可以得出 $T(n) = (2n^2 + 2n + 3) * t$ .

从中我们可以总结得到一个非常重要的规律, 所有代码的执行时间 $T(n)$ 与每行代码的执行次数 $n$ 成正比
$T(n) = O(f(n))$
其中 $T(n)$ 表示代码执行的时间; n表示数据规模的大小; $f(n)$ 表示每行代码执行的次数总和. 公式中的 $O$ , 表示代码的执行时间 $T(n)$ 与 $f(n)$ 表达式成正比.

所以 $T(n) = O(2n + 2)$ , $T(n) = O(2n^2 + 2n + 3)$ , 这就是大 $O$ 时间复杂度表示法. 大 $O$ 时间复杂度实际表示的是代码执行时间随数据规模增长的变化趋势, 所以, 也叫做渐进时间复杂度, 简称时间复杂度.

当 $n$ 很大的时候, 我们只需记录一个最大量级就可以了, 例如 $T(n) = O(n)$ ; $T(n) = O(n^2)$ .

时间复杂度分析

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

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

总的时间复杂度为 $O(n)$

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

    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;
    }

总的时间复杂度为 $O(n^2)$

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

    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;
    }

总的时间复杂度为 $O(n^2)$

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

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

常量阶 $O(1)$
对数阶 $O(logn)$
线性阶 $O(n)$
线性对数阶 $O(nlogn)$
平方阶 $O(n^2)$ 、立方阶 $O(n^3) \cdots k$ 次方阶 $O(n^k)$
指数阶 $O(2^n)$
阶乘阶 $O(n!)$

将上述时间复杂度错略的分为两类：多项式量级和非多项式量级. 其中, 非多项式量级只有两个: $O(2^n)$ 和 $O(n!)$ .

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

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

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

$O(1)$

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

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

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

$O(logn)$ 、 $O(nlogn)$

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

从代码中可以看出, 变量 $i$ 的值为:
$2^0\ \ 2^1\ \ 2^2\ \cdots \ 2^k\ \cdots \ 2^x = n$
通过求解 $2^x = n$ , 就可以知道代码的执行次数. 所以其为 $O(\log_2n)$ .

因为 $\log_3n$ 就等于 $\log_32 * \log_2n$ , 所以 $O(\log_3n) = O(C * \log_2n)$ , 其中 $C = \log_32$ 是一个常量. 因此, 在对数时间复杂度的表示方法里, 忽略对数的"底", 统一表示为 $O(\log n)$ .

如果一段代码的时间复杂度是 $O(\log n)$ , 循环 $n$ 遍, 时间复杂度就是 $O(n\log n)$ .

$O(m+n)$ 、 $O(m*n)$

    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;
    }

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

乘法类似.

空间复杂度

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

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];
    }
}

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

常见的空间复杂度就是 $O(1)$ 、 $O(n)$ 、 $O(n^2)$ .

学习关键

多练

复杂度分析（上）

为什么需要复杂度分析？

大 $O$ 复杂度表示法

时间复杂度分析

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

空间复杂度

学习关键

猜你喜欢

热点阅读

复杂度分析（上）

为什么需要复杂度分析？

大复杂度表示法

时间复杂度分析

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

空间复杂度

学习关键

猜你喜欢

热点阅读

大 $O$ 复杂度表示法