复杂度分析（一）

一、什么是复杂度分析？

1. 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”;

2. 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能;

3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度;

4. 复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

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

1. 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2. 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

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

1. 大O表示法

• 来源
  算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。

• 特点
  以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。

2. 复杂度分析法则

• 单段代码看高频：比如循环。

• 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。

• 嵌套代码求乘积：比如递归、多重循环等

• 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

四、常用的复杂度级别？

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括:

O(1)（常数阶）

int i = 8;
int j = 6;
int sum = i + j;

O(logn)（对数阶）、O(n)（线性阶）

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

image.png

O(nlogn)（线性对数阶）
如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

O(n^{2)（平方阶）、O(n}3)（立方阶）

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

非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括：
O(2^n)（指数阶）、O(n!)（阶乘阶）

五、如何掌握好复杂度分析方法？

复杂度分析关键在于多练，所谓孰能生巧。