给定嵌套循环的运行时是什么？

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如果您有兴趣，请指向问题的链接。

所以毕竟我的问题是-这个代码是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