🌟一、小引：什么是“算法效率”？

算法效率，也叫 时间复杂度（Time Complexity）。

它不关心你的电脑配置到底有多高，运行速度到底有多快，也不关心你的代码运行具体用了多少秒。
它只关心 当数据量变大时，程序的执行步骤增加得有多快。

换言之：

算法效率衡量的是：数据规模变大时，算法变慢的速度有多快。

🌟二、为什么要用 O(…) 来描述？

为什么要用O(…)来描述算法效率？
因为实际运行的时间会受到以下影响

  • 电脑性能的不同
  • 程序语言的差异
  • 编译器优化程度

这些都会影响“秒数”，所以我们不去看秒数，而是看：

算法执行步骤的数量（操作次数）随着输入规模 n 的增长趋势。

如何理解这句话？
我们可以用O(…)来描述这个趋势，如：

  • O(1)——常数时间
  • O(n)——线性增长
  • O(n²)——平方增长
  • O(log n)——对数增长

🌟三、怎么推导 O(…)？

现在我将以Python为程序语言，例举几个简单的例子，去推导“数操作次数”
⭐① 推导 O(n)：一次循环

1
2
for i in range(n):
    print(i)

执行步骤分析：

  • 循环执行了 n 次
  • 每次执行一次，循环体就会 print 一次

📚结论：操作次数 ≈ n → O(n)

⭐ ② 推导 O(n²)：双层循环

1
2
3
for i in range(n):
    for j in range(n):
        print(i, j)

执行步骤分析：

  • 外层循环 n 次
  • 内层循环每次运行 n 次
  • 总次数 = n x n = n²

📚结论：操作次数 ≈ n² → O(n²)
Tips：为什么冒泡循环效率很低，就是因为它有双层循环

⭐ ③ 推导 O(log n)：每次把问题砍半
以下为经典算法——二分查找

1
2
3
4
5
6
7
while left <= right:
    mid = (left + right) // 2

    if target < nums[mid]:
        right = mid - 1
    else:
        left = mid + 1

每次循环做了什么？

  • 把范围砍掉了一半

例如 n = 16

第 1 次：范围 16
第 2 次：范围 8
第 3 次：范围 4
第 4 次：范围 2
第 5 次：范围 1

砍半直到 1，大概砍了几次？
答案是：log₂(n) 次。

📚结论：操作次数 ≈ O(log n) — 对数时间
Tips：增长非常慢，比你想象的快得多。

⭐ ④ 推导 O(1)：常数时间

1
2
3
lst[10]
a = 7 * 123
return x

无论 n 是多少，这些操作都只执行 一次。

📚结论：操作次数 ≈ O(1) = 不随输入大小变化

⭐ ⑤ 常见复杂度由低到高

| 复杂度	     | 常见例子       		|
| ---------- | ------------------------ |
| O(1)       | 取数组元素		|
| O(log n)   | 二分查找			|
| O(n)       | 遍历数组			|
| O(n log n) | 快速排序、归并排序		|
| O(n²)      | 冒泡、选择、插入排序	|
| O(2ⁿ)      | 递归回溯（如八皇后） 	|
| O(n!)      | 全排列问题		|

🌟四、最关键的一句总结

推导时间复杂度，就是数最深的循环嵌套层数。
每层循环 n 次 → 乘一个 n。
若每次把问题砍一半 → log n。

知道了原理之后，我们就几乎可以推导所有算法的复杂度。

🌟五、尝试推导，多加练习

1
2
3
for i in range(n):
    for j in range(100):
        print(i, j)
  • 外层循环：i 从 0 到 n-1 → 执行 n 次
  • 内层循环：j 从 0 到 99 → 固定 100 次，与 n 无关
  • 总执行次数 = n × 100 → O(n)

✅ 答案：O(n)

注意：常数 100 可以忽略，所以复杂度还是 O(n)

1
2
while n > 1:
    n = n // 3
  • 每次循环把 n 缩小为 1/3
  • 循环次数 ≈ 对数 log₃(n)
  • 常用 Big O 表示法忽略底数 → O(log n)

✅ 答案：O(log n)

这是典型的“每次把问题砍半或砍几分之一”的对数复杂度。

1
2
3
for i in range(n):
    for j in range(i):
        print(i, j)
  • 外层循环 i 从 0 到 n-1 → n 次
  • 内层循环 j 从 0 到 i-1 → 执行 i 次
  • 总执行次数 = 0 + 1 + 2 + … + (n-1) = n(n-1)/2 → O(n²)

✅ 答案：O(n²)

注意：这是典型的“逐渐增长的内层循环”，复杂度仍然是平方级别。

🌟六、可视化图像


图片由chatGPT生成Python代码matplotlib库可视化编译结果

🔹 表格说明

  • X轴：Input size 为输入规模
  • Y轴：Number of operations / Times 为操作次数 / 时间
  • 标题：Algorithm complexity 为算法复杂度表格

🔹 图形说明

  1. O(1) — 水平线，完全不随 n 变化
  2. O(log n) — 最平缓，几乎贴近横轴
  3. O(n) — 线性增长
  4. O(n log n) — 稍陡，比 O(n) 快些但远小于 O(n²)
  5. O(n²) — 二次方增长，快速上升
  6. O(2^n) — 指数增长，非常陡峭
  7. O(n!) — 阶乘增长，几乎垂直，非常快爆炸

注意：我把 y 轴设为 对数刻度，这样指数和阶乘曲线不会直接爆掉，可以清楚看出差异。