时间复杂度总结

基本概念

• 时间复杂度：描述算法运行时间随输入规模增长的趋势。
• 渐进复杂度：关注算法在大规模输入下的性能，忽略低阶项和常数因子。

---

大 O 记号

• 性质：
  1. 对于任一常数 c > 0，有 O(f(n)) = O(c * f(n))。
  2. 对于任意常数 a > b > 0，有 O(n^a + n^b) = O(n^a)。

---

时间复杂度实例

1. 冒泡排序

• 时间复杂度：O(n²)
• 分析：
  • 外层循环最多执行 n-1 次。
  • 内层循环每次最多执行 n-1 次比较和交换。
  • 总操作次数不超过 2(n-1)²，简化为 O(n²)。

2. 常数时间复杂度 O(1)

• 问题：从数组中找一个既不是最大值也不是最小值的数。
• 算法：
  • 取前三个数，排序后返回中间的数。
• 时间复杂度：O(1)，因为操作次数固定。

3. 对数时间复杂度 O(log n)

• 问题：统计一个非负整数二进制表示中 1 的个数。
• 算法：
  • 每次右移一位，检查最低位是否为 1。
• 时间复杂度：O(log n)，因为循环次数为 1 + log₂n。

4. 线性时间复杂度 O(n)

• 问题：计算数组中所有元素的和。
• 算法：
  • 遍历数组，累加每个元素。
• 时间复杂度：O(n)，因为需要遍历 n 个元素。

5. 多项式时间复杂度 O(polynomial(n))

• 问题：冒泡排序、遍历数组等。
• 特点：
  • 运行时间可以表示为 n^k（k 为常数）。
  • 即使 k 很大（如 n¹⁰⁰），仍属于多项式时间。
  • 对比：多项式时间比指数时间（如 2ⁿ）高效得多。

6. 指数时间复杂度 O(2ⁿ)

• 问题：计算 2ⁿ（禁止使用移位运算）。
• 算法：
  • 循环 n 次，每次乘以 2。
• 时间复杂度：O(2ⁿ)，因为输入规模为 n 的二进制位数 r，n ≈ 2ʳ。
• 特点：指数时间算法在大规模输入下不可行。

---

常见时间复杂度对比

复杂度	描述	示例算法
O(1)	常数时间	取数组中间值
O(log n)	对数时间	二分查找
O(n)	线性时间	遍历数组
O(n log n)	线性对数时间	快速排序
O(n²)	平方时间	冒泡排序
O(2ⁿ)	指数时间	穷举搜索

---

总结

• 大 O 记号：用于描述算法时间复杂度的上限。
• 渐进分析：关注算法在大规模输入下的性能。
• 常见复杂度：从 O(1) 到 O(2ⁿ)，性能差异巨大。
• 实际应用：选择算法时，优先考虑低时间复杂度的算法。