给定嵌套循环的运行时间是多少？

Question

我正在努力提高编码水平，因此在每次 hackerrank 挑战之后，我都会查看其他人的工作情况，以便将我的代码与他们的进行比较。一个有趣的解决方案，显然有效，是这样的：

function getMoneySpent (keyboards, drives, b) {
  return keyboards.reduce (
    (acc, curr) =>
      Math.max (acc, ...drives.map (usb => usb + curr).filter (ku => b >= ku)),
    -1
  );
}

console.log (getMoneySpent ([1, 20, 40], [5, 60, 7], 50));

它基本上找到两个数字（每个数组中的一个）的最大总和 <= 一个数字（在本例中为 50）。然而，当我剖析代码时，似乎有两个循环，一个 .reduce，一个 .map 和一个 .filter。这会使此代码成为 O(n)^2 吗？我很确定它不会通过测试用例，因为数组可以是 1000 长，而数字 (50) 可以是 10^6。 Here's link 如果你感兴趣的话。

毕竟我的问题是 - 这个代码是 O(n)^2 吗？

Answer 1

据我所知，实际上是3•O(n)^2

推理见下：

function getMoneySpent (keyboards, drives, b) {
                // O(n)
  return keyboards.reduce ( 
    (acc, curr) =>
        // O(n) +              O(n) +                  O(n)
      Math.max (acc, ...drives.map (usb => usb + curr).filter (ku => b >= ku)),
    -1
  );
}

O(n) * (O(n) + O(n) + O(n))
O(n) * 3•O(n)
3•O(n)^2

Math.max source code