2 复杂度分析

[TOC]

1 定义及必要性

之所以需要复杂度分析，就是需要一个可以量化的指标，来衡量一个算法或者一段代码的执行效率，占用内存的大小。相应的定义名称就是时间复杂度和空间复杂度。

之所以不使用实际测试代码来展现性能的原因，我理解主要有：

在相同条件下的测试，仅能有限的表达不同代码的当前情况，即测试想要达到各种边界条件，还是很困难的，成本很高；其次也很麻烦；
不利于交流。不同人的测试环境不同，对相同算法的测试情况，不可能有完全相同的数据表现，只是趋势对比即可。

2 大O复杂度表示法

复杂度分析，就是不运行代码，但是能够评估出代码的性能。

举例来说

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

如何评估这段代码的耗时情况呢？

假设每行代码执行一次都是一个单位时间，记为unit_time。那么上面代码总的执行次数就是3+2n+2n²，即2,3,4行执行1次，5,6行各执行n次，7,8行各执行n*n次。

那么总时间就是
$$
T(n)=(3+2n+2n^2)*unit_time
$$

有了数学公式，就可以量化的评估这段代码的性能了其实。但是每个代码块都表示为公式其实还是麻烦。

从公式中，可以得到一些规律，即时间T(n)和代码执行次数成正比。转换公式表达为
$$
T(n)=O(f(n))
$$
上式中，T(n)表示代码执行的时间，n表示数据规模大小，f(n)表示所有代码执行的次数总和，也是一个公式f。O表示正比关系。

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

这就是大O时间复杂度表示法。

3 时间复杂度分析

3.1 如何快速分析代码的时间复杂度

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

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

加法法则：即把代码执行次数都计算后相加，就如定义的那个case一样的计算，用公式表达就是
$$
如果 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))).
$$
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，用公式表达就是
$$
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
$$

3.2 几种常见时间复杂度

常见的时间复杂度只有几种，从好到坏依次如下

O(1)
O(logn)
O(n)
O(nlogn)
O(n²)
O(2ⁿ)
O(n!)

上述的7种，又可以分为两类数据，多项式量级和非多项式量级。

非多项式量级会随着n的增大，执行时间急剧增加，即O(2ⁿ)和O(n!)。

3.2.1 O(1)

O(1)只是表示代码执行了常量级别，不是具体的1次。也就是说执行时间和n无关。

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

3.2.2 O(logn) O(nlogn)

这种称为对数阶时间复杂度，是最难分析的一种时间复杂度。

举例来说

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

看到i的增长速度，是乘以2的；所以理想情况下
$$
i=2^x=n，其中x为i=i*2的执行次数
$$
换算一下
$$
x=log_2n
$$
也就是说，
$$
T(n)=(1+2log_2n)*unit_time=O(f(2log_2n))=O(logn)
$$
变化一下的话，比如

i = 1;
for (j = 0; j < n; j++){
    while (i <= n){
        i = i * 3;
    }
}

$$ T(n)=O(f(nlog_3n))=O(nlogn) $$

这里的3和2的对数，因为是可以转换的，所以就忽略了。

3.2.3 O(m+n) O(m*n)

当一段代码，同时由多个数据的规模决定的时候，就是上述的表达式了，比如

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

4 空间复杂度

类似时间复杂度的定义，表达的是耗时的趋势，空间复杂度也是占用空间的趋势。

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

推理的方式就是假设每个空间占用unit_space，分析每行占用情况得到表达式，然后用大O表示法简化表达即可。

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

5 最好、最坏情况时间复杂度

有些代码的情况比较复杂，存在不同情况下，复杂度不同的情况。

// n 表示数组 array 的长度
int find(int[] array, int n, int x){
    int i = 0;
    int pos = -1;
    for (; i < n; ++i){
        if (array[i] == x){
            pos = i;
            break;
        }
    }
    return pos;
}

array[i]的值的情况不同，导致pos=i这些代码的执行次数，可能从1次到n次不等。

为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

上述代码的最好就是O(1)，最差就是O(n)

6 平均情况时间复杂度

对于平均情况而言，列出每次可能情况和可能的概率进行计算即可；假设x出现在数组中和不在数组中的概率都是0.5
$$
T(平均执行一次)=1*\frac{1}{2}\frac{1}{n}unit_time\
T(不出现在数组中)=n\frac{1}{2}unit_time\
依次类推得到总的\T(n)=(1\frac{1}{2n}+ 2\frac{1}{2n}+···+ n*\frac{1}{2n}+n*\frac{1}{2})*unit_time=\frac{(1+3n)}{4}*unit_time
$$
所以平均时间复杂度就是O(n)。

一般而言，都不需要分析最好、最坏、平均时间复杂度，无需恐惧。

7 均摊时间复杂度

相比于上述三个特殊的时间复杂度，这个更特殊，特殊在使用场景上。

case：

// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val){
    if (count == array.length){
        int sum = 0;
        for (int i = 0; i < array.length; ++i){
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }
    array[count] = val;
    ++count;
}

上述代码的时间复杂度，也是概率性变动的。

简单理解下，就是持续向array中写入数据，当写满时，sum所有数据写入array[0]，然后重复。

时间复杂度，直接看是O(n)；最好是O(1)，最好情况是数组还有位置的时候；最差是O(n)，是写入的时候刚好满了；平均是O(1)，即
$$
1*\frac{1}{n}+1*\frac{1}{n}+···+1*\frac{1}{n}+n*\frac{1}{n}=\frac{n-1}{n}+1
$$
但这种特殊case的平均时间复杂度，不应该使用这么复杂的计算方法的。因为直观上，会发现有大量的情况是O(1)的操作。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

这个就是摊还分析法，通过摊还分析法得到的时间复杂度，就是均摊时间复杂度。

具体到这个case，做法就是把有序的n次情况中的，耗时多的那1次操作时间，均摊到剩下的n-1次中去。那n-1种情况都是n/(n-1)的耗时了。带入上述公式就是
$$
\frac{n}{(n-1)n}*n
$$
还是O(1)。

重视下摊还分析法即可。

均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。

8 练习

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element){
    if (i >= len){ // 数组空间不够了
        // 重新申请一个 2 倍大小的数组空间
        int new_array[] = new int[len * 2];
        // 把原来 array 数组中的数据依次 copy 到 new_array
        for (int j = 0; j < len; ++j){
            new_array[j] = array[j];
        }
        // new_array 复制给 array，array 现在大小就是 2 倍 len 了
        array = new_array;
        len = 2 * len;
    }
    // 将 element 放到下标为 i 的位置，下标 i 加一
    array[i] = element;
    ++i;
}

最好O(1)，直接添加进去了；

最差O(n)，n=len，数据空间不够的情况；

平均，先直接认为是O(1)，毕竟大多数操作是最好情况的。

计算一下，用摊还方法来看，每len次，有1次的耗时是len，分配给其他len-1次即可，所以还是O(1)。

数据结构与算法之美(2) 复杂度分析