#算法复杂度分析

#为什么需要复杂度分析

同一个问题，可能有多种不同的算法来解决，我们当希望选择效率最好的算法，但实际情况比较我们想像的更复杂，这时我们就需要一种方法来比较这些算法的优劣，判断哪个算法更有效。

除此之外，复杂度分析也可以帮助我们去预测算法在不同规模的数据下，程序运行所需的时间，所消耗的资源，通过复杂度板，我们可以去找到算法的瓶颈，从而进行针对性的优化。

#什么是算法复杂度

在讨论算法的效率时，我们只关心两种类型的资源，时间和空间，因此复杂度也可以从这两方面来分析。

当然，我们可以用计时器来计算算法执行所需要的时间（比如多少毫秒），来描述时间复杂度，也可以使用所消耗的空间容量来描述空间复杂度。

但这样做并不好，算法执行时间越少就代表算法越好吗？同样的算法，在两台不同的计算机中运行，由于两台计算的性能不同，比如说两台计算机的 CPU，一个是 i5 一个是 i7，i7 一定比 i5 更强大，当然算法完成所需的时间更少，但并不能说明这个算法就更好。

哪怕两台配置相同的计算，同样的算法在这两台机上执行，所花的时间也不一定就相同，毕竟机器上运行的其它程序、服务的都可能影响到程序执行的时间。

算法复杂度不是指算法实际运行的时间（因为实际运行时间会受到硬件、编程语言、编译器等因素的影响），而是指 算法执行所需资源（通常是时间和空间）随着输入规模增长而增长的趋势。

• 时间复杂度 (Time Complexity)： 衡量算法执行所需的时间资源。
• 空间复杂度 (Space Complexity)： 衡量算法执行所需的空间资源（内存）。

我们通常更关注 时间复杂度，因为它往往是算法性能的主要瓶颈。

#输入规模

输入规模是指算法处理的数据量的大小。它通常用一个变量 n 来表示。

例子：

• 对于排序算法，输入规模就是数组的长度 n。
• 对于图算法，输入规模可以是图的顶点数 n 或边数 m。
• 对于字符串匹配算法，输入规模可以是字符串的长度 n。

#大 O 记号

大 O 符号（Big O Notation）是计算机科学中用来描述算法复杂度的一种表示法。它用于表示算法在最坏情况下的时间或空间复杂度，从而帮助我们了解算法的效率和性能。

简单来说，大 O 符号描述了当输入规模 n 趋近于无穷大时，算法执行时间或所需空间如何增长。它侧重于输入规模 n 对算法性能的影响，而忽略常数因素和低阶项。

下面是使用大 $O$ 符号来分析算法时的一些原则：

• 不用具体的单位（如毫秒或秒）来描述代码的效率
• 只关心时间和空间如何根据输入的大小进行调整
• 考虑问题的最坏情况
• 略去常数和非主要影响因子

例如，对于输入规模 $n$，一个算法的实际执行时间是 $2n^2 + 3n + 5$，那么它的时间复杂度就是 $O(n^2)$。

#常见的时间复杂度

在算法分析中，我们通常只关注影响代码执行总次数的关键代码部分（如循环、递归），一些次要的代码属于非主要影响因子，在计算时间复杂度时可以忽略。

下图展示了一些常见的时间复杂度，描述了代码执行总次数随着数据规模的增长如何变化的趋势。

• $O(1)$ – 常数复杂度
• $O(log n)$ – 对数阶复杂度
• $O(n)$ – 线性阶复杂度
• $O(n log n)$ – 线性对数阶，也称多项式阶时间复杂度
• $O(n ^ 2)$ – 平方阶复杂度
• $O(2 ^ n)$ – 指数阶复杂度
• $O(n!)$ – 阶乘阶复杂度

上面的复杂度量级中，又可以粗略的分为两类，多项式量级与非多项式量级，非多项式量的算法问题又叫做 NP （Non-Deterministic Polynomial）问题。

上面列出的复杂度量级中，非多项式量级只有两种：$O(2^n)$ 和 $O(n!)$ 。

当数据规模 $n$ 越来越大时，非多项量级算法的执行时间会急剧增加，因此这两种非多项式量级的算法效率非常低下，我们就尽量避免写出这样的算法时间复杂度（当数据规模非常小的时候，并不需要过多考虑时间的复杂度问题，因此关系不大）。

下面选用其中一些常用的时间复杂度，通过具体的代码来看看如何分析与计算时间复杂度。

#常数阶复杂度：$O(1)$

• 算法的执行时间不随输入规模的增长而变化。 • 例子：访问数组中的某个元素、执行简单的算术运算。

如果一个算法的执行次数不随数据规模的变化而变化，那就可以说这段代码的时间复杂度是常数阶复杂度，用 $O(1)$ 表示。

比如下面这段代码：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    cout << 2 * n << endl;
    return 0;
}

无论输入的 $n$ 是多少，该程序都只执行一次，时间复杂度并不随着数据 $n$ 的增长而变化，因此该程序的时间复杂度为 $O(1)$。

#线性阶复杂度：$O(n)$

• 算法的执行时间随着输入规模的增长呈线性增长，即输入规模翻倍，执行时间也翻倍。 • 例子：遍历一个数组，对数组元素求和。

再来看看下面这段函数代码，主要目的是对一个数组元素求和。

int sumArray(int arr[], int n) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += arr[i];
  }
  return sum; // O(n)
}

可以看到，循环执行的次数与 $n$ 直接相关，$n$ 是多少，循环就执行多少次。随着 $n$ 的增长，执行的次数同步增长，这样的算法复杂度也称之为线性阶。

#对数阶：$O(log n)$

• 算法的执行时间随着输入规模的增长而缓慢增长（对数次增长）。 • 例子：二分查找。每次将搜索范围缩小一半。

先看一段非常简单的代码。

int cnt = 0; // 记录循环的次数
for(int i = 1; i <= n; i *= 2) {
  cnt++;
}

当 $n=32$ 时，循环执行完成后 cnt 的值为 6 ，也就是说循环执行了共 6 次。

观察此循环，发现 i 并不是逐一增长的，而是不断的翻倍（i *= 2），当 $n=32$ 时，每次循环执行时的 i 依次是 1 2 4 8 16 32。

根据高中的数学知识不难得出一个计算循环次数 x 的公式 $2^x = n$ ，$x = log_{2}{n}$ ，因此可知这段代码的时间复杂度为 $O(logn)$ ，这里 $logn$ 是指以 2 为底的对数，下面的 2 可省略。

我们后面会学到的二分查找也是对数阶的复杂度。

int binarySearch(int arr[], int n, int target) {
  int left = 0, right = n - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // O(log n)
}

#线性对数阶：$O(nlong n)$

• 算法的执行时间随着输入规模增长呈 n log n 形式。略快于平方复杂度，但慢于线性复杂度。 • 例子：归并排序、快速排序（平均情况）。

理解了上面的线性阶复杂度和对数阶复杂度，线性对数阶也就很好理解了，只需要在对数阶的这段循环代码外再套一层重复 n 次的循环即可。

int cnt = 0; // 记录循环的次数
for (int i = 1; i <= n; i++) {
  for(int j = 1; j <= n; j *= 2) {
    cnt++;
  }
}

如果同样是 $n=32$，这段代码执行完成后，cnt 的值应该是 192 (32 * 6 = 192）。因此这段代码的时间复杂度为 $O(nlogn)$，称为线性对数阶复杂度。

我们后面在排序算法中会学到归并排序算法就是线性对数阶的复杂度。

void mergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right); // O(n log n)
  }
}

#平方阶复杂度：$O(n^2)$

• 算法的执行时间随着输入规模呈平方增长。常见于简单的双重循环算法。 • 例子：冒泡排序、选择排序、插入排序。

平方阶复杂度，代码大家应该就很熟悉，其实就是嵌套的两层循环，每层循环执行次数为 $n$，两层就是 $n \times n = n^2$。

int cnt = 0; // 记录循环的次数
for (int i = 1; i <= n; i++) {
  for(int j = 1; j <= n; j++) {
    cnt++;
  }
}

同样的道理，如果是三层嵌套循环，每层循环执行 n 次，整个的代码时间复杂度就是 $O(n^3)$ 。

例如，冒泡排序算法就是平方阶时间复杂度。

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  } // O(n²)
}

#指数阶复杂度：$O(2^n)$

• 算法的执行时间随着输入规模呈指数增长。常见于递归算法，如解决子集问题、汉诺塔问题。 • 例子：斐波那契数列的递归计算。

指数阶复杂度，可以这么样，元素每增加一个，其执次的次数就会翻倍。

递求解斐波那契数列（Fibonacci）数列第 n 项的程序就是典型的指数阶复杂度示例。

int fib(int n) {
  cnt++;
  if (n == 0 || n == 1) return n;
  else return fib(n - 1) + fib(n - 2);
}

斐波那契数列从第 3 项开始，每一项的数字都等于前两项的数字之和，也就是说，每一项其实可以分解为求它的前面两项。

要求的 $n$ 每多一位，其要计算的项就要多两倍，因此其时间复杂度是 $O(2^n)$。

除此之外，当我们当我们在遍历一棵深度为 $n$ 的满二叉树所有节点时，由于满二叉树的节点数量与深度 $n$ 之间的关系是节点数量等于 $2^n-1$，所有节点都要访一次，因此其时间复杂度是 $O(2^n)$ 。

#阶乘阶复杂度：$O(n!)$

• 算法的执行时间随着输入规模呈阶乘增长。常见于全排列生成算法。 • 例子：生成 n 个元素的全排列。

比如求 1 ～ n 的全排列，时间复杂度就是 $O(n!)$ ，效率很低。

void permute(vector<int>& arr, int l, int r) {
  if (l == r) {
      // 输出排列
  } else {
    for (int i = l; i <= r; i++) {
      swap(arr[l], arr[i]);
      permute(arr, l + 1, r);
      swap(arr[l], arr[i]);
    }
  }
} // O(n!)

#空间复杂度

空间复杂度表示的是算法执行时所消耗的存储空间与数据规模之间的增长关系。主要取决于算法中声明的变量和分配的数据结构所占用的内存空间。

相对于时间复杂度来说，空间复杂度要简单很多，一般来说只需要掌握下面三个即可。

• 常数阶 $O(1)$
• 线性阶 $O(n)$
• 平方阶 $O(n^2)$

#常数阶

• 算法所需的额外空间不随输入规模的增长而变化。
• 例子：使用少量临时变量。

int sum = 0; // O(1)
for (int i = 0; i < n; ++i) {
  sum += array[i];
}

空间复杂度：$O(1)$ （只使用了常数个变量）

#线性阶

• 算法所需的额外空间随着输入规模的增长而线性增长。
• 例子：创建一个长度为 n 的数组。

int* newArray = new int[n]; // O(n)
for (int i = 0; i < n; ++i) {
  newArray[i] = array[i] * 2;
}

空间复杂度：$O(n)$ （创建了一个长度为 n 的新数组）

#平方阶

• 算法所需的额外空间随着输入规模的增长而平方增长。
• 例子：创建一个 n x n 的二维数组。

int** matrix = new int*[n]; // O(n)
for (int i = 0; i < n; ++i) {
  matrix[i] = new int[n]; // O(n) * O(n) = O(n^2)
}

#小结

• 算法复杂度是评估算法效率的重要指标。
• 时间复杂度衡量算法执行所需的时间资源，空间复杂度衡量算法执行所需的空间资源。
• 大 O 记号是一种用来描述算法复杂度渐近行为的数学符号。
• 掌握复杂度分析的基本原则和方法，可以帮助我们选择合适的算法，优化算法性能。