什么是 Big O？以及 O(N^2) 这个恶棍

Source: Dev.to

使用 Elixir 的算法复杂度：理解 O(N²) 以及为什么你的列表如此慢？

如果你使用 Elixir 或其他语言编程，已经看到代码在 10 条数据时运行完美，却在 10 000 条时卡死，那你已经碰到了 算法复杂度。

大 O 符号 O(...) 并不衡量秒数，而是衡量执行时间相对于输入规模 (N) 的 增长规律。它是编写可扩展代码最重要的工具。

🟢 O(1)：常数复杂度

执行时间始终相同，无论你的列表是 10 条还是 100 万条。

Elixir 示例 – prepend（在头部插入）：

# O(1)：创建一个指向旧列表的新节点。
new_list = [novo_item | lista_antiga]

# O(1)：访问头部
[head | _] = new_list

这是函数式代码中最常见的操作，也是 Elixir 列表创建如此快速的原因。

🟡 O(N)：线性复杂度

执行时间随输入规模成比例增长。如果列表大小翻倍，时间也翻倍。

Elixir 示例 – 遍历列表（map、reduce）或在末尾追加：

# O(N)：遍历列表的每个元素
sum = Enum.reduce(list, 0, &(&1 + &2))

# O(N)：在末尾追加时，系统必须遍历整个列表。
list = list ++ [item_no_fim]

🔥 O(N²)：平方恶魔

O(N²) 复杂度是可扩展性的最大敌人。如果输入 (N) 翻倍，执行时间会 四倍增长（2² = 4）。

原因： 嵌套循环，内部循环的迭代次数依赖于整体输入规模。

实际案例 – 朴素的重复元素检查

def check_duplicate_slow(list) do
  # Enum.any? 迭代列表：N 次
  Enum.any?(list, fn current_element ->
    # 对每个元素，再次遍历整个列表：N 次
    list
    |> Enum.filter(&(&1 == current_element))
    |> Enum.count() > 1
  end)
end

分析

• 外层 Enum.any? 执行 N 次。
• 对每次执行，内部 Enum.filter 再遍历整个列表（N 个元素）。
• 操作总数约为 N × N = O(N²)。

如果 N = 10 000，算法将进行 100 000 000 次操作（即一亿次）——增长速度难以承受！

下一站：跃迁到 O(N)

O(N²) 的解法写起来很容易，却会毁掉性能。我们可以通过只遍历每个元素一次，并使用 O(1) 访问 的数据结构，将重复元素问题转化为快速的 O(N) 算法。下一篇文章我们将探讨这种技术。

从 O(N²) 迁移到 O(N)!