从 O(N^2) 到 O(N) 的迁移：O(1) 的力量

Source: Dev.to

从 O(N²) 迁移到 O(N)：O(1) 的力量

驯服增长：如何使用 Elixir 数据结构将 O(N²) 转换为 O(N)

在上一篇文章中我们看到，O(N²) 复杂度来源于一个嵌套循环，对每个元素 (N) 都遍历整个列表 (N)。当算法需要执行 N × N 次操作时，它无法扩展。

将 O(N²) 迁移到 O(N)（线性） 的关键是确保每个输入元素只被访问 常数 次。

目标： 将“在列表中查找元素”的操作从 O(N) 转为 O(1)。

O(1) 的秘密：映射和集合

要实现常数时间的查找或插入 O(1)，我们不能使用 Elixir 的普通列表。需要一种能够瞬间回答“这个项目已经存在吗？”而不进行迭代的结构。

在 Elixir 中，合适的结构是 MapSet（集合）或 Map（映射）。它们使用 哈希 将键转换为可预测的内存地址。

Elixir 中的 O(N) 解决方案：Reduce 与 MapSet

为了解决重复元素问题并在 O(N) 时间内完成，我们使用函数式的 累积 技术。使用 Enum.reduce_while 只遍历列表一次，并用 MapSet 作为累加器来记录已经出现的元素。

Elixir 代码：快速去重

defmodule OptimizedDuplicationCheck do
  def contains_duplicate_fast(list) do
    # 1. 累加器：从空的 MapSet 开始。
    initial_set = MapSet.new()

    list
    |> Enum.reduce_while(initial_set, fn element, seen_elements ->
      # O(1) 检查
      if MapSet.member?(seen_elements, element) do
        # 🟢 最佳情况 (O(1))：找到后停止。
        {:halt, true}
      else
        # O(1) 更新：加入元素并继续。
        new_set = MapSet.put(seen_elements, element)
        {:cont, new_set}
      end
    end)
    |> (&(&1 == true)).()
  end
end

📈 复杂度分析

通过将内部的 O(N) 查找替换为 O(1)，我们消除了额外的 N 因子，确保算法线性扩展。使用 Enum.reduce_while 还能在 最佳情况 下优化：如果重复元素是第一个出现的，执行时间为 O(1)。

下一站：O(log N)

如果 O(N) 已经很优秀，想象一下一个算法只需要大约 24 步就能在一千万个元素的列表中找到目标。

在下一篇文章中，我们将探讨 二分查找 及其 O(log N) 复杂度，这是真正的“搜索圣杯”。我们会说明列表必须是有序的原因，以及在 Elixir 中使用哪种数据结构来正确实现它。