时间复杂度：从"这代码怎么这么慢"到"原来如此"

你可能听过这样的对话：

"这个算法是 O(n²)，太慢了。"
"换成 O(n log n) 的排序吧。"

然后你点点头，假装听懂了。

别装了，我知道你没懂。因为当年的小明也是这样。

今天，我们不背公式，不看数学证明，只用最直观的方式，让你真正理解时间复杂度。

一个真实的场景

假设你在一个图书馆找一本书。

场景 A：书架是乱的

你只能一本一本地翻，从第一本看到最后一本。图书馆有 1000 本书，最坏情况下你要翻 1000 次。

场景 B：书架按字母排序

你可以用"二分法"——先看中间的书，如果要找的书在前面就往前找，在后面就往后找。每次排除一半的书。1000 本书，大约翻 10 次就能找到（因为 2¹⁰ = 1024）。

同样是找书，方法不同，效率天差地别。

时间复杂度，就是用来描述这种效率差异的工具。

时间复杂度到底在说什么？

时间复杂度回答的是一个问题：

当数据量增大时，算法的运行时间会以什么样的速度增长？

注意，它不是告诉你"这个算法要运行多少秒"，而是告诉你"数据量翻倍时，时间会怎么变"。

这就像问：

• "你跑 100 米要多少秒？" → 具体时间（取决于你的体能、天气、心情...）
• "你跑的距离翻倍，时间大概翻几倍？" → 增长规律（这是时间复杂度关心的）

几种常见的复杂度，用人话说

O(1) —— 常数时间

特点：不管数据量多大，时间都一样。

比喻：你知道书在第 3 排第 5 本，直接走过去拿。书架上有 100 本还是 100 万本，对你来说没区别。

// 取数组的第一个元素
function getFirst(arr) {
  return arr[0]  // 不管数组多长，都是一步到位
}

现实中的例子：

• 用下标访问数组元素
• 哈希表查找（理想情况）
• 判断一个数是奇数还是偶数

O(n) —— 线性时间

特点：数据量翻倍，时间也翻倍。

比喻：书架是乱的，你要找的书可能在任何位置，只能一本本翻。书越多，翻的时间越长。

// 在数组中找某个值
function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i
  }
  return -1
}

为什么叫"线性"？ 如果画个图，x 轴是数据量 n，y 轴是时间，你会得到一条直线。

现实中的例子：

• 遍历数组/链表
• 找最大值/最小值
• 简单的字符串匹配

O(n²) —— 平方时间

特点：数据量翻倍，时间变成 4 倍。数据量变成 10 倍，时间变成 100 倍。

比喻：你不仅要翻每一本书，还要把每本书和其他所有书比较一遍。这就是"双重循环"的代价。

// 冒泡排序
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {          // 外层循环 n 次
    for (let j = 0; j < arr.length - 1; j++) {    // 内层循环也 n 次
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
}

危险信号：当你写出两层嵌套的 for 循环时，停下来想一想，有没有更好的办法。

现实中的例子：

• 冒泡排序、选择排序
• 简单的两两比较
• 很多暴力解法

O(log n) —— 对数时间

特点：数据量翻倍，时间只增加一点点。

比喻：二分查找。每次排除一半，1000 本书只需要 10 次比较，100 万本书也只需要 20 次。

// 二分查找（数组必须有序）
function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) return mid
    if (arr[mid] < target) left = mid + 1
    else right = mid - 1
  }
  return -1
}

为什么是 log？ 因为你每次把问题规模砍半，砍几次能砍到 1？这就是对数的定义。

现实中的例子：

• 二分查找
• 平衡二叉树的查找
• 很多分治算法的"分"的过程

O(n log n) —— 线性对数时间

特点：比 O(n²) 快很多，是高效排序算法的标配。

比喻：你把书分成很多小堆（log n 次分割），然后每堆都整理一遍（每次整理 n 本）。

// 归并排序的思想
function mergeSort(arr) {
  if (arr.length <= 1) return arr
  
  const mid = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, mid))   // 分
  const right = mergeSort(arr.slice(mid))     // 分
  
  return merge(left, right)                    // 合（这里是 O(n)）
}

现实中的例子：

• 归并排序、快速排序、堆排序
• 很多分治算法

直观对比：当 n = 1000 时

当 n = 1,000,000（一百万）时：

看到 O(n²) 的可怕了吧？这就是为什么面试官总问你"有没有更好的解法"。

如何分析代码的时间复杂度？

记住三条规则：

规则 1：看循环

• 一层循环 → 通常 O(n)
• 两层嵌套循环 → 通常 O(n²)
• 循环次数减半 → 通常 O(log n)

规则 2：只看最高阶

function example(n) {
  // 第一部分：O(n)
  for (let i = 0; i < n; i++) { /* ... */ }
  
  // 第二部分：O(n²)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) { /* ... */ }
  }
}

总复杂度是 O(n + n²) = O(n²)。因为当 n 很大时，n² 远大于 n，n 可以忽略。

规则 3：忽略常数

O(2n) = O(n)，O(100n²) = O(n²)

常数不影响增长趋势，所以忽略它。这也是为什么时间复杂度不能告诉你"具体多少秒"。

几个容易踩的坑

坑 1：看起来是 O(n)，实际是 O(n²)

// 你以为这是 O(n)？
for (let i = 0; i < arr.length; i++) {
  arr.splice(i, 1)  // splice 本身是 O(n) 的！
}
// 实际是 O(n²)

坑 2：递归的复杂度不直观

// 斐波那契数列
function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

看起来简洁优雅，实际是 O(2ⁿ)，慢到离谱。n = 40 就能让你的电脑卡住。

坑 3：API 的隐藏复杂度

// indexOf 是 O(n)
if (arr.indexOf(x) !== -1) { /* ... */ }

// includes 也是 O(n)
if (arr.includes(x)) { /* ... */ }

// 想要 O(1)？用 Set
const set = new Set(arr)
if (set.has(x)) { /* ... */ }

实战：优化一道经典题

题目：找出数组中两个数，使它们的和等于目标值。

暴力解法 O(n²)

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

两层循环，每个数都要和其他数比较一遍。

优化解法 O(n)

function twoSum(nums, target) {
  const map = new Map()  // 用哈希表记录"见过的数"
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (map.has(complement)) {
      return [map.get(complement), i]
    }
    map.set(nums[i], i)
  }
}

只需要遍历一次，每次查找都是 O(1)。

思路转变：从"两两比较"变成"查找差值"，用空间换时间。

总结

时间复杂度不是用来背的，而是用来分析的。

当你能看着代码，自然而然地判断出它是 O(n) 还是 O(n²)，能意识到"这里有两层循环，可能有性能问题"，你就真正理解时间复杂度了。

记住：

• O(1)：直接存取，最快
• O(log n)：每次砍半，很快
• O(n)：遍历一遍，正常
• O(n log n)：高效排序的标配
• O(n²)：双重循环，要警惕
• O(2ⁿ)：指数爆炸，别用

下一篇，我们聊聊空间复杂度——代码不仅要跑得快，还要省内存。

「程序员的两大难题：缓存失效和命名。」
「还有第三个：分析递归的时间复杂度。」
—— 小明