Javascript Array.reduce（）和Array.find（）的时间复杂度是多少？

Question

我正在尝试返回值索引的数组，这些值加起来等于给定的目标。我正在尝试以最快的方式解决它！

例子：

sumOfTwo([1, 2, 4, 4], 8)   // => [2, 3]
sumOfTwo([1, 2, 3, 9], 8)   // => []

所以首先我尝试了一个简单的蛮力。（时间复杂度：O（n ^ 2））

function sumOfTwo(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) {
        return [i, j];
      }
    }
  }

  return [];
}

然后我想：（时间复杂度：排序为O（n log n）的 + for循环为O（n） ）

function sumOfTwo(arr, target) {
  const sortedArr = arr.sort();
  let idxFromBack = arr.length - 1;

  for (let [idx, val] of sortedArr.entries()) {
    if (val + arr[idxFromBack] > target) {
      idxFromBack--;
    }

    if (val + arr[idxFromBack] === target) {
      return [idx, idxFromBack];
    }
  }

  return [];
}

然后我想到了这种解决方案，我什至不知道时间的复杂性。

function sumOfTwo(arr, target) {
  const complements = [];

  for (let [idx, val] of arr.entries()) {
    if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
      return [complements.find(v => v.value === target - val).index, idx];
    }

    complements.push({index: idx, value: target - val});
  }

  return [];
}

我知道我使用的是for循环，但我不知道内置高阶函数.reduce()和的复杂性.find()。我尝试了几次搜索，但找不到任何东西。

如果有人可以帮助我，那就太好了！如果可能，请包括Big-O表示法。

Repl.it：https://repl.it/@abranhe/sumOfTwo

---

还请包括最后一个解决方案的时间复杂度。

Answer 1

的最小时间复杂度.reduce是O(n)，因为它必须遍历所有元素一次（假设不会引发错误），但是它可以是无限的（因为您可以在回调函数内编写任何代码）。

为您

  // Loop, O(n), n = length of arr:
  for (let [idx, val] of arr.entries()) {
    // .reduce, O(n), n = length of complements:
    if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
      // If test succeeds, .find, O(n), n = length of complements:
      return [complements.find(v => v.value === target - val).index, idx];
    }

    complements.push({index: idx, value: target - val});
  }

在最坏的情况下，时间复杂度是O(n^2)。将reduce在运行O(n)时间，你运行一个reduce在每个条目arr，使得它O(n^2)。

（这.find也是一个O(n)操作，但O(n)+ O(n)= O(n)）

事先对数组进行排序的代码具有降低复杂性的正确方法，但是它也存在一些缺陷。

• 首先，您应该按数字（(a, b) => a - b)）排序；.sort()没有参数的将按字母顺序排列（例如，[1, 11, 2]不希望出现）。

• 其次，仅递减idxFromBack是不够的：例如，sumOfTwo([1, 3, 8, 9, 9], 9)不会看到1和8是匹配项。也许最好的策略是振荡while：从idxFromBack，向后迭代，直到找到匹配项或总和太小，再向前迭代，直到找到匹配项或总和太大。

您也可以通过不使用进行排序，而不使用.sort((a, b) => a - b)，复杂度为O(n log n)，而是使用基数排序或计数排序（二者都具有的复杂度O(n + k)，其中k为常数）来提高此代码的性能。最佳算法将取决于输入的总体形状和方差。

更好的，完全不同的O(n)策略是使用Map或Object。在数组上进行迭代时，将将导致当前项目匹配的值放入对象的键中（该值是当前索引），然后看是否要迭代的当前值存在于对象中。最初的对象：

  // Loop, O(n), n = length of arr:
  for (let [idx, val] of arr.entries()) {
    // .reduce, O(n), n = length of complements:
    if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
      // If test succeeds, .find, O(n), n = length of complements:
      return [complements.find(v => v.value === target - val).index, idx];
    }

    complements.push({index: idx, value: target - val});
  }