CMINI777

# 复杂度分析

数据结构与算法解决的是让代码运行更快更省存储空间的问题。那如何来衡量代码的执行效率呢？这里就需要时间、空间复杂度分析。其实我们可以用“肉眼”就能看出一段代码的执行时间，那么这里我们需要引入大 O 复杂度表示法：T(n)=O(f(n))。 T(n)表示代码执行的时间；n 表示数据规模的大小。f(n) 表示每行代码执行的次数总和。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。 看到这个概念也许觉得有点晕，没关系，上代码：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }
1
2
3
4
5
6
7
8

假设每行代码执行的时间都一样，为 unit_time，第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n * unit_time 的执行时间，so，上面整段代码执行时间是(2n+2) * unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。套上公式，那就是T(n) = O(2n+2)，这就是大 O 时间复杂度表示法。 它并不代表代码执行的具体时间，但是它能表示出代码执行时间的变化趋势，我们可以把这个叫做渐进时间复杂度（简称：时间复杂度）。既然它表示的是代码执行时间的变化趋势，那么我们可以把公式中的低阶、常量、系数三部分忽略掉，我们只需要记录一个最大量级就可以了，so，上面这段代码可以标记为T(n) = O(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;
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11

第 2、3、4 行代码分别需要 1 个 unit_time 的执行时间，第 5、6 行都运行了 n 遍，所以需要 2n * unit_time 的执行时间，第 7、8 行代码循环执行次数为 n^2，所以需要 2 * n^2 * unit_time 的执行时间，so，上面整段代码执行时间是(2 * n^2+2n+3) * unit_time。套上公式，那就是T(n) = O(2 * n^2+2n+3)，so，上面这段代码可以标记为T(n) = O(n^2)。

# 时间复杂度分析方法

1、只关注循环执行次数最多的一段代码 上面的那两个举例，第一段代码总的时间复杂度就是 O(n)，第二段代码就是O(n^2) 2、加法法则：总复杂度等于量级最大的那段代码的复杂度 如果 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)))。

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;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

综合这三段代码的时间复杂度，我们取其中最大的量级，so，上面这段代码复杂度为O(n^2)。 3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 如果 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))。 假设 T1(n) = O(n)，T2(n) = O(n^2)，则 T1(n) × T2(n) = O(n^3)。

# 常用的复杂度级别

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n)（指数阶）、O(n!)（阶乘阶） 例如：

 int i = 8;
 int j = 6;
 int sum = i + j;
1
2
3

上面这段代码的时间复杂度是O(1)。总结：只要代码的执行时间不随 n 的增大而增长，我们都可以称之为常数阶，即时间复杂度是O(1)。

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

变量 i 的值从 1 开始取，每循环一次就乘以 2，当大于 n 时，循环结束。 这里就是等比数列，例如2^0，2^1，2^2，……，2^x。 2^x=n 求解 x，x=log2n，所以上面这段代码的时间复杂度为O(log2n)

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

上面这段代码的时间复杂度为O(log3n) 不管是以 2 为底、以 3 为底、以几为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。

# 空间复杂度分析

空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。 就是看代码有没有占有更多的空间，跟时间复杂度分析一样，低阶、常量阶跟数据规模n没有关系，所以可以忽略，例如申请了一个变量i，我们就可以忽略，但如果申请了一个大小为n的数组，我们就可以将这个空间复杂度表示为O(n)。

数据结构与算法02 →