算法基础 - 时间复杂度和空间复杂度（万字长文详解）

前言

什么是算法效率

在编写好程序代码之后，需要运行在计算机上，而在运行过程中需要占用CPU时间片和内存空间。
算法效率是指算法在执行任务时的性能情况。

时间复杂度

定义

时间复杂度可以直观理解为算法运行所需时间与输入规模之间的关系。

作用

用于描述：随着输入数据量的增加，算法执行所需要的时间将如何增长。

类比理解

如果你要在书架上找一本书，你可以有两种方法：

• 顺序查找：从书架的第一本书开始，一本一本地看，直到找到你想要的书。
• 使用目录：先在目录中找到书的编号，然后直接去相应的位置拿书。

顺序查找的时间复杂度是线性的，也就是说，如果书架上有n本书，在最坏的情况下，你可能需要查看所有n本书。我们说这个算法的时间复杂度是O(n)。 而使用目录查找的时间复杂度是常数的，不管书架上有多少书，你都能很快找到，我们说这个算法的时间复杂度是O(1)。

空间复杂度

定义

算法运行时所需内存空间与输入规模之间的关系。

作用

用于描述：随着输入数据量的增加，算法执行过程中临时占用存储空间的大小。

类比理解

如果你想记录下你已经查找过的书，你可能需要一张纸来写下书名：

• 顺序查找：这张纸上的记录数量将随着书架上的书数量增加而增加，空间复杂度是O(n)。
• 目录查找：你可能不需要记录任何东西，或者只需要记录一个编号，空间复杂度是O(1)。

大O表示法

大O表示法（Big O notation）是用于描述算法运行时间或空间复杂度的一种数学表示方法。它提供了一种抽象的方式来评估算法的性能，尤其是在数据规模增长时算法的表现。

为什么需要？

判断一个算法所编程序运行时间的多少，并不是将程序编写出来，通过在计算机上运行所消耗的时间来度量。原因如下：

• 解决一个问题的算法可能有很多种，全部实现的工作量是巨大，不可能穷举列出每一种算法；
• 不同计算机的软、硬件环境不同；即便使用同一台计算机，不同时间段其系统环境也不相同，程序的运行时间很可能会受影响，可能导致结果相差甚远。

所以要通过相同的计算规则来刻画出算法运行效率，来评估算法会更加高效。

定义

时间复杂度描述了算法在输入规模 n 增加时，运行时间增长的速率。我们用 T(n) 表示算法的运行时间，若有一个函数 f(n)，使得当n 趋于无穷大时，${\lim }_{n\to \infty }\frac{T(n)}{f(n)}$ 是一个不等于零的常数，则称 f(n) 为T(n) 的同数量级函数，记为T(n)=O(f(n))。这里O(f(n)) 是算法的渐进时间复杂度。f(n)的形式举例：

• f(n) = 3n+1;
• f(n) = 7n^2 +1;
• f(n) = 4 n^3 + 5n^2 + 3
• …

计算步骤

1. 计算基本操作的执行次数 T(n)

• 基本操作是指算法中执行次数最多的操作。基本操作通常是算法中出现次数最多的原子操作，如赋值、比较、算术运算等。
• 分析算法最坏的情况下，这些操作的执行次数。即算法执行所需的最大时间。

2. 确定 T(n) 的数量级（按规则）

• 忽略常数因子：在计算时间复杂度时，我们忽略常数因子，用常数1来取代运行时间中所有加法常数。因为当输入规模n很大时，常数因子对算法运行时间的影响可以忽略不计。
• 忽略低阶项：我们只保留最高阶的项，因为当n趋向于无穷大时，最高阶项将决定函数的增长速率。
• 忽略最高阶项的系数：与忽略常数因子类似，最高阶项的系数在n很大时对增长速率的影响也可以忽略。

3. 使用大O表示法表示时间复杂度

• 找到一个函数f(n)，使得当n趋向于无穷大时，T(n)/f(n)的极限是一个非零常数。
• 如果这个条件满足，我们就可以说f(n)是T(n)的同数量级函数，并用T(n) = O(f(n))来表示算法的时间复杂度。

常见复杂度

按上述步骤套案例来理解

O(1)

说明

无论输入数据规模如何，执行时间都保持不变。

案例

访问数组中的元素。
在C语言中，访问数组元素通常是一个常数时间操作，即时间复杂度为O(1)。这是因为数组在内存中是连续存储的，每个元素都可以通过其索引直接访问，而不需要遍历整个数组。

#include <stdio.h>int main() {int array[10]; // 声明一个包含10个整数的数组int index, value;// 初始化数组for (index = 0; index < 10; index++) {array[index] = index;}// 访问数组元素value = array[5]; // 直接访问索引为5的元素printf("The value at index 5 is: %d\n", value);return 0;
}

分析：
无论数组的大小如何，访问数组中任意位置的元素（如array[5]）的时间是不变的。以下是为什么这是O(1)操作的原因：

• 直接访问：数组元素在内存中是连续存储的，每个元素的地址可以通过基地址加上偏移量计算得出。偏移量是元素索引乘以元素大小（对于整数通常是4或8字节）。
• 无需遍历：访问特定的数组元素不需要遍历数组中的其他元素。你可以直接使用索引来定位和访问元素。
• 时间不变：由于访问任何元素都是通过相同的计算方式，这个操作的时间不会随着数组大小的增加而增加。

还有哪些？

• 数组访问：如前所述，通过索引访问数组中的元素。
• 哈希表操作：
  • 插入一个新元素（平均情况下）。
  • 删除一个元素（平均情况下）。
  • 查找一个元素（平均情况下）。
• 栈操作：
  • 压栈（push）。
  • 出栈（pop）。
  • 查看栈顶元素。
• 队列操作（对于循环队列或双端队列）：
  • 入队（enqueue）。
  • 出队（dequeue）。
  • 查看队头或队尾元素。
• 链表操作（在已知节点的情况下）：
  • 插入一个新节点（在已知前驱节点的情况下）。
  • 删除一个节点（在已知前驱节点的情况下）。
• 树操作（在已知节点的情况下，对于特定类型的树）：
  • 插入或删除节点（在二叉搜索树中，如果树是平衡的）。
  • 查找节点（在二叉搜索树中）。
• 变量赋值：给一个变量赋值。
• 交换两个变量的值。
• 计数器增加或减少。
• 访问固定大小的集合或映射中的元素（例如，访问固定大小的哈希表）。

O(logN)

说明

表示算法的时间复杂度是输入规模 N 的对数。这里的对数通常是基数为 2 的对数（即 log₂N），但在 Big O 表示法中，我们通常忽略基数，因为它对于复杂度的渐进分析并不重要。

通常与那些能够通过每次操作减少问题规模的方式（通常是减半）的算法相关。这种类型的算法在处理大数据集时非常高效，因为它们能够在相对较少的操作次数内完成任务。

理解：

• 对数增长速度
  当 N 增加时，log(N) 的值增长得非常缓慢。例如：
  如果 N = 2，则 log₂N = 1
  如果 N = 4，则 log₂N = 2
  如果 N = 8，则 log₂N = 3
  如果 N = 16，则 log₂N = 4
  以此类推，N 每翻倍，log₂N 只增加 1。

• 效率
  O(log(N)) 复杂度的算法是非常高效的，特别是当 N 非常大时。这是因为算法执行的操作次数几乎不会随着输入规模的增长而显著增加

案例

二分查找法。

下面是用 C 语言实现二分查找的代码，并附上其时间复杂度说明：```c
#include <stdio.h>// 二分查找函数
int binarySearch(int arr[], int size, int target) {int left = 0;int right = size - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止整型溢出if (arr[mid] == target)return mid;  // 找到目标，返回索引else if (arr[mid] < target)left = mid + 1; // 目标在右侧elseright = mid - 1; // 目标在左侧}return -1; // 未找到目标
}int main() {int arr[] = {2, 3, 4, 10, 40};int size = sizeof(arr) / sizeof(arr[0]);int target = 10;int result = binarySearch(arr, size, target);if(result != -1) {printf("元素在索引 %d 处找到。\n", result);} else {printf("元素未被找到。\n");}return 0;
}

分析：

基本操作：
在二分查找中，基本操作是比较目标值与数组中间元素（arr[mid]）的大小。这一操作在每一次迭代中执行一次。比较 目标值 target 和 arr[mid]。

最多执行次数：
为了确定 T(n)，我们需要知道在最坏情况下算法需要执行多少次基本操作。

1. 初始规模：数组大小为 n。
2. 每次迭代：将数组的查找范围缩小一半。具体变化为：n→n/2→n/4→…
3. 查找范围缩小到1（即剩余一个元素需要检查，说明数组最后只剩下一个元素）。

整个算法最多需要执行多少次基本操作取决于：我们要将 n 缩小到 1 需要多少次减半操作。

计算这个次数：

1. 令 k 为需要执行的迭代次数，使得 n / $2^k$ = 1
2. 方程求解： k = ${\log }_{2}n$
   所以，T(n) =${\log }_{2}n$。

使用大 O 表示法表示时间复杂度
通过上述分析，我们知道二分查找的操作次数为 ${\log }_{2}n$。在大 O 表示中，常数因子不影响量级，因此时间复杂度为：
T(n) =${\log }_{2}n$。

在二分查找中，每次迭代都会将待查询的范围减半。这种“对半分”的策略使得每经过一次迭代，问题规模就减少一半。这种复杂度能够保证即使在非常大的数据集合中，查找操作仍能快速完成，是因为对数增长的速度非常缓慢。

还有哪些？

• 二分查找（Binary Search）：在有序数组中查找一个特定的元素。
• 平衡二叉搜索树（Balanced Binary Search Tree）操作：包括查找、插入和删除。平衡树如 AVL 树、红黑树等保证了操作的时间复杂度为 O(log(N))。
• 堆（Heap）操作：在二叉堆（如最小堆或最大堆）中进行插入、删除最小/最大元素以及构建堆等操作。
• BST（Binary Search Tree）中的成功者/失败者树操作：用于查找第 k 大/小的元素。
• 在决策树中进行决策：如果决策树是平衡的，那么找到最终决策的时间复杂度是 O(log(N))。
• 幂运算：计算 a 的 b 次幂，其中 b 是整数，可以通过快速幂算法在 O(log(N)) 时间内完成，这里 N 是 b。

O(N)

说明

O(N) 时间复杂度是用于描述算法运行时间随输入规模增长的关系的一种度量方式。这里 N 通常代表输入数据的规模，例如数组的大小、列表的长度等。

理解：

• O(N) 描述的是一种线性关系，意味着如果输入规模 N 增加一倍，算法的运行时间大致也会增加一倍。
• O(N) 时间复杂度与 N 的具体值无关，而与 N 的增长速率有关。因此，无论 N 是 10、100 还是 1000，只要输入规模增长，算法的运行时间也会以相同的速率增长。

案例

单层循环

#include <stdio.h>int main() {int n;// 假设n已经被赋值for (int i = 0; i < n; i++) {// 基本操作printf("%d\n", i);}return 0;
}

分析：

1. 基本操作：是 printf(“%d\n”, i);。
2. 确定数量级：这个基本操作在for循环中执行了n次， 此时f(n) = n。
3. 大O表示：运行时间 T(n)=O(f(n)) 等价于 T(n)=O(n)；最终时间复杂度是O(n)。

还有哪些？

• 遍历数组或列表：对一个长度为 N 的数组或列表进行一次遍历。
• 线性搜索：在未排序或已排序的数组中查找一个元素，需要遍历整个数组。
• 链表的遍历：遍历一个链表，需要访问每个节点一次。

O(N*logN)

说明

表示算法的运行时间与输入规模 N 成正比，并且还与 N 的对数成正比。这个复杂度通常出现在算法同时具有一个线性（N）和一个对数（logN）的步骤。

理解：

• 分治策略：许多分治算法具有 O(N*logN) 的时间复杂度。这些算法通常将问题分成更小的部分，然后递归地解决这些部分。
• 两层循环：想象一个算法，它包含一个循环，该循环内部还有一个循环。如果外层循环是线性的（N 次迭代），而内层循环是对数复杂度的（例如，每次迭代将问题大小减半），那么总的时间复杂度将是 O(N*logN)。

实际应用
在现实世界中，O(N*logN) 的算法通常比 O(N^2) 的算法更高效，特别是当 N 变得非常大时。例如，快速排序和归并排序通常比冒泡排序和插入排序更受欢迎，因为它们在大数据集上的性能更好。

案例

#include <stdio.h>void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}int partition(int arr[], int low, int high) {int pivot = arr[high]; // 选取最后一个元素作为基准int i = (low - 1); // 较小元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于 pivotif (arr[j] <= pivot) {i++; // 增加较小元素的索引swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}void quickSort(int arr[], int low, int high) {if (low < high) {// pi 是分区索引，arr[pi] 现在在正确的位置int pi = partition(arr, low, high);// 分别递归地排序元素quickSort(arr, low, pi - 1);  // 递归排序左子数组quickSort(arr, pi + 1, high); // 递归排序右子数组}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("Sorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

分析：

1. 基本操作的执行次数：在最坏情况下，比较次数是 $\frac{n(n-1)}{2}$
2. T(n) 的数量级：在最坏情况下，$T_{\text{比较}}=(n-1)+(n-2)+\dots +1=\frac{n(n-1)}{2}$
3. 大 O 表示法：在最坏情况下，快速排序的时间复杂度是O($n^2$)，但平均情况下是O(n*logn)

还有哪些？

• 归并排序（Merge Sort）：递归地将列表分成两半，排序后合并。
• 快速排序（平均情况）（Quick Sort）：通过选择一个“基准”元素，将数组划分为两部分并递归排序。
• 堆排序（Heap Sort）：构建一个堆数据结构，然后不断删除最大值（或最小值）并重建堆。
• Timsort：Python 的排序算法，结合归并排序和插入排序的优点，最坏情况下为 O(N*log⁡N)。

O($N^2$)

说明

指算法的执行时间与输入规模 N 的平方成正比。即随着输入规模增大，算法的运行时间会以平方倍数增长。

平方关系 意味着如果输入规模翻倍，算法的运行时间将增加到原来的四倍。例如，如果 N 从 10 增加到 20，运行时间将增加到原来的 4 倍（因为 $20^2$/ $10^2$ = 4）。

O($N^2$) 的算法通常不适合处理大规模数据集，因为它们的运行时间会随着数据规模的平方增长而变得过长。

案例

双层循环

#include <stdio.h>int main() {int n;// 假设n已经被赋值for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 基本操作printf("%d %d\n", i, j);}}return 0;
}

分析：

1. 基本操作：是 printf(“%d %d\n”, i, j);。
2. 确定数量级：外层循环执行n次，内层循环也执行n次，所以基本操作执行了n * n = $n^2$次， 此时f(n) = $n^2$。
3. 大O表示：运行时间 T(n)=O(f(n)) 等价于 T(n)=O($n^2$)；最终时间复杂度是O( $n^2$) 。 因此，时间复杂度是O($n^2$)。

还有哪些？

• 冒泡排序（Bubble Sort）：重复扫描列表，每次比较相邻元素并交换位置。
• 选择排序（Selection Sort）：每次遍历未排序的部分，选择最小（或最大）元素放到已排序部分的末尾。
• 插入排序（Insertion Sort）：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 矩阵乘法（Naive Matrix Multiplication）：两个N×N 矩阵相乘需要进行三重嵌套循环。
• Floyd-Warshall算法：计算所有节点对最短路径，用于图中的最短路径问题。
• 穷举算法（Brute Force）：在某些问题中通过穷举所有可能的解决方案来找到答案。
• 双重循环遍历：任何涉及双重循环遍历列表中所有元素对的算法（如寻找特定条件满足的所有元素对）。

O($N^3$)

说明

O(N^3)
算法的执行时间与输入规模 N 的立方成正比。即随着输入规模增大，算法的运行时间以立方倍数增长。如果有三个嵌套循环，每个循环运行N次，总迭代次数就是 N * N * N = $N^3$。

立方关系 意味着如果输入规模翻倍，算法的运行时间将增加到原来的八倍。例如，如果 N 从 10 增加到 20，运行时间将增加到原来的 8 倍（因为 20^3 / 10^3 = 8）。

随着数据规模变大，运行时间增长得非常快，所以O($N^3$)复杂度的算法在处理大规模数据时通常相当低效。

案例

#include <stdio.h>void tripleLoop(int N) {int i, j, k;int count = 0; // 用于计数基本操作的执行次数for (i = 0; i < N; i++) {for (j = 0; j < N; j++) {for (k = 0; k < N; k++) {// 这里是基本操作，比如打印或者计数count++; // 执行基本操作}}}printf("基本操作的执行次数: %d\n", count);
}int main() {int N = 10; // 假设 N 的值为 10tripleLoop(N);return 0;
}

分析：

从计算基本操作的执行次数

在这个例子中，基本操作是 count++。每次内层循环执行时，这个操作都会执行一次。因为内层循环是嵌套在最外层循环中的，所以最差情况下，基本操作的执行次数是：

• 第一层循环执行 N 次。
• 第二层循环在第一层循环的每次迭代中执行 N 次。
• 第三层循环在第二层循环的每次迭代中执行 N 次。

所以，基本操作的执行次数是 N * N * N = N^3。

确定T(n)的数量级

T(n) 表示算法运行时间与输入规模 n 的关系。在这个例子中，T(n) 与基本操作的执行次数成正比，因此 T(n) 的数量级是 N^3。

使用大O表示法表示时间复杂度
因为基本操作的执行次数是 $N^3$，所以我们可以使用大O表示法将算法的时间复杂度表示为 O($N^3$)。这意味着随着 N 的增加，算法的运行时间将按照 N 的立方的速率增长。

还有哪些？

• 矩阵乘法：传统的矩阵乘法算法具有 O($N^3$) 的时间复杂度。虽然现代计算机科学中有一些更快的算法（如Strassen算法），但基本的矩阵乘法仍然遵循 O($N^3$) 的复杂度。
• 多项式相乘：两个 degree-N 多项式的经典相乘方法具有 O($N^3$) 的时间复杂度。
• 图的着色：某些图着色问题的暴力解决方法可能会达到 O($N^3$) 的时间复杂度。
• 动态规划：某些动态规划问题，尤其是那些需要三维状态空间的，可能会有 O($N^3$) 的时间复杂度。
• 三次方程求解：数值方法求解三次方程在某些情况下可能会导致 O($N^3$) 的时间复杂度。
• 高斯消元法：在不使用优化的情况下，高斯消元法解线性方程组具有O($N^3$) 的时间复杂度。
• FFT（快速傅里叶变换）的实现：尽管 FFT 本身不是 O($N^3$) ，但是某些不正确的实现或者在多维情况下的递归调用可能会导致接近于 O($N^3$) 的性能。

O($2^N$)

说明

算法的执行时间随着输入规模 N 的指数级增加，即时间复杂度是一个指数函数，基数为2。
随着 N 增加，每增加一个单位，运行时间会翻倍。这导致增长非常快。

案例

#include <stdio.h>// 递归计算斐波那契数列的第 n 个数
long long fibonacci(int n) {if (n <= 0) {return 0;} else if (n == 1) {return 1;} else {return fibonacci(n - 1) + fibonacci(n - 2);}
}int main() {int n;printf("Enter the value of n: ");scanf("%d", &n);printf("Fibonacci number at position %d is %lld\n", n, fibonacci(n));return 0;
}

分析：

计算基本操作的执行次数

在这个递归实现中，基本操作是递归函数调用。对于 fibonacci(n)，它会调用 fibonacci(n-1) 和 fibonacci(n-2)。每次递归调用都会进行一次加法操作。

确定 T(n) 的数量级
递归斐波那契数列的递归树可以非常直观地展示 T(n) 的数量级。每个递归调用都会生成两个新的递归调用，直到达到基本情况。递归树的大小大约是 2^n ，因为每个节点都有两个子节点。

使用大O表示法表示时间复杂度
递归斐波那契数列的时间复杂度是 O(2^n)，因为每个递归级别都大约是前一个的两倍，而递归的深度是 n。

还有哪些？

• 子集生成：生成一个集合的所有子集。对于大小为N的集合，有 2^N 个可能的子集。
• 幂集：与子集生成类似，幂集是指一个集合的所有子集的集合，因此其大小为 2^N。
• 递归斐波那契数列计算：使用简单的递归方法（没有记忆化或动态规划优化）来计算斐波那契数列的第 N 个数。
• 旅行商问题（TSP）的暴力解法：尝试所有可能的路径组合来找到最短路径，对于 N 个城市的 TSP，可能的路径数量是 N!，但如果只考虑路径的子集，则可以认为是O(2^N)。
• 布尔可满足性问题（SAT）：在布尔可满足性问题中，如果使用暴力方法尝试所有可能的真值赋值，复杂度为O(2^N). 其中 N 是布尔变量的数量。
• 密码学中的穷举攻击：在密码学中，尝试所有可能的密钥来破解加密信息，如果密钥空间是 N 位，那么可能的密钥数量是2^N。

O(n!)

说明

算法的执行时间随着输入规模 N 的阶乘增长。阶乘 n! 表示从 1 乘到n 的所有整数的积。

随着 N 的增加，运行时间会以非常快的速度增长，比指数级的 O(2^N) 还要快。这是因为阶乘增长的速度远远超过多项式、指数甚至双重指数的增长速度。

特点：

• 非常低效：对于任何大于很小的n值，具有O(n!)时间复杂度的算法在实践中都是不可行的。
• 完全指数级增长：n!的增长速度远远超过2^n或n2这样的常见复杂度。

示例：一个简单的例子是计算所有n个元素的排列。对于n个元素，总共有n!种不同的排列方式，如果我们要列举出所有排列，那么算法的时间复杂度就是O(n!)。

直观感受为什么这么差：

• 考虑n=10的情况：
  10! = 3,628,800 这意味着如果有一个O(n!)的算法来处理10个元素，它需要进行大约3.6百万次基本操作。

• 对于更大的n值，情况会迅速恶化：
  20! ≈ 2.43 * 10^18
  30! ≈ 2.65 * 10^32

案例

C语言实现的排列生成算法。该算法使用递归来生成一个包含n个元素的集合的所有可能排列。

#include <stdio.h>void swap(int *x, int *y) {int temp = *x;*x = *y;*y = temp;
}void permute(int *array, int start, int end) {if (start == end) {for (int i = 0; i <= end; i++) {printf("%d ", array[i]);}printf("\n");} else {for (int i = start; i <= end; i++) {swap((array + start), (array + i));permute(array, start + 1, end);swap((array + start), (array + i)); // backtrack}}
}int main() {int n;printf("Enter the number of elements: ");scanf("%d", &n);int array[n];printf("Enter %d elements: ", n);for (int i = 0; i < n; i++) {scanf("%d", &array[i]);}printf("All possible permutations are:\n");permute(array, 0, n - 1);return 0;
}

分析：

基本操作的执行次数
对于排列生成算法，每次递归调用都会尝试将每个元素放在当前位置，然后递归地排列剩余的元素。对于每个元素，我们都需要执行以下操作：

1. 交换当前元素与它后面的元素。
2. 递归排列剩余元素。
3. 再次交换回来以恢复原始状态（回溯）。

在每一层递归中，我们需要进行 n-i 次交换（其中 i 是当前的递归深度）。在最坏的情况下，我们会有 n 层递归，每一层递归都会执行 n-i 次交换。

还有哪些？

• 排列生成：生成一个集合的所有可能排列。例如，生成一个包含n个元素的集合的所有排列，会有n!种不同的排列方式。
• 旅行商问题（TSP）：寻找最短路径访问一系列城市并返回起点的最优解。当使用暴力搜索算法时，其时间复杂度为O(n!)，因为需要考虑所有可能的路径排列。
• 子集和问题：在给定的正整数集合中找到所有和为特定值的子集。如果使用穷举所有可能的子集，其时间复杂度接近O(n!)。
• 作业调度问题：在考虑所有可能的作业顺序时，例如，当有n个作业需要调度，并且每个作业都有特定的处理时间，要找到最优的作业顺序，其时间复杂度是O(n!)。
• 括号匹配问题：生成所有可能的括号匹配序列。例如，对于n对括号，总共有n!/(n!(n-1)!/2!) = n!/(n*(n-1)!/2)种可能的匹配方式。
• 组合问题：在考虑所有可能的组合时，特别是当需要考虑组合的排列时，时间复杂度可能会达到O(n!)。

复杂度比较

大小关系

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶) < O(n!) (阶乘)

图表

这些算法的复杂度就是数学层面的问题了，可以通过图表来进行分析。

图表理解：
以下是各个时间复杂度对应的曲线斜率特征：

1. O(1) - 常数阶:曲线斜率为0。这意味着无论输入规模n如何变化，算法的运行时间保持不变，所以曲线是一条水平线。
2. O(log n) - 对数阶:曲线增长很慢，斜率逐渐减小，这意味着随着 n 增加，性能影响很小。
3. O(n) - 线性阶:曲线是一条斜直线，斜率恒定。运行时间直接与 n 成正比。
4. O(n^2) - 平方阶:曲线是抛物线，斜率随着 n 增加而线性增加。性能影响比线性算法显著。
5. O(n^3) - 立方阶:曲线斜率增长速度比平方阶更快。随着n的增加，曲线的斜率急剧上升，表示算法运行时间的增长速度非常快。
6. O(2^n) - 指数阶:曲线斜率以指数速度增长。在指数函数的曲线中，随着n的增加，斜率几乎垂直上升，表明算法运行时间急剧增加。
7. O(n!) - 阶乘阶:曲线斜率增长速度超过所有上述复杂度。阶乘函数的曲线几乎在每一个点上的斜率都比前一个点大得多，表明算法运行时间随n的增加而以更快的速度增长。

常见算法的复杂度

PS:之后会针对以上的每一种算法进行详细分析。

解惑

补充数学知识-对数和指数

指数函数

指数函数具有形式f(x) = $a^x$，其中：a>0 且 a != 1。

举例：
f(x)=$2^x$

• f(0) = $2^0$ = 1
• f(1) = $2^1$ = 2
• f(2) = $2^2$ = 4
• f(3) = $2^3$ = 8
• f(4) = $2^4$ = 16

实例分析：
举例分析： 假设有一个细菌群体，每20分钟分裂一次，即细菌数量每20分钟翻一番。我们可以用指数函数来描述这个增长过程。

设初始时刻（t=0）细菌数量为P0，则t分钟后细菌数量P(t)可以表示为： P(t) = P0 * 2^(t/20)

例如，如果初始时刻细菌数量为100个，那么40分钟后细菌数量为： P(40) = 100 * 2^(40/20) = 100 * 2^2 = 100 * 4 = 400个

对数函数

对数函数的形式是g(x) = ${\log }_a(x)$，其中：a>0 且 a != 1。

举例：g(x) = ${\log }_2(x)$

• g(0) = ${\log }_2(0)$ = 0
• g(2) = ${\log }_2(2)$ = 1
• g(4) = ${\log }_2(4)$ = 2
• g(8) = ${\log }_2(8)$ = 3
• g(16) = ${\log }_2(16)$ = 4

实例分析：
现在考虑一个国家的人口增长。在初期，由于资源丰富，人口增长较快，但随着人口数量的增加，资源变得有限，增长速度逐渐减慢。这种增长模式可以用对数函数来近似描述。

设初始年份（t=0）人口为 P${}_0$ ，每年人口增长的比例为固定的r，则t年后人口 P(t) 可以表示为：
$P(t)=P_0\times (1+r{)}^t$

如果我们假设人口增长的比例随人口数量的增加而减少，那么人口增长的对数模型可以表示为：
$\log \left(\frac{P(t)}{P_0}\right)=\log \left(\frac{P_0\times (1+r{)}^t}{P_0}\right)=\log (1+r{)}^t=t\times \log (1+r)$

或者，如果我们想表示人口随时间的增长关系，可以使用以下指数形式：

$P(t)=P_0\times (1+r{)}^t$

分析过程：

1. 初始条件：假设初始年份人口 P${}_0$ 为 100万人, 年增长率为5%。

2. 时间点1：第1年末, 人口增长到 100万 $\times (1+0.05{)}^1$ = 105万。

3. 时间点2：第2年末, 人口增长到 100万 $\times (1+0.05{)}^2$ = 110.25万。

4. 时间点3：第3年末, 人口增长到 100万 $\times (1+0.05{)}^3$ = 115.7625万。

省略log(N) 底数

为什么计算复杂度：log${}_2$(N) 和 log${}_8$(N) 之间的差异只是一个常数，它们都被简化为 O(log(N))？

因为不同底数的对数可以相互换算：${\log }_a(N)=\frac{{\log }_b(N)}{{\log }_b(a)}$

例如：

${\log }_{10}(N)=\frac{{\log }_2(N)}{{\log }_2(10)}$

可以转换成：${\log }_{10}(N)=C\cdot {\log }_2(N)$，其中$C=\frac{1}{{\log }_2(10)}$。

所以：
$O(C\cdot {\log }_2(N))\equiv O({\log }_2(N))\equiv O(\log (N))$

为什么复杂度会分3种情况

时间复杂度分为最好情况、一般情况和最坏情况，是为了全面理解算法在不同情境下的性能表现：

1. 最好情况：

   • 这是算法执行得最快的情境。通常由于输入数据已经接近目标，算法所需的操作数量最少。
   • 分析最好情况有助于了解算法在理想条件下的潜在效率。

2. 一般情况（平均情况）：

   • 反映算法在典型或平均输入条件下的性能。它考虑了所有可能输入的概率分布。
   • 这种分析通常更能代表算法的实际性能表现，对预期性能评估很重要。

3. 最坏情况：

   • 描述算法在最不利输入条件下的性能。这里需要进行最多的操作。
   • 这种分析确保算法在任何情况下都能接受，并用于保证性能上界。

AI算法中的复杂度怎么计算？

1. 确定关键操作

• 矩阵运算：如矩阵乘法，这是大多数 AI 算法的核心计算。
• 激活函数：计算激活函数的复杂度。

2. 评估模型规模

• 层数：神经网络的层数和每层的节点数量。
• 参数数量：模型的总参数数会影响计算复杂度。

3. 分析训练流程

• 前向传播：每层计算输出的复杂度。
• 反向传播：梯度计算的复杂度。

4. 考虑数据规模

• 样本数：每次迭代要处理的训练数据数量。
• 特征数：输入数据的维度。

5. 合并计算

• 单次迭代：前向和反向传播的复杂度。
• 总复杂度：乘以迭代次数得到总复杂度。