算法的时间和空间复杂度

算法 复杂度

1. Motivation - 为什么需要复杂度分析

事后统计法（也就是把代码运行一遍，通过统计、监控得到运行的时间和占用的内存大小）的测试结果非常依赖测试环境以及受数据规模的影响程度非常大。但是实际上更需要一个不用具体的测试数据就可以估计出算法的执行效率的方法。

2. 大 O 复杂度表示法

算法的执行效率简单来说就是算法的执行时间。比如下面这段代码的执行时间，假设每行代码执行的时间是一样的，都为 unit_time。在这个假设的基础之上，这段代码的总执行时间为 (2n + 2)* unit_time。

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

通过这个例子，可以看出总执行时间 T(n) 是与每行代码的执行次数成正比，即可以满足这个公式 T(n) = O(f(n))，其中 n 是数据规模的大小，f(n) 表示每行代码执行的总次，O() 表示一个函数，即 T(n) 与 f(n) 成正比。在这个例子中 T(n) = O(2n+2)，这种方式就被称为大 O 复杂度表示法。但是实际上，大 O 时间复杂度并不具体表示代码执行真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度，简称时间复杂度。那么，在 2n+2 这个式子中，系数 2 和 常数 2 并不左右增长趋势，比如它是线性，并不是会因为系数 2 或者常数 2 改变它线性增长的趋势，因此又可以写成T(n)=O(n)。又比如 T(n) = O(n^2)，那么表示代码执行时间随数据规模 n 增长的变化趋势是 n 平方。下面这张图是不同时间复杂度，随数据规模增长的执行时间变化

3. 时间复杂度分析

如何对一段代码的时间复杂度进行分析呢？可以采用以下几种方法

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

因为大 O 复杂度表示法只是表示一种趋势，所以可以忽略掉公式中的常数项、低阶、系数等，只记录一个最大的量级就可以了。因此在分析一个算法、一段代码的复杂度的时候，只需要关注循环次数最多的那一段代码就行了。比如下面这段代码，时间复杂度是 O(n)

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

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

这个主要是省略掉大 O 复杂度中的低阶项。个人感觉这个方法跟上面的方法有些重合。比如下面这段代码中，可以按照循环分为三个段，第一个段中有个循环，但是循环次数是个常数项，对增长趋势无任何影响，因此时间复杂度是 O(1)，第二段代码的时间复杂度是 O(n)，第三个段代码的时间复杂度是 O(n^2)。这三个段中量级最大的那个时间复杂度也就是整段代码的时间复杂度。

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) {
        j = 1; 
        for (; j <= n; ++j) {
            sum_3 = sum_3 +  i * j;
        }
    }
    return sum_1 + sum_2 + sum_3;
}

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

比如下面这段代码中，f() 是一个循环操作，整个复杂度是 O(n)，而 cal() 中的循环相当于外层，调用了 f()，假如把 f() 当成一个简单的操作的话，那么时间复杂度是 O(n)，算上 f() 真实的复杂度之后，整个 cal() 的时间复杂度是 O(n)O(n)=O(nn) = 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;
}

3.1. 常见时间复杂度

下面针对上述的若干种时间复杂度进行阐述：

1. O(1)
   O(1)是常量级时间复杂度的一种表示，只要代码的时间不随 n 的增大而增大，那么它的时间复杂也是 O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 O(1)。
   

2. O(logn)、O(nlogn)
   对数时间复杂度往往比较难分析，比如下面这段代码中

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

3. 从 i 的值从 1 开始取，每循环 1 次就乘以 2，一直到 n 为止。那么当执行 x 次时到达 n，那么，推得 ，时间复杂度为 。假如每循环 1 次变成乘以 3，如下所示

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

4. 可得 ，时间复杂度为 。那么由于 ，这个时间复杂度又可以是 。因此在对数阶时间复杂度的表示方法里，可以忽略“底”，而直接统一成 O(logn)。
   O(nlogn) 的时间复杂度就相当于上面说到的“乘法法则”：一段代码的时间复杂度为O(logn) ，这段代码循环 n 次，时间复杂度就是 O(nlogn) 了。

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

6. 从这段代码中可以看出m 和 n 是两个数据规模，无法评估 m 和 n 的量级大小。因此，不能省略其中任何一个，所以就是 O(m+n) 了。

7. O(2^n)、O(n!)
   在上述表格中列出的复杂度量级，可以粗略的分为两类：多项式量级和非多项式量级。其中非多项式量级只有这两个。非多项式量级的算法问题也叫做 NP(Non-Deterministic Ploynomial，非确定多项式)问题。当 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间也会无限增长，所以是种很低效的算法。
   

   3.2. 最好、最坏情况时间复杂度

   比如下面这段代码中，是在数组中查找一个数据，但是并不是把整个数组都遍历一遍，因为有可能中途找到了就可以提前退出循环。那么，最好的情况是如果数组中第一个元素正好是要查找的变量 x ，时间复杂度就是 O(1)。最坏的情况是遍历了整个数组都没有找到想要的 x，那么时间复杂就成了 O(n)。因此 O(1) 就是这段代码的最好情况时间复杂度，也就是在最好的情况下，执行这段代码的时间复杂度。O(n) 就是这段代码的最坏情况时间复杂度。

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

   3.3. 平均情况时间复杂度（加权平均时间复杂度或者期望时间复杂度）

   最好和最坏情况时间复杂度都是极端情况发生的时间复杂度，并不常见。因此可以使用平均情况时间复杂度来表示。比如上面这段代码中查找 x 在数组中的位置有两种情况，一种是在数组中，另一种是不在数组中。在数组中又可以在数组中的 0~n-1 位置。假设在数组中和不在数组中的概率分别为 1/2，在数组中的 0~n-1 的位置概率都一样，为 1/(2 *n)。因此，上述这段的平均情况时间复杂度（或者叫加权平均时间复杂度、期望时间复杂度）为
   

   假如使用如下公式计算复杂度的话，那么就相当于每种情况的发生概率都是 1/(n+1) 了，没有考虑每种的情况的不同概率，存在一定不准确性。

3.4. 均摊时间复杂度

均摊时间复杂度采用的是摊还分析法（平摊分析法）。就是把耗时多的操作，平摊到其他那些时间复杂度比较低的操作上。比如下面这段代码

// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = newint[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;
}

这段代码想要实现的就是往一个数组中插入数据，如果数组满了的话，那么就求和之后的 sum 放到数组的第一个位置，之后继续将数据插入到数组中。通过分析可以发现，这段代码的最好情况时间复杂度是 O(1)，最坏情况时间复杂度是 O(n)，平均时间复杂度是 O(1)。
那么这段代码中，在大部分情况下，时间复杂度是 O(1)，只有个别情况下，复杂度才是 O(n)。并且，O(1) 和 O(n) 出现的比较规律，一般一个 O(n) 执行之后，会出现 n-1 个 O(1) 的执行。针对这种情况，可以使用摊还分析法，就是把 O(n) 这个耗时多的时间复杂度均摊到接下来的 n-1 个 O(1) 的执行上，均摊下来的时间复杂度为 O(1)，这个时间复杂度就是均摊时间复杂度。
那么均摊时间复杂度不怎么常见，常见的场景是：对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高。而且这些操作之间存在前后连贯的时序关系，比如上面提到的先是一系列 O(1) 的时间复杂度操作，接下来是 O(n) 的时间复杂度操作。这个时候就可以采用摊还分析法将较高时间复杂度的那次操作的耗时平摊到其他时间复杂度比较低的操作上。

4. 空间复杂度分析

空间复杂度分析方法很简单。时间复杂度的全称叫做渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。那么空间复杂度全称叫做渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
比如下面这段代码中，首先 int i= 0; 申请一个空间存储变量，是常量可以忽略，int[] a = new int[n]; 申请了一个大小为 n 的 int 类型数组，剩下的代码都没有占用更多的空间，因此空间复杂度是 O(n)

void print(int n) {
    int i = 0;
    int[] a = newint[n];
    for (i; i <n; ++i) {
        a[i] = i * i;
    }
    for (i = n-1; i >= 0; --i) {
        print out a[i]
    }
}

对于空间复杂度分析，其实比较简单，一般看变量声明时分配的空间大小即可。

4.1. 常用时间复杂度

常用的空间复杂度就上面 3 种，O(nlogn)、O(logn)这样的对数阶复杂度一般都用不到。

5. 总结

回顾一下复杂度分析，总的来说时间复杂度的 motivation 是想要一个不用具体数据就可以估算出算法的执行效率的方法。而时间复杂度采用的是大 O 表示法，大 O 表示法其实描述的是一个增长趋势。比如 n^2 中，当 n 的值越来越大时候，O(n^2) 这个算法的执行时间是成平方增长的，而 O(n) 这个算法的执行时间是成直线型增长的，因此 O(n^2) 的时间复杂度是更高（见第一张图）。之后是几种常用的时间复杂度，平均时间复杂度、最好最坏时间复杂度，均摊时间复杂度（均摊这种思想在操作系统中有一定的体现：RR 调度算法中，在时间片大小选择上，有着类似的处理方式，因为 RR 是一个抢占式调度算法，当发生调度之后会发生进程的上下文切换，而进程的上下文切换是需要额外的时间成本，而这个时间成本会均摊到时间片上，当时间片很大时，显然均摊的效果不错，因此这个额外的时间成本影响会很小）