javascript - 避免重复计算优化嵌套for循环的时间复杂度

Question

今天我用下面的代码在 HackerRank 上做了一个简单的挑战，它 100% 可以接受并且有效，但我想知道是否有一种方法可以通过消除重复计算来进一步减少所需的循环。

让我直观地向您展示正在发生的事情，当我完成时，我的代码示例将会非常深入!

代码获取数字数组中的第一个数字并将其添加到每个后续数字并检查它是否可以被 k = 3 整除。

在一个包含 6 个数字的数组中，这相当于 15 个循环，这将是 O(n²)，这意味着我的循环将按输入量呈指数增长。 7 个数字将是 21 个循环。

P.S.，您可能认为 6 应该是 21 个循环，而 7 应该是 28 个循环，但请记住，我总是取当前数字并将其添加到下一个数字，最后一个数字除外。

视觉分解

输入:[1, 3, 2, 6, 1, 2]

• 1+3、1+2、1+6、1+1、1+2
• 3+2、3+6、3+1、3+2
• 2+6、2+1、2+2
• 6+1, 6+2
• 1+2

说明

如果您查看我用粗体 显示的数字，您会发现它们是重复计算。 斜体 数字是可被k = 3 整除的数字。现在我们开始讨论我的问题了。我怎样才能消除这个重复的数学，在这个特定的例子中，这会使我的循环从 15 减少到 8。如果所有数字都不同，该算法仍然会有 O(n²) 的更坏情况，但这仍然是一种优化。

代码演示

function divisibleSumPairs(k, a) {
  let pairs = 0;
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if ((a[i] + a[j])/k % 1 === 0) pairs++;
    }
  }
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

Answer 1

我花了一段时间思考如何预处理数字数组以防止重复计算，然后我离开了一会儿，然后头脑清醒并喝了一杯冷水回到问题上。

然后我想“如果我改为预处理除数会怎么样”？

这种方法的缺点是它创建了一个与除数大小相等的数组，但它在 O(n) 时间复杂度(螺丝空间复杂度，lol)中做到了

对于这个特定的例子，我们有 3 个用于除数的循环，6 个用于计算的循环，总共 9 个循环，这比原始解决方案节省了 6 个循环，并且消除了 O( n²).

这导致我的函数的总体时间复杂度为 O(n)

function divisibleSumPairs(k, a) {
  const mod = new Array(k).fill(0);
  let pairs = 0;
  
  for (let i = 0; i < a.length; i++) {
      const position = a[i] % k;
      
      pairs += mod[(k - position) % k];
      mod[position]++;
  }
  
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

性能测试

我通过性能测试对我的代码进行了多次迭代，我惊讶地发现一个简单的 for 循环与 forEach 和 reduce< 相比要好得多.

1. for^2:原代码
2. for: 这篇文章中的代码
3. forEach:这篇文章，使用forEach代替
4. reduce:这篇文章，使用reduce代替

https://jsperf.com/for-2-vs-for-vs-foreach-vs-reduce/1