javascript - JavaScript 中 Map 和 For 循环的时间复杂度

Question

我为以下问题尝试了Map和for 循环。由于时间复杂度，我没有看到两者之间有太大的区别。

我认为 JavaScript Map 操作的复杂度是O(1)，而 for 循环的复杂度是O(n)。

const withHash = (array, sum) => {
  // complexity: O(n)
  for (let i = 0; i < array.length; i++) {
    const temp = sum - array[i];

    // complexity: O(1)
    if (HashMap.has(temp)) {
      console.log(
        "Pair with given sum " + sum + " is (" + array[i] + ", " + temp + ")"
      );
    }

    HashMap.set(array[i], array[i]);
  }
};

const withForLoop = (array, sum) => {
  // complexity: O(n)
  for (let i = 0; i < array.length; i++) {
    const temp = array[i];

    // complexity: O(n)
    for (let j = 0; j < array.length; j++) {
      const x = temp + array[j];

      if (x === sum) {
        console.log(
          "Pair with given sum " + sum + " is (" + array[j] + ", " + temp + ")"
        );
      }
    }
  }
};

let HashMap = new Map();

const numbers = [3, 4, 5, 6, 7, 8, 12];
const sum = 15;

console.time();
withHash(numbers, 15);
console.timeEnd();

console.time();
withForLoop(numbers, 15);
console.timeEnd();

为什么尽管withForLoop方法 n 个正方形，但它给出了更快的结果？

标签： javascriptarraysdata-structureshashmap