一、什么是复杂度分析？

  1. 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
  2. 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
  3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
  4. 复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

二、为什么要进行复杂度分析？

  1. 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
  2. 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

三、如何进行复杂度分析？

  1. 大O表示法
    1. 来源：算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
    2. 特点 以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。
  2. 复杂度分析法则
    1. 单段代码看高频：比如循环。
    2. 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
    3. 嵌套代码求乘积：比如递归、多重循环等
    4. 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

      四、常用的复杂度级别？

      多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n)（指数阶）、O(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 遍，所以需要 2nunit_time 的执行时间，所以这段代码总的执行时间就是 **`(2n+2)unit_time`。
所有代码的执行时间T(n) 与每行代码的执行次数成正比.** 即: 每行代码的执行次数越多,所有代码的执行时间就越长. 每行代码的执行次数越少,所有代码的执行时间就越短.
**

  1.  int cal(int n) {
  2.    int sum = 0;
  3.    int i = 1;
  4.    int j = 1;
  5.    for (; i <= n; ++i) {
  6.      j = 1;
  7.      for (; j <= n; ++j) {
  8.        sum = sum +  i * j;
  9.      }
  10.    }
  11.  }

按照上面的思路来。第二行1，第三行1，第四行1，第五行n，第六行n，第七行n，第八行n，共(3+2n+2n````)*unit_time。
尽管我们不知道unit_time的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。

T(n)=O(f(n)) T(n) 表示代码执行的时间； n 表示数据规模的大小； f(n) 表示每行代码执行的次数总和。 因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

第一个例子中的 T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n+2n+3)。这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

如果用大O表示法，第一个例子T(n) = O(n)，第二个为T(n) = O(n)。当n很大的时候，上面公式中的低阶，常数和系数，都可以忽略。只需要记录一个最大值就可以了。比如第二个例子的 T(n) = O(2n+2n+3)，当n为10000时，2n就是2亿，低阶2n为20000还有常数3基本就可以忽略不计了。

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码
    1. 我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

  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()函数，复杂度是T1(n) = O(n)，但是f()函数本身不是简单的操作。它的时间复杂度是T2(n) = O(n)，所以整个cal()函数的复杂度是T(n) = T1T2 = O(nn) = O(n)

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

03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ - 图1
多项式时间复杂度

  1. O(1)
    1. O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
    2. 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)
  2. O(logn)、O(nlogn)
    i=1;
while (i <= n)  {
i = i * 2;
}
    从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。一个一个列出来，就应该是这个样子的：
    03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ - 图2
    通过 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。
    那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
    3.O(m+n)、O(m*n)

空间复杂度分析

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

常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。