两种不同方法的时间和空间复杂度

Question

我正在尝试学习如何估算不同迭代的时间和空间复杂度，并且需要第二种方法的帮助。下面这两个函数在时空复杂度上有什么区别？

这应该是O(n)时间和O(n)空间。

function twoNumberSum(array, targetSum) {
  let nums = {};

  for (const num of array) {
    const potentialMatch = targetSum - num;

    if (potentialMatch in nums) {
      return [potentialMatch, num].sort((a, b) => a - b)
    } else {
      nums[num] = true
    }
  }

  return []
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

但是，这种方法吗？

function twoNumberSum(array, targetSum) {
  const map = new Map(array.map(item => [item, item]));

  for (let [key, value] of map) {
    const missingInc = targetSum - value;
    if (missingInc !== value && map.has(missingInc)) {
      return [value, map.get(missingInc)].sort((a, b) => a - b)
    }
  }

  return [];
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

还有，最后一个问题...当我用.sort((a, b) => a - b)对return语句进行排序时，应将其定义为O(log(n))吗？

Answer 1

我建议首先将它们重构为使用相同的数据结构，以使差异变得更加明显：

function twoNumberSum(array, targetSum) {
  let nums = new Set();
  for (const num of array) {
    const potentialMatch = targetSum - num;
    if (nums.has(potentialMatch) {
      return [potentialMatch, num].sort((a, b) => a - b)
    } else {
      nums.add(num)
    }
  }
  return []
}

function twoNumberSum(array, targetSum) {
  const nums = new Set();
  for (const num of array)
    nums.add(num);
  // alternatively, use const nums = new Set(array), but the loop is clearer
  for (let num of array) {
    const missingInc = targetSum - num;
    if (missingInc !== value && nums.has(missingInc)) {
      return [value, missingInc].sort((a, b) => a - b)
    }
  }
  return [];
}

在考虑性能之前，我们需要评估正确性/等效性：请注意，当输入值包含重复项时，第二个功能不起作用。但让我们假设这是一个前提条件（永远不会发生），在这种情况下，结果总是相同的。

不同之处在于，一种方法总是在测试值之前构造整个查找图，而另一种方法则是随时随地构建它。虽然两者都具有O(n)最坏情况复杂度，但第一种方法的最佳情况复杂度是O(1)，而第二种方法的最佳情况复杂度是O(n)。 average的复杂度取决于输入的分布方式。

当我用.sort((a, b) => a - b)对return语句进行排序时，应将其定义为O(log(n))吗？

没有排序的复杂度通常为O(n log n)，但其中n表示要排序的数组的长度。在您的情况下，您总是将两个项目组成的数组进行排序，这具有恒定的复杂性。它不取决于输入n的大小（假定为array.length，尽管在某些数字问题中，您还需要考虑数字的大小）。