目录
1 执行时间的度量方法
1.1 事后统计
1.2 事前分析
2 时间复杂度的理解
2.1 基本概念
2.2 大 O 渐进表示法
2.3 时间复杂度的意义
3 时间复杂度的计算
3.1 技巧概述
3.2 案例分析 1
3.3 案例分析 2
4 常见的时间复杂度
4.1 多项式时间复杂度
4.2 指数时间复杂度
4.3 增长速度排序
5 时间复杂度的分析案例
5.1 O(1) - 常数时间复杂度
5.2 O(log n) - 对数时间复杂度
5.3 O(sqrt(n)) - 平方根阶
5.4 O(n) - 线性时间复杂度
5.5 O(n log n) - 线性对数时间复杂度
5.6 O(n^2) - 平方时间复杂度
5.7 O(n^3) - 立方时间复杂度
5.8 O(2^n) - 指数时间复杂度
5.9 O(n!) - 阶乘时间复杂度
5.10 O(n^n) - 超指数时间复杂度
1 执行时间的度量方法
评估算法的时间开销，通常采用两种方法：事后统计和事前分析。
1.1 事后统计
事后统计是指通过实际运行基于算法编写的程序，利用计算机内部机制记录程序执行时间和实际占用的空间。
优点：
- 直接反映了算法在具体环境下的表现。
缺点：
- 必须先编写并运行程序。
- 结果受硬件性能、操作系统、编程语言等因素影响较大，难以直接反映算法本身的优劣。
- 不适合快速比较不同算法的性能。
1.2 事前分析
事前分析则是通过数学方法推导出算法的时间界限函数，不依赖于具体的硬件和软件环境。
相关因素：
- 算法选用的策略（例如，分治、贪心、动态规划等）。
- 问题的规模（例如，数组的长度、图的顶点数等）。
- 数据的初始状态（例如，数据是否已经部分排序）。
- 编程语言的选择。
- 编译器生成的机器代码质量。
- 计算机执行指令的速度。
简化假设：
- 为了简化分析，通常忽略硬件和编程语言的影响，假设一个特定算法的时间度量 T 主要依赖于问题的规模 n，即 T(n)。
2 时间复杂度的理解
2.1 基本概念
时间复杂度是一种评估算法效率的方法，它描述了算法中基本操作的总次数随问题规模增长的趋势，而不是具体的执行时间。
基本操作：算法中最核心的操作，通常是最耗时的部分。
问题规模：问题的大小，通常用 n 表示（例如，数组的长度、图的顶点数等）。
时间复杂度：用大 O 符号表示，形式为 T(n) = O(f(n))，其中 f(n) 是问题规模 n 的函数。
2.2 大 O 渐进表示法
大 O 符号用于描述函数的渐近行为，即当 n 趋向于无穷大时，算法的基本操作次数的增长趋势。表示方法为 T(n) = O(f(n))。常见的几种时间复杂度包括：
O(1) - 常数时间复杂度
这是最理想的复杂度，表示算法的执行时间不会随着输入数据规模 n 的增长而变化。无论输入数据有多大，算法的执行时间都是一个常数。例如，访问数组中的某个元素的时间复杂度就是 O(1)。
O(log n) - 对数时间复杂度
表示算法的执行时间随着输入数据规模 n 的增长呈对数增长。这种类型的算法通常通过每次迭代减少问题的规模来实现高效的性能，比如二分查找。这里的底数通常不重要，因为不同底数的对数函数在大 O 记号下是等价的，如对于 O(log2(n)) 等价于 O(log n)。
O(√n) - 平方根时间复杂度
平方根时间复杂度 O(√n) 表示算法的执行时间与输入数据规模 n 的平方根成正比。这意味着如果输入数据规模增加四倍，算法的执行时间会增加两倍。这种复杂度的算法通常通过逐步增加步长或逐步减少问题规模来实现高效的性能。
O(n) - 线性时间复杂度
表示算法的执行时间与输入数据规模 n 成正比。这意味着如果输入数据规模增加一倍，算法的执行时间也大约会增加一倍。遍历数组或列表中的所有元素就是一个线性时间复杂度的例子。
O(n log n) - 线性对数时间复杂度
这种复杂度常见于一些高效的排序算法，如快速排序、归并排序等。这类算法通常涉及将问题分解成更小的问题（分治法），然后合并这些子问题的解。执行时间随着输入数据规模的增加而增加，但增加的速度慢于 O(n^2)。
O(n^2) - 平方时间复杂度
当算法中存在嵌套循环时，可能会出现这种时间复杂度。每个内层循环都会遍历整个数据集，导致总的执行时间为 n 乘以 n。冒泡排序和选择排序是具有 O(n^2) 时间复杂度的典型例子。
O(n^3) - 立方时间复杂度
类似于 O(n^2)，但是涉及到三层嵌套循环的情况。这种复杂度的算法在处理大数据集时效率非常低，应该尽量避免使用。
O(n^k), k > 3 - 多项式时间复杂度
这里 k 是一个大于 3 的常数。当 k 较大时，这种复杂度的算法效率非常低，通常只适用于小规模的数据集。
O(2^n) - 指数时间复杂度
这种复杂度的算法随着输入数据规模 n 的增加，执行时间呈指数级增长。这类算法通常用于解决需要探索所有可能性的问题，如某些组合优化问题。对于稍大的数据集，这类算法可能变得不可行。
O(n!) - 阶乘时间复杂度
这是最差的时间复杂度之一，通常出现在需要考虑所有排列情况的算法中，如旅行商问题的暴力解法。这类算法的执行时间随输入规模的增长而极其迅速地增加。
O(n^n) - 超指数时间复杂度
这个复杂度比 O(2^n) 还要高，意味着算法的执行时间随输入规模的增长而极其迅速地增加。这种复杂度非常罕见，通常只出现在理论讨论中。
2.3 时间复杂度的意义
时间复杂度帮助我们评估算法在不同规模下的性能，选择最优的算法。通过分析时间复杂度，可以找到算法的瓶颈，进行针对性的优化。此外，时间复杂度提供了一种理论上的评估方法，使得算法的性能评估更加客观和科学。
3 时间复杂度的计算
3.1 技巧概述
计算时间复杂度的技巧主要包括直接观察法和举例验证法。通过这些方法，我们可以确定算法中基本操作的执行次数，并将其表示为问题规模的函数 f(n)，然后取其增长最快的项。
- 直接观察法：通过仔细分析算法中的每个步骤，确定每个步骤的执行次数，并将这些次数相加，得到总的执行次数。这种方法适用于结构较为简单、步骤清晰的算法。
- 举例验证法：通过具体的例子，手动计算算法在不同规模下的执行次数，从而验证和确认时间复杂度。这种方法适用于复杂度较高的算法，通过具体的数据验证理论分析的正确性。
3.2 案例分析 1
考虑以下代码片段：
#include <stdio.h>void PlayGame(int n) // n 为问题规模
{int i = 1; // 执行 1 次while (i <= n) // 执行 n + 1 次{ printf("数据已加载%.2lf%,即将开始\n", (i + 0.0) / n * 100); // 执行 n 次i++; // 执行 n 次}printf("数据加载完毕，开始战斗吧！"); // 执行 1 次
}int main()
{PlayGame(200);return 0;
}将所有操作的执行次数相加，得到总的执行次数：T(n) = 1 + (n + 1) + n + n + 1 = 3n + 3。
时间复杂度描述的是算法中基本操作的总次数随问题规模增长的趋势。在这种情况下，T(n) = 3n + 3 是一个线性函数。为了简化表示，我们使用大 O 符号来描述时间复杂度：T(n) = O(3n + 3)。由于常数项和低阶项在大 O 表示法中可以忽略不计，因此最终的时间复杂度为：T(n) = O(n)。
3.3 案例分析 2
考虑以下代码片段：
int m = 5;
int n = 10;
for (int i = 0; i < m; i++)
{for (int j = 0; j < n; j++){printf("我执行了多少次呢？\n");}
}步骤1：分析每个循环的执行次数
- 外层循环从
i = 0到i < m，共执行m次。 - 内层循环从
j = 0到j < n，共执行n次。 - 每次内层循环都会执行一次
printf语句。
步骤2：计算总的执行次数
- 外层循环执行
m次，每次外层循环中，内层循环执行n次。 - 因此，
printf语句总共执行的次数为：T(m,n) = m × n。
步骤3：确定时间复杂度
在这个例子中，m 和 n 都是独立的问题规模参数。如果我们将 m 和 n 视为独立的变量，那么时间复杂度为：T(m,n)=O(m×n)。
如果我们将 m 和 n 都视为同一个问题规模 n，即 m = n，那么时间复杂度为：
总结
通过直接观察法，我们确定了 printf 语句的执行次数为 m * n。因此，该代码的时间复杂度为 O(m×n)。如果 m 和 n 都是同一个问题规模 n，则时间复杂度为 O(n^2)。
4 常见的时间复杂度
在时间复杂度分析中，通常将时间复杂度分为多项式时间复杂度和指数时间复杂度。具体来说：
4.1 多项式时间复杂度
包括形如 的时间复杂度，其中 k 是一个常数。常见的多项式时间复杂度有
、
、
、
、
、
和
等。
4.2 指数时间复杂度
包括形如 的时间复杂度，其中 a > 1。常见的指数时间复杂度有
、
、
、
等。当 k > 3 时，多项式时间复杂度
也可以被视为接近指数时间复杂度，因为它们的增长速度非常快。
4.3 增长速度排序
部分证明（了解）：
当 n 趋向 +∞ 时，n 比 logn 变大的速度快很多。
当 n 趋向 +∞ 时，2^n 比 n^2 变大的速度快很多。
提示：
在实际应用中，选择具有较低时间复杂度的算法可以显著提高程序的运行效率，特别是在处理大量数据时。然而，时间复杂度并不是选择算法的唯一标准，空间复杂度、实现难度、代码可读性和维护性等因素也需要考虑。
5 时间复杂度的分析案例
5.1 O(1) - 常数时间复杂度
定义：
常量阶 O(1) 时间复杂度表示算法的执行时间与输入数据的大小无关。无论输入数据增大多少倍，算法的执行时间和空间消耗都保持不变。这种时间复杂度的算法被认为是高效的，因为它们在处理大规模数据时表现稳定。
常见场景：
常量阶 O(1) 时间复杂度的算法通常出现在以下场景中：
- 单个操作或固定数量的操作，不依赖于输入数据的大小。
- 没有循环或递归，或者循环和递归的次数与输入数据的大小无关。
示例：
下面是一个计算从 1 到 n 的整数之和的函数 Sum1，其时间复杂度为 O(1)：
void Sum1(int n)
{int sum = 0; // 执行 1 次sum = (1 + n) * n / 2; // 执行 1 次printf("testSum1:%d\n", sum); // 执行 1 次
}在这个函数中，每条语句都只执行一次，且执行次数与输入参数 n 无关。因此，该函数的时间复杂度为 O(1)。
5.2 O(log n) - 对数时间复杂度
定义：
对数时间复杂度 O(log n) 表示算法的执行时间与输入数据规模 n 的对数成正比。这种复杂度的算法通常通过每次迭代减少问题的规模来实现高效的性能。具体来说，每次迭代后，问题的规模会减小一半或更少。因此，即使输入数据规模很大，算法的执行时间也不会显著增加。
常见场景：
对数时间复杂度 O(log n) 的算法通常出现在以下场景中：
- 二分查找：在有序数组中查找特定元素。
- 分治法：将问题分解为更小的子问题，然后合并子问题的解。
- 快速幂：高效计算幂运算。
- 平衡二叉树的插入和查找操作。
示例：
下面是一些典型的对数时间复杂度 O(log n) 的算法示例。
示例1：每次乘以 2 的循环
下面是一个简单的循环，每次迭代将变量 i 乘以 2，直到 i 超过 n。
void test1(int n) {int i = 1;while (i <= n) {i *= 2;}
}- 经过 m 次迭代后，i 的值为 2^m。
- 当 2^m > n 时，循环结束，可知循环次数 m 满足： 2^m <= n，解得 m <= log n。
- 因此，上面代码的时间复杂度为 O(log n)。
示例2：二分查找
二分查找是一种在有序数组中查找特定元素的高效算法。通过每次迭代将搜索范围减半，可以在对数时间内找到目标元素。
int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { // 当左边界小于等于右边界时，继续查找 // 计算中间索引，使用 left + (right - left) / 2 防止直接 (left + right) / 2 导致的整数溢出 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; // 如果循环结束还没有找到目标元素，则返回-1表示未找到
} - 每次迭代将搜索范围减半，因此时间复杂度为 O(log n)。
- 具体来说，经过 m 次迭代后，搜索范围从 n 缩小到 1，即 n / 2^m = 1，解得 m = log n。
5.3 O(sqrt(n)) - 平方根阶
定义：
平方根时间复杂度 O(√n) 表示算法的执行时间与输入数据规模 n 的平方根成正比。这意味着如果输入数据规模增加四倍，算法的执行时间会增加两倍。这种复杂度的算法通常通过逐步增加步长或逐步减少问题规模来实现高效的性能。
常见场景
平方根时间复杂度 O(√n) 的算法通常出现在以下场景中：
- 检查一个数是否为质数。
- 查找数组中的某个特定模式。
- 一些特定的数学问题，如求解平方根。
示例
下面是一些典型的平方根时间复杂度 O(√n) 的算法示例。
示例1：逐步增加步长
void fun(int n) {int i = 0, s = 0;while (s < n) {// 基本操作i++;s = s + i;}
}- 每次迭代将
i增加 1，并将i加到s上。 - 假设循环执行 m 次结束，则有 s1 = 1, s2 = 1 + 2 = 3, s3 = 1 + 2 + 3 = 6, ..., sm = 1 + 2 + 3 + ... + m = m(m + 1) / 2。
- 可知，循环次数 m 满足：m(m + 1) / 2 < n。
- 解不等式 m(m + 1) / 2 < n，得到 m(m + 1) < 2n。
- 进一步简化，得到 m^2 + m - 2n < 0。
- 由求根公式得 m = (-1 + sqrt(1 + 8n)) / 2，m ≈ sqrt(2n) - 1/2
- 因此，时间复杂度为 O(√n)。
示例2：检查一个数是否为质数
bool isPrime(int n) {if (n <= 1) {return false;}if (n <= 3) {return true;}if (n % 2 == 0 || n % 3 == 0) {return false;}for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) {return false;}}return true;
}- 检查一个数是否为质数时，只需要检查到 √n 即可。
- 因此，循环
for (int i = 5; i * i <= n; i += 6)的时间复杂度为 O(√n)。
5.4 O(n) - 线性时间复杂度
定义：
线性时间复杂度 O(n) 表示算法的执行时间与输入数据规模 n 成正比。这意味着如果输入数据规模增加一倍，算法的执行时间也会大约增加一倍。这种复杂度的算法通常涉及遍历整个数据集的每个元素。
常见场景：
线性时间复杂度 O(n) 的算法通常出现在以下场景中：
- 遍历数组或列表中的所有元素。
- 简单的查找操作。
- 累加或统计操作。
示例：
下面是一些典型的线性时间复杂度 O(n) 的算法示例。
示例1：打印 "test" n 次
void Sum2(int n) {for (int i = 1; i <= n; i++) { printf("test"); // 执行 n 次}
}在这个函数中，printf 语句在循环中执行 n 次，因此总的时间复杂度为 O(n)。
示例2：计算从 1 到 n 的整数之和
void Sum3(int n) {int i, sum = 0; // 执行 1 次for (i = 1; i <= n; i++) {sum += i; // 执行 n 次}printf("testSum3:%d\n", sum); // 执行 1 次
}在这个函数中，sum += i 语句在循环中执行 n 次，因此总的时间复杂度为 O(n)。
示例3：从数组中查找目标元素
// 定义一个函数，用于在数组中搜索一个目标值
void Search(int arr[], int n, int target) { // 使用 for 循环遍历数组中的每个元素 for (int i = 0; i < n; i++) { // 检查当前元素是否等于目标值 if (arr[i] == target) { // 如果找到目标值，打印目标值 printf("%d", target); // 找到目标值后退出循环，不再继续搜索 break; } }
} - 最好时间复杂度：如果目标元素
target在数组的第一个位置，循环只执行一次，时间复杂度为 O(1)。 - 最坏时间复杂度：如果目标元素
target在数组的最后一个位置或不存在，循环执行 n 次，时间复杂度为 O(n)。 - 平均时间复杂度：假设目标元素
target在数组中任意位置的概率相同（1/n），则平均时间复杂度为 O(n)。因为，循环次数为（1+n）/2，则 T(n)=O(x)=O(n)。
示例4：自增循环
void func(int n) {int i = 1, j = 100;while (i < n) {// 基本操作j++;i += 2;}
}- i 的初值为 1，每次自增 2。假设 i 自增 m 次后循环结束，则 i 最后的值为 1 + 2m。
- 循环结束的条件是 i >= n，因此有 1 + 2m ≥ n。
- 解不等式 1 + 2m ≥ n，得到 2m ≥ n - 1，进一步得到 m ≥ (n - 1) / 2。
- 因此，循环执行的次数 m 为 (n - 1) / 2。
- 由于时间复杂度只关心最高阶项，忽略常数项，因此时间复杂度 T(n) = O(n)。
5.5 O(n log n) - 线性对数时间复杂度
定义：
线性对数时间复杂度 O(n log n) 表示算法的执行时间与输入数据规模 n 和其对数 log n 的乘积成正比。这种复杂度的算法通常通过将问题分解为更小的子问题，然后合并这些子问题的解来实现高效的性能。具体来说，每次迭代后，问题的规模会减小一半，同时需要进行线性的合并操作。
常见场景：
线性对数时间复杂度 O(n log n) 的算法通常出现在以下场景中：
- 高效的排序算法，如快速排序、归并排序。
- 分治法，将大问题分解为多个小问题，然后合并解。
- 二叉堆的构建和操作。
- 计算几何中的分治算法，如最近点对问题。
示例：内外层循环
void test3(int n) {int x;for (int i = 0; i < n; i++) {x = 1;while (x < n / 2) {x = 2 * x;}}
}- 内层循环
while (x < n / 2)中，每次迭代将x乘以 2，直到x超过n / 2。 - 设内层循环执行了 m 次，那么 2^m > n / 2，解得 m = log(n / 2) = log n - 1。
- 因此，内层循环的时间复杂度为 O(log n)。
- 外层循环
for (int i = 0; i < n; i++)执行 n 次。 - 因此，总的时间复杂度为 O(n * log n)。
5.6 O(n^2) - 平方时间复杂度
定义：
平方时间复杂度 O(n^2) 表示算法的执行时间与输入数据规模 n 的平方成正比。这意味着如果输入数据规模增加一倍，算法的执行时间会增加四倍。这种复杂度的算法通常涉及嵌套循环，每个内层循环都会遍历整个数据集。
常见场景：
平方时间复杂度 O(n^2) 的算法通常出现在以下场景中：
- 双层遍历：遍历二维数组或矩阵。
- 冒泡排序算法：通过多次遍历数组，每次将最大的元素移到末尾。
- 插入排序算法：通过多次遍历数组，将每个元素插入到已排序的部分中。
示例：
下面是一些典型的平方时间复杂度 O(n^2) 的算法示例。
示例1：双层遍历
void Add(int x, int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {x = x + 1;}}
}- 内层循环
for (int j = 0; j < n; j++)执行 n 次。 - 外层循环
for (int i = 0; i < n; i++)也执行 n 次。 - 因此，总的时间复杂度为 O(n * n) = O(n^2)。
示例2：嵌套循环计数
void func(int n) {int x = 0;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {++x;}}
}- 内层循环
for (int j = i + 1; j < n; ++j)的执行次数随着i的增加而减少。 ++x位于最内层循环中，因此取++x作为基本操作。- 显然，
n为规模，可以算出++x的执行次数为 f(n) =(n-1)+(n-2)+…+1 = n(n-1)/2。 - 变化最快的项为 n²/2，因此时间复杂度为 T(n) = O(n^2)。
示例3：多层循环累加
int SumFunc(int n) {int sum = 0; // 执行 1 次for (int i = 0; i < 100; i++) {sum += i; // 执行 100 次}for (int i = 0; i < n; i++) {sum += i; // 执行 n 次}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {sum += i; // 执行 n * n 次}}return sum;
}- 第一个循环
for (int i = 0; i < 100; i++)执行 100 次。 - 第二个循环
for (int i = 0; i < n; i++)执行 n 次。 - 第三个循环
for (int i = 0; i < n; i++)和for (int j = 0; j < n; j++)执行 n * n 次。 - 因此，总的时间复杂度为 1 + 100 + n + n^2。
- 大 O 表示法，取最高阶 n^2，所以是 O(n^2)。
5.7 O(n^3) - 立方时间复杂度
定义：
立方时间复杂度 O(n^3) 表示算法的执行时间与输入数据规模 n 的立方成正比。这意味着如果输入数据规模增加一倍，算法的执行时间会增加八倍。这种复杂度的算法通常涉及三层嵌套循环，每层循环都会遍历整个数据集。
常见场景：
立方时间复杂度 O(n^3) 的算法通常出现在以下场景中：
- 三维数组或矩阵的遍历。
- 一些复杂的动态规划问题。
- 一些特定的图论算法，如 Floyd-Warshall 算法（用于求解所有节点对之间的最短路径）。
示例：三层嵌套循环
int test1(int n) {int sum = 0; // 执行 1 次for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {sum++; // 执行 n * n * n 次}}}return sum; // 执行 1 次
}int main() {int sum = test1(5);printf("sum = %d\n", sum); // 125 => 5^3
}- 最内层循环
for (int k = 0; k < n; k++)执行 n 次。 - 中间层循环
for (int j = 0; j < n; j++)也执行 n 次。 - 外层循环
for (int i = 0; i < n; i++)也执行 n 次。 - 因此，总的时间复杂度为 O(n * n * n) = O(n^3)。
5.8 O(2^n) - 指数时间复杂度
定义：
指数时间复杂度 O(2^n) 表示算法的执行时间与输入数据规模 n 的指数成正比。这意味着如果输入数据规模增加一倍，算法的执行时间会增加两倍。这种复杂度的算法通常涉及递归或回溯，每次递归调用都会产生两个或更多新的递归调用。指数时间复杂度的算法在处理大规模数据时非常低效，但在某些特定问题中仍然是必要的。
常见场景：
指数时间复杂度 O(2^n) 的算法通常出现在以下场景中：
- 递归算法，如计算斐波那契数列。
- 回溯算法，如解决旅行商问题（TSP）、子集和问题。
- 动态规划问题，如某些背包问题的朴素解法。
示例：
下面是一些典型的指数时间复杂度 O(2^n) 的算法示例。
示例1：计算斐波那契数列
int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);
}- 每次递归调用
fibonacci(n - 1)和fibonacci(n - 2)，都会产生两个新的递归调用。 - 因此，递归树的高度为 n，每一层的节点数都是前一层的两倍。
- 总的时间复杂度为 O(2^n)。
示例2：子集和问题
bool subsetSum(int set[], int n, int sum) {if (sum == 0) {return true;}if (n == 0 && sum != 0) {return false;}if (set[n - 1] > sum) {return subsetSum(set, n - 1, sum);}return subsetSum(set, n - 1, sum) || subsetSum(set, n - 1, sum - set[n - 1]);
}- 每次递归调用
subsetSum(set, n - 1, sum)和subsetSum(set, n - 1, sum - set[n - 1])，都会产生两个新的递归调用。 - 因此，递归树的高度为 n，每一层的节点数都是前一层的两倍。
- 总的时间复杂度为 O(2^n)。
5.9 O(n!) - 阶乘时间复杂度
定义：
阶乘时间复杂度 O(n!) 表示算法的执行时间与输入数据规模 n 的阶乘成正比。这意味着如果输入数据规模增加一倍，算法的执行时间会增加一个数量级。这种复杂度的算法通常涉及全排列或组合问题，每次递归调用都会产生多个新的递归调用。阶乘时间复杂度的算法在处理大规模数据时非常低效，但在某些特定问题中仍然是必要的。
常见场景：
阶乘时间复杂度 O(n!) 的算法通常出现在以下场景中：
- 全排列问题：生成所有可能的排列。
- 旅行商问题（TSP）：寻找最短路径，涉及所有城市的排列。
- 组合问题：生成所有可能的组合。
示例：
下面是一些典型的阶乘时间复杂度 O(n!) 的算法示例。
示例1：生成全排列
#include <stdio.h>// 交换两个整数的值
void swap(int *x, int *y) {int temp = *x; // 临时变量存储 *x 的值*x = *y; // 将 *y 的值赋给 *x*y = temp; // 将临时变量的值赋给 *y
}// 生成数组的所有排列
void permute(int *array, int start, int end) {// 如果 start 等于 end，说明已经到达叶子节点，输出当前排列if (start == end) {for (int i = 0; i <= end; i++) {printf("%d ", array[i]); // 输出当前排列的一个元素}printf("\n"); // 换行，表示一个完整的排列} else {// 从 start 到 end 进行递归for (int i = start; i <= end; i++) {swap(&array[start], &array[i]); // 交换 start 和 i 位置的元素permute(array, start + 1, end); // 递归生成剩余部分的排列swap(&array[start], &array[i]); // 回溯，恢复数组状态}}
}int main() {int array[] = {1, 2, 3}; // 定义一个数组int n = sizeof(array) / sizeof(array[0]); // 计算数组的长度permute(array, 0, n - 1); // 调用 permute 函数生成所有排列return 0;
}- 每次递归调用
permute(array, start + 1, end)，都会产生n - start个新的递归调用。 - 因此，递归树的高度为 n，每一层的节点数都是前一层的 n - start 倍。
- 总的时间复杂度为 O(n!)。
示例2：旅行商问题（TSP）
#include <stdio.h>
#include <limits.h> // 引入 limits.h 以使用 INT_MAX#define V 4 // 定义顶点数量// 返回两个整数中的较小者
int min(int a, int b) {return (a < b) ? a : b;
}// 旅行商问题 (TSP) 的递归函数
int tsp(int graph[][V], int s, int visited[], int count, int cost, int &ans) {// 如果所有城市都已访问且从最后一个城市到起始城市有路径if (count == V && graph[s][0] > 0) {ans = min(ans, cost + graph[s][0]); // 更新最小成本return ans;}// 尝试访问每个未访问的城市for (int i = 0; i < V; i++) {if (!visited[i] && graph[s][i] > 0) { // 如果城市 i 未被访问且从 s 到 i 有路径visited[i] = 1; // 标记城市 i 为已访问// 递归访问下一个城市tsp(graph, i, visited, count + 1, cost + graph[s][i], ans);visited[i] = 0; // 回溯，取消标记城市 i}}return ans; // 返回当前找到的最小成本
}int main() {// 定义图的邻接矩阵int graph[V][V] = {{0, 10, 15, 20},{10, 0, 35, 25},{15, 35, 0, 30},{20, 25, 30, 0}};int visited[V] = {0}; // 初始化访问数组，所有城市均未访问visited[0] = 1; // 标记起始城市为已访问int ans = INT_MAX; // 初始化最小成本为最大整数值int s = 0; // 起始城市索引// 调用 TSP 递归函数，打印最小成本printf("The minimum cost is %d\n", tsp(graph, s, visited, 1, 0, ans));return 0;
}- 每次递归调用
tsp(graph, i, visited, count + 1, cost + graph[s][i], ans)，都会产生多个新的递归调用。 - 因此，递归树的高度为 n，每一层的节点数都是前一层的 n - count 倍。
- 总的时间复杂度为 O(n!)。
5.10 O(n^n) - 超指数时间复杂度
定义：
超指数时间复杂度 O(n^n) 表示算法的执行时间与输入数据规模 n 的 n 次幂成正比。这意味着如果输入数据规模增加一倍，算法的执行时间会增加一个非常大的数量级。这种复杂度的算法通常涉及多重嵌套循环，每层循环的次数都与输入规模 n 相关。O(n^n) 的算法在处理大规模数据时极其低效，但在某些特定问题中仍然有其应用价值。
常见场景：
超指数时间复杂度 O(n^n) 的算法通常出现在以下场景中：
- 多重嵌套循环：每个循环的迭代次数都与输入规模 n 相关。
- 某些特定的组合优化问题。
- 某些特定的数学问题，如多项式的展开。
示例：
下面是一些典型的超指数时间复杂度 O(n^n) 的算法示例。
示例1：多重嵌套循环
#include <stdio.h>// 打印所有 n 个元素的组合
void printNestedLoops(int n) {int array[n]; // 定义一个大小为 n 的数组// 初始化数组，所有元素初始值为 0for (int i = 0; i < n; i++) {array[i] = 0;}// 无限循环，直到所有组合都被打印while (1) {// 打印当前数组的状态for (int i = 0; i < n; i++) {printf("%d ", array[i]);}printf("\n"); // 换行，表示一个完整的组合// 从最后一个元素开始，尝试增加其值int index = n - 1;while (index >= 0 && array[index] == n - 1) {array[index] = 0; // 如果当前元素已经达到最大值 (n-1)，重置为 0index--; // 移动到前一个元素}// 如果所有元素都已经达到最大值，退出循环if (index < 0) {break;}// 增加当前元素的值array[index]++;}
}int main() {int n = 3; // 定义数组的大小printNestedLoops(n); // 调用函数打印所有组合return 0;
}- 每个循环的迭代次数都与输入规模 n 相关。
- 总的时间复杂度为 O(n^n)。
示例2：多项式的展开
#include <stdio.h>// 展开多项式的函数
void expandPolynomial(int n) {// 定义一个大小为 n 的数组来存储系数int coefficients[n];// 初始化数组，所有系数初始值为 1for (int i = 0; i < n; i++) {coefficients[i] = 1;}// 三层嵌套循环，用于更新系数for (int i = 0; i < n; i++) { // 第一层循环，遍历每个系数for (int j = 0; j < n; j++) { // 第二层循环，遍历每个系数for (int k = 0; k < n; k++) { // 第三层循环，遍历每个系数// 基本操作：更新当前系数coefficients[i] += coefficients[j] * coefficients[k];}}}// 打印更新后的系数for (int i = 0; i < n; i++) {printf("Coefficient %d: %d\n", i, coefficients[i]);}
}int main() {int n = 3; // 定义多项式的阶数expandPolynomial(n); // 调用函数展开多项式return 0;
}- 每个循环的迭代次数都与输入规模 n 相关。
- 总的时间复杂度为 O(n^n)。