C语言时间复杂度详解（从零开始掌握算法效率分析）

常见的时间复杂度类型

以下是几种最常见的时间复杂度，按效率从高到低排列：

• O(1)：常数时间。无论输入多大，执行时间不变。例如访问数组元素 a[5]。
• O(log n)：对数时间。常见于二分查找。
• O(n)：线性时间。循环遍历一次数组。
• O(n log n)：常见于高效排序算法，如快速排序、归并排序。
• O(n²)：平方时间。常见于双重嵌套循环。
• O(2ⁿ) 或 O(n!)：指数或阶乘时间，通常不可接受，应尽量避免。

如何计算 C 语言代码的时间复杂度？

我们通过几个例子来学习 C语言性能优化 中的关键技巧。

例1：O(1) 常数时间

int getFirst(int arr[], int n) {    return arr[0];  // 无论 n 多大，都只执行一次}

这段代码的时间复杂度是 O(1)。

例2：O(n) 线性时间

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

循环执行了 n 次，所以时间复杂度是 O(n)。

例3：O(n²) 平方时间

void printPairs(int arr[], int n) {    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            printf("(%d, %d)\n", arr[i], arr[j]);        }    }}

外层循环 n 次，内层也 n 次，总共执行 n × n = n² 次，时间复杂度为 O(n²)。

忽略常数和低阶项

在 算法效率分析 中，我们只关注最高阶项，并忽略常数系数。例如：

• 3n + 5 → O(n)
• 2n² + 100n + 1000 → O(n²)
• log n + 10 → O(log n)

这是因为当 n 非常大时，高阶项主导了运行时间，低阶项和常数几乎可以忽略。

小贴士：如何优化时间复杂度？

1. 避免不必要的嵌套循环。
2. 使用哈希表（如 C 中的数组模拟）将查找从 O(n) 降到 O(1)。
3. 对有序数据使用二分查找（O(log n)）而非线性查找（O(n)）。
4. 选择更高效的排序算法（如 qsort() 内部通常是 O(n log n)）。

总结

掌握 C语言时间复杂度 是成为高效程序员的关键一步。通过本 时间复杂度计算教程，你应该已经能够识别常见代码的时间复杂度，并初步具备 C语言性能优化 和 算法效率分析 的能力。记住：写代码不仅要“能跑”，更要“跑得快”！

继续练习，多分析，你也能写出高性能的 C 程序！