javascript - 这个 JavaScript 函数的时间复杂度是线性的还是二次的？

Question

我正试图在 Google 采访视频中了解这个解决方案:https://youtu.be/XKu_SEDAykw?t=1139 .

虽然视频中他们说它是线性的，但我不能 100% 确定整个解决方案是否(以及为什么)是线性的而不是二次的？

因为 find()/includes() 方法嵌套在 for 循环中，这让我假设它有一个运行-O(N * N) 的时间。

但是 find()/includes() 正在搜索一个每次增长 1 步的数组，让我觉得运行时实际上只是 O(N + N)?

这是我在 JavaScript 中的解决方案版本:

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

我的工作:

• 当i = 1时，searchValues.length = 0
• 当i = 2时，searchValues.length = 1
• 当i = 3时，searchValues.length = 2

这不应该意味着 O(N + (N - 1)) 的线性运行时间吗？或者我错过了什么？!

感谢您的帮助!

Answer 1

是的，您的解决方案是二次的，因为正如您提到的 .includes 遍历数组，for 也是如此。然而在采访中，他们谈到了用于查找数组的 unordered_set，这意味着这可以实现为 HashSet，它具有 O(1) 查找/插入时间，使得算法 O(n) (和 O(n²) 最坏，最坏的情况)。 JS 等价物是一个 Set:

 const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));