javascript - 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 loop 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 符号。

复制 : 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) 排序 not 来提高此代码的性能。 ，其复杂度为 O(n log n) ，但使用基数排序或计数排序(两者的复杂度均为 O(n + k) ，其中 k 是一个常数)。最佳算法将取决于输入的一般形状和方差。

一个更好的，完全不同的 O(n)策略是使用 map 或对象。遍历数组时，将与当前项匹配的值放入对象的键中(其中值是当前索引)，然后查看被迭代的当前值是否存在于最初的对象:

const sumOfTwo = (arr, target) => {
  const obj = {};
  for (const [i, num] of arr.entries()) {
    if (obj.hasOwnProperty(String(num))) {
      return [obj[num], i];
    }
    const matchForThis = target - num;
    obj[matchForThis] = i;
  }
  return [];
};

console.log(
  sumOfTwo([1, 2, 4, 4], 8),   // => [2, 3]
  sumOfTwo([1, 2, 8, 9], 9),  // 1 + 8 = 9; [0, 2]
  sumOfTwo([1, 2, 3, 9], 8)   // => []
);