07 算法评价标准：时间复杂度（大 O 渐进表示法、常见时间复杂度及案例分析）

直接观察法：通过仔细分析算法中的每个步骤，确定每个步骤的执行次数，并将这些次数相加，得到总的执行次数。这种方法适用于结构较为简单、步骤清晰的算法。
举例验证法：通过具体的例子，手动计算算法在不同规模下的执行次数，从而验证和确认时间复杂度。这种方法适用于复杂度较高的算法，通过具体的数据验证理论分析的正确性。

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，那么时间复杂度为：

$T(n) = O(n^{2})$

总结

通过直接观察法，我们确定了 printf 语句的执行次数为 m * n。因此，该代码的时间复杂度为 O(m×n)。如果 m 和 n 都是同一个问题规模 n，则时间复杂度为 O(n^2)。

4 常见的时间复杂度

在时间复杂度分析中，通常将时间复杂度分为多项式时间复杂度和指数时间复杂度。具体来说：

4.1 多项式时间复杂度

包括形如 $O(n^{k})$ 的时间复杂度，其中 k 是一个常数。常见的多项式时间复杂度有 $O(1)$ 、 $O(\log n)$ 、 $O(n)$ 、 $O(n \log n)$ 、 $O(n^2)$ 、 $O(n^3)$ 和 $O(n^k)$ 等。

4.2 指数时间复杂度

包括形如 $O(a^n)$ 的时间复杂度，其中 a > 1。常见的指数时间复杂度有 $O(2^n)$ 、 $O(3^n)$ 、 $O(n!)$ 、 $O(n^n)$ 等。当 k > 3 时，多项式时间复杂度 $O(n^k)$ 也可以被视为接近指数时间复杂度，因为它们的增长速度非常快。

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) 的算法通常出现在以下场景中：

检查一个数是否为质数。
查找数组中的某个特定模式。
一些特定的数学问题，如求解平方根。

示例

下面是一些典型的平方根时间复杂度 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 的数组

    // 初始化数组，所有元素初始值为 0
    for (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)，重置为 0
            index--;  // 移动到前一个元素
        }

        // 如果所有元素都已经达到最大值，退出循环
        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];

    // 初始化数组，所有系数初始值为 1
    for (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)。

乐奇 Rokid 开放社区

更多推荐

Meta Muse 爆火：12 天下载量反超 ChatGPT，个人 AI 智能体完整使用指南

乐奇 Rokid 开放社区

AI 日报（2026年9月24日）

2026年9月24日，AI技术与应用呈现多元化演进态势。硬件与端侧方面，Meta在Connect大会发布首款轻量化VR眼镜与无摄像头智能眼镜，全面接入Muse智能体；谷歌上线Gemini 3.8 Flash TTS可定制语音模型，并在DeepMind推动私密计算与服务端内存融合。行业与前沿科研领域，Anthropic湿实验实验室利用Claude发现CRISPR样新型酶系统，并推出一站式Claude