《时间复杂度（C语言）》

前言

写程序时，我们最关心的往往是“能不能跑起来”“结果对不对”。但真正优秀的程序员会更进一步，追求写出高效、优雅、性能优秀的代码。

在大数据量、频繁调用、实时要求等场景下，效率的差别往往不是毫秒级，而是“几秒 VS 几小时”的级别。
这时候，时间复杂度就成为判断算法优劣的关键指标。

时间复杂度告诉我们：随着输入数据规模增加，程序执行时间如何变化。

本篇博客将围绕 C 语言中的时间复杂度展开，深入剖析其概念、表示法、常见形式及如何估算，并通过代码举例帮助你掌握这个关键技能。

---

一、时间复杂度的概念

**时间复杂度（Time Complexity）**描述的是算法运行时间与输入数据规模（n）之间的关系。（说白了就是执行次数）

为什么要有时间复杂度？

程序运行的时间可能会受到以下因素影响：

• 电脑配置：CPU快慢
• 编译器优化与否
• 操作系统调度
• 编程语言的效率

这些因素都不是算法本身的问题。为了客观评价算法的优劣，我们引入了时间复杂度，它：

✅ 只关注算法本身的运行步骤数量变化趋势
✅ 忽略常数、低阶项、硬件环境等非本质因素
（总结就是一个程序最多循环多少次）

举个生活中的例子：

• 一个电梯：一次只能运一人（算法A），每人都从1楼坐到10楼；（如果n个人就要循环n次）
• 一个扶梯：可以同时站很多人，一起移动（算法B）。（如果n个人也是一次）

虽然电梯更高级，但当人变多时，扶梯可能更快。这就体现了随着输入数据增加，效率谁更优的问题。

---

二、大O的渐进表示法（Big O）

我们使用“大O符号”来描述时间复杂度，用来表示最坏情况下，算法执行步骤的数量级。

常见的大O表示法如下：

时间复杂度	说明	举例	备注
O(1)	常数时间	单个变量赋值	最理想，输入多少都一个步骤
O(log n)	对数时间	二分查找	每次输入规模减半，增长很慢
O(n)	线性时间	单层循环	输入翻倍，执行次数也翻倍
O(n log n)	线性对数时间	归并排序	高效排序中常见
O(n²)	平方时间	冒泡排序	两层循环，性能急剧下降
O(2ⁿ)	指数时间	全排列、子集枚举	输入稍多就无法承受
O(n!)	阶乘时间	穷举全部排列	极度低效，仅适合非常小数据规模

注：O(n^2) 之后的效率太低了有理论意义，没有实际意义

几个注意点：

• 只保留最高阶项，忽略低阶项和常数系数

  例如：O(3n² + 2n + 5) ➡️ 简化为 O(n²)

• 只考虑最坏情况（worst-case），除非特别说明

  比如查找失败时执行最多步骤

---

三、常见时间复杂度分析

🔹 O(1) 常数时间（理想型）

不依赖输入数据大小，永远只执行一次或固定次数的操作。

int getFirstElement(int arr[]) {return arr[0];  // 不管数组多大，操作只有一次
}

哪怕数组长度是 100 万，也只取了第一个数。

---

🔹 O(n) 线性时间

操作次数与输入数据成正比。

for(int i = 0; i < n; i++) {printf("%d\n", i);
}

执行 n 次，输入增长一倍，循环次数也翻倍。

---

🔹 O(n²) 平方时间

双重循环的经典例子，每个元素和其它所有元素都比较一次。

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

总共执行 n × n 次操作。当 n = 1000 时，总共执行 1,000,000 次！

---

🔹 O(log n) 对数时间

输入每次减半，典型例子是二分查找。

int binarySearch(int arr[], int n, int target) {int left = 0, right = n - 1;while(left <= right) {int mid = (left + right) / 2; //为了防止溢出这里也可以写成 int mid = left + (right - left) >> 1;if(arr[mid] == target) return mid;else if(arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}

每轮都将问题规模减半，效率非常高。

---

🔹 O(n log n) 混合型复杂度

排序算法中最理想的复杂度之一，如归并排序和快速排序。

归并排序伪代码结构如下：

void mergeSort(int arr[], int left, int right) {if(left >= right) return;int mid = (left + right) / 2;mergeSort(arr, left, mid);       // T(n/2)mergeSort(arr, mid + 1, right);  // T(n/2)merge(arr, left, mid, right);    // 合并操作 O(n)
}

总共执行 log n 层递归，每层花费 n 时间 ➜ O(n log n)。

---

🔹 O(2ⁿ) 指数时间

递归求解斐波那契数列是最常见的例子：

int fib(int n) {if(n <= 1) return n;return fib(n - 1) + fib(n - 2);
}

每次都递归两次，形成指数级增长，非常低效。n = 50 需要上亿次递归。

---

四、时间复杂度估算方法（技巧总结）

常数复杂度：赋值、简单运算、单次函数调用

循环结构：重点在循环次数与n的关系

• 单层 for：O(n)
• 嵌套 for：O(n²) 或更高
• 减半循环：O(log n)

递归结构：要结合 递归树 或 主定理（Master Theorem） 估算

---

总结

时间复杂度是算法分析的核心指标，帮助我们用数学的视角衡量代码效率。

时间复杂度	增长速度	代表算法/场景
O(1)	最快	数组下标访问
O(log n)	很快	二分查找
O(n)	线性	遍历数组
O(n log n)	较快	快排、归并排序
O(n²)	慢	冒泡、选择排序
O(2ⁿ)	很慢	穷举子集、回溯 、第n个斐波那契数
O(n!)	极慢	全排列问题