数据结构与算法学习笔记 (一) 复杂度分析

数据结构与算法是计算机类从业者的必修课，一直学的不够深入，前段时间订阅了个专栏，终于开始总结了，拖延症太可怕 必须得改！开始学习数据结构与算法之前，先思考为什么要学习数据结构与算法呢？数据结构与算法解决了什么问题呢？我们要知道数据结构与算法解决的是如何让计算机执行速度更“快”和存储空间更“省”的问题，那么，执行效率就是衡量算法质量的一个重要指标。所以，学习数据结构与算法之前，先来掌握一个数据结构与算法中最重要的概念--复杂度。这里的复杂度具体是指时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系。

时间复杂度

• 时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系
• 时间复杂度表示法
  先来用一段简单的代码，求1,2,3,...n的累加和，估算一下代码的总执行时间T(n)。

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

假设每行代码的执行时间一样，为unit_time。可以看到，第2、3行代码的执行时间分别是1个unit_time，第4、5行代码的执行时间分别是n个unit_time，所以整段代码的总的执行时间就是(2n+2)个unit_tme。因此，可以看出所有代码的执行时间T(n)与每行代码的执行次数成正比。
现在，可以根据这个规律总结成一个公式。
$$\mathit{T}\left(\mathit{n}\right)=\mathit{O}\left(\mathit{f}\right(\mathit{n}\left)\right)$$
公式中，n表示数据的规模；T(n)表示每行代码执行的时间；f(n)表示每行代码执行的总次数；O表示代码的执行时间T(n)与代码执行的总次数f(n)成正比。所以，求和代码中T(n)=O(2n+2)，这就是大O时间复杂度表示法。
注意：大O时间复杂度实际上并不是代码真实的执行时间，而是表示代码执行时间随数据规模增长的趋势，因此也叫渐进时间复杂度。
知道了时间复杂度的表示法，现在再来看一下如何分析时间复杂度呢？

• 时间复杂度分析法

1.只关注循环执行次数最多的一段代码
大 O 这种复杂度表示方法只是表示一种变化趋势。通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级。因此，在分析代码的时间复杂度时，只需要关注循环执行次数最多的那段代码。拿上面1,2,...,n累加和的代码为例，第2、3行都是常量级执行时间，与n大小无关，所以对复杂度没有影响，而第4、5行执行次数最多，所以整段代码的总的执行时间取决于此，这两行代码被执行了n次，总时间复杂度就是O(n)。

2.加法法则：总复杂度等于量级最大的那段代码的复杂度
首先分析下面代码的时间复杂度：

1    int cal(int n) {
2       int sum_1 = 0;
3       int p = 1;
4       for (; p < 100; ++p) {
5         sum_1 = sum_1 + p;
6       }
7    
8       int sum_2 = 0;
9       int q = 1;
10      for (; q < n; ++q) {
11         sum_2 = sum_2 + q;
12       }
13     int sum_3 = 0;
14     int i = 1;
15     int j = 1;
16     for (; i <= n; ++i) {
17       j = 1;
18     for (; j <= n; ++j) {
19           sum_3 = sum_3 +  i * j;
20      }
21   }
22   return sum_1 + sum_2 + sum_3;
23   }

代码分为三部分，分别是求 sum_1、sum_2、sum_3。sum_1代码循环执行了 100 次，是常量级的执行时间，与数据规模n无关，不影响时间复杂度。sum_2第10、11行执行了n次，时间复杂度是O(n)，而sum_3第18/19行执行了n²次，时间复杂度是O(n²)，取最大量级，因此整段代码的时间复杂度就是O(n²)。
抽象为公式，如果 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))).

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

可以看出cal()，如果只是简单的函数，时间复杂度是O(n)，但cal()本身嵌套了一个f()函数，其复杂度也是O(n)，所以cal()整体的时间复杂度就是T(n) = T1(n) * T2(n) = O(n*n)= O(n²)
总结：复杂度量级包括常量阶O(1)，线性阶O(n)，对数阶O(logn)，线性对数阶O(nlogn)，平方阶O(n²)，立方阶O(n³)，k次方阶O(n^k)以及指数阶O(2ⁿ)、阶乘阶O(n!)。这次复杂度量级可以粗略的分为多项式量级和非多项式量级，其中只有指数阶和阶乘阶是非多项式量级，当数据规模n增大时，非多项式量级算法的执行时间会急剧增加，因此，非多项式时间复杂度的算法其实是非常低效的算法，主要需要掌握几种常见的多项式时间复杂度。

空间复杂度

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

来看一段代码具体说明空间复杂度的分析方法

1    void print(int n) {
2      int i = 0;
3      int[] a = new int[n];
4      for (i; i <n; ++i) {
5        a[i] = i * i;
6      }
7    
8      for (i = n-1; i >= 0; --i) {
9        print out a[i]
10      }
11    }

例子中第2行，申请了一个空间存储变量i，但与数据规模n无关；第3行申请了大小为n的Int类型的数组，此外剩余的代码没有再占用其他空间，因此整段代码的空间复杂度就是O(n)。
总结：常见的空间复杂度有O(1)、O(n)、O(n² )，其他的平时用不到，只要掌握常见的几种就足够了。

PS:有人可能会说，跑一遍代码就知道了算法的执行时间和占用的内存大小，为什么还要花时间分析复杂度呢？
答：1.复杂度分析不依赖硬件环境、不受数据规模制约、成本低、简单易操作 2.考虑算法的复杂度，有助于写出更高质量的代码，有利于降低开发、维护成本

欢迎大家提供宝贵建议
博客以学习、分享为主！