如何降低嵌套循环的时间复杂度

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

在这篇文章中，我将演示一种理解、分析和降低算法时间复杂度的方法，特别是对于嵌套循环而言。

这些示例将使用 Ruby，但可以翻译成任何编程语言。

问题

在参与各种项目的过程中，经常会遇到类似下面的代码片段，即“嵌套循环”，也就是一个循环嵌套在另一个循环之下：

for group in groups
  for user in users
    # do something with the group and user
  end
end

分析以上代码，并假设我们有 100 个组和 100 个用户：

• 对于每个用户组（重复 100 次），我们遍历所有用户（重复 100 次），这导致了100 * 100 = 10000多次迭代。
• 每次迭代都会消耗 CPU 资源，因此迭代次数越多，算法性能就越差。
• 如果列表随着时间推移而增长，这种算法可能会面临严重的性能问题。

在大 O 表示法分析中，该算法的时间复杂度可能为 O(n) squared，或者 O(n) O(n²)，因为 O(n) = n 100 * 100 = 100²。

我们能否改进它？

为了降低O(n²) 平方运算的时间复杂度，我们可以努力将其降低到O(n) 线性或O(log(n))在大多数情况下降低，这将使我们的算法运行得更快。

有些问题类别无法以最优方式进行简化，但我们的例子完全可以进行简化。

我们来看看如何改进它。

减少迭代次数

请记住，此时我们的算法将执行 10000 次迭代100²：

groups = [1, 2, ....100]
users  = [1, 2, ....100]

for group in groups
  for user in users
...

一个简单的解决方法是删除嵌套循环：

for group in groups
  # do something with group and user
  # now we are missing the user, but we need to fetch the user information from another data structure
end

• 该算法只需执行 100 次迭代，速度快得多。
• 这意味着它是线性的，或者O(n)

但是我们的算法不再有效，因为我们必须从分组循环内部获取用户信息。

理想情况下，对于每个组，无论用户列表有多大，我们都希望在恒定时间内获取用户信息。

哈希表万岁！

在计算机科学中，数据结构是一个非常重要的研究和理解课题。为了在常数时间内获取用户信息O(1)，我们可以使用哈希表。

Ruby 提供了这种现成的数据结构，称为哈希（Hash）。

构建哈希

如何在分组循环中构建包含所有必要信息的哈希表？我们需要遍历所有用户，并使用所需信息构建哈希表。

这种技术广泛用于创建类似“索引”的结构，通过键可以在恒定时间内访问信息O(1)。例如：

users_idx = {}

for user in users
  users_idx[user[:id]] = ...
end

然后，无论何时我们需要获取用户信息，我们都可以通过访问users_idx相应的密钥来实现。

综合起来

为了继续挑战减少算法迭代次数，我们需要执行以下步骤：

• 构建包含后续要访问信息的“索引”。
• 遍历循环并从先前创建的“索引”中获取附加信息

users_idx = {}

for user in users
  users_idx[user[:group_id]] = ...
end

for group in groups
  user_information = users_idx[group[:id]]
  # do something with group AND user information
end

等等，两个环？那不还是平方数 O(n²)吗？我们来比较一下。

第一种方案执行100 * 100 = 10.000若干次迭代，而第二种方案执行100 次迭代来构建索引，再加上 100 次迭代来遍历组100 + 100 = 200。简而言之：

nested loop:    100 * 100 = 10.000
index AND loop: 100 + 100 = 200

它仍然比初始值低得多10.000。我们可以写更多循环，三遍、四遍、五遍。这都没关系，它仍然是线性的 O(n)，因为就时间复杂度而言，O(n) = O(2n) = O(3n)等等……

比较两种解决方案

在这个 Gist中，我创建了虚拟数据和基准测试，以便比较这两种解决方案。

对于较小的列表，实际差别不大。但对于较大的列表，改进效果就很明显了。

以下是使用该索引的速度提升效果的测试结果：

10 groups   | 10 users   => 2x   faster
100 groups  | 100 users  => 3x   faster
100 groups  | 100 users  => 31x  faster
1000 groups | 1000 users => 70x  faster
5000 groups | 5000 users => 510x faster

结论

本文演示了如何分析、理解和降低算法的时间复杂度，特别是当我们遇到嵌套循环的情况时。

大多数情况下，与其尝试寻找其他复杂的解决方案（例如缓存甚至更复杂的解决方案），不如理解算法分析，这可以帮助我们编写出更好、更便宜的解决方案。

此外，如果循环使用 ORM 执行数据库查询，则只需使用SQL JOIN即可改进许多嵌套循环。