Javascript Array.reduce()和Array.find()的时间复杂度是多少?

问题描述

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

I am trying to return an array of indexes of values that add up to a given target. I am trying to solve it the fastest way I can!

示例:

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

所以首先我尝试了一个简单的蛮力. (时间复杂度: O(n ^ 2))

So first I tried a simple brute-force. (Time complexity: 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)排序 O(n log n) +)

Then I tried: (Time complexity: sorting 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 [];
}

然后我带来了这种解决方案，我什至都不知道时间的复杂性.

Then I came with this solution that I don't even know the time complexity.

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()的复杂性.我尝试了几次搜索，但找不到任何东西.

I know that I am using a for-loop but I don't know the complexity of the build-in high order functions .reduce() and .find(). I tried a couple of searches but I couldn't find anything.

如果有人可以帮助我，那就太好了！请尽可能添加Big-O表示法.

If anyone can help me would be great! Please include Big-O notation if possible.

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

请同时提供上一个解决方案的时间复杂度.

Please also include the time complexity of the last solution.

推荐答案

.reduce的最小时间复杂度是O(n)，因为它必须对所有元素进行一次迭代(假设错误不是't throw)，但是它 是不受限制的(因为您可以在回调函数中编写所需的任何代码).

The minimum time complexity of .reduce is O(n), because it must iterate through all elements once (assuming an error isn't thrown), but it can be unbounded (since you can write any code you want inside the callback).

为您

  // 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)时间运行，并且您为arr中的每个条目运行reduce，将其设置为O(n^2).

the time complexity is, worst case, O(n^2). The reduce runs in O(n) time, and you run a reduce for every entry in arr, making it O(n^2).

(.find也是O(n)操作，但O(n) + O(n) = O(n))

(The .find is also an O(n) operation, but O(n) + O(n) = O(n))

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

Your code that sorts the array beforehand has the right idea for decreasing complexity, but it has a couple flaws.

• 首先，您应该按数字顺序对 ((a, b) => a - b))进行排序；没有参数的.sort()将按字母顺序排序(例如，[1, 11, 2]是不可取的).

• First, you should sort numerically ((a, b) => a - b)); .sort() with no arguments will sort lexiographically (eg, [1, 11, 2] is not desirable).

第二，仅递减idxFromBack是不够的:例如，sumOfTwo([1, 3, 8, 9, 9], 9)不会看到1和8是匹配项.也许最好的策略是改为使用while进行振荡:从idxFromBack开始，向后迭代直到找到匹配项或总和太小，然后 也向前迭代直到匹配项出现为止.找到或总和太大.

Second, just decrementing idxFromBack isn't enough: for example, sumOfTwo([1, 3, 8, 9, 9], 9) will not see that 1 and 8 are a match. Perhaps the best strategy here would be to oscillate with while instead: from a idxFromBack, iterate backwards until a match is found or the sum is too small, and also iterate forwards until a match is found or the sum is too large.

您还可以通过不使用复杂度为O(n log n)的.sort((a, b) => a - b)而不是使用基数排序或计数排序(二者均具有O(n + k)的复杂度，其中是一个常数).最优算法将取决于输入的总体形状和方差.

You can also improve the performance of this code by sorting not with .sort((a, b) => a - b), which has complexity of O(n log n), but with radix sort or counting sort instead (both of which have complexity of O(n + k), where k is a constant). The optimal algorithm will depend on the general shape and variance of the input.

一种更好的，完全不同的O(n)策略将是使用Map或Object.在数组上进行迭代时，将与当前项目匹配的将要产生结果的值放入对象的键(该值是当前索引)中，然后看看是否当前最初在对象中存在要迭代的值:

An even better, altogether different O(n) strategy would be to use a Map or object. When iterating over the array, put the value which would result in a match for the current item into a key of the object (where the value is the current index), and just look to see if the current value being iterated over exists in the object initially:

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)   // => []
);

这篇关于Javascript Array.reduce()和Array.find()的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！