为何时间复杂度O(n²)的JS函数比O(n)的运行更快？

先明确核心结论：你对两个函数的时间复杂度判断有偏差，且foo的实现存在高常数项开销，这是导致它更慢的关键。

一、纠正时间复杂度的误解 #

bar的时间复杂度并非严格意义上的O(n²)：

• bar里的every遍历phones数组（长度n≈250），每次调用的COMPANIES.includes(type)是遍历固定长度的数组（COMPANIES只有8个元素，属于常数m）。
• 渐近复杂度分析中，常数项会被忽略，所以bar的实际时间复杂度是O(n*m)=O(n)，而非O(n²)。只有当COMPANIES的长度随phones的长度n增长时，才会达到O(n²)。

二、foo性能差的具体原因 #

foo的实现存在多个高开销操作：

• reduce中频繁创建新对象：每次迭代都用{ ...acc }复制整个累加对象，随着acc里的属性增多，复制的开销会越来越大。250次迭代就会创建250个新对象，带来大量内存分配和后续垃圾回收工作，这是最大的性能瓶颈。
• 额外的遍历与对象操作：reduce之后还要遍历COMPANIES删除属性，再调用Object.values生成数组，这些额外的O(m)操作进一步增加了开销。

三、bar性能更优的原因 #

bar的实现更轻量化，且有隐性优化：

• 无内存复制开销：全程只是数组遍历和简单的查找判断，没有对象复制、属性删除这类高开销操作，内存使用更高效。
• 提前终止遍历：every方法是短路求值的——只要有一个元素不满足条件，就会立刻停止遍历返回结果。比如lgCheck里，只要找到一个LG类型的元素，就会直接返回false，不用遍历完所有250条数据，实际执行的次数可能远小于n。
• 操作简洁直接：逻辑链短，没有多余的中间数据处理（比如foo里的typesCount对象），减少了数据流转的开销。

附原代码 #

const LANGUAGES = {
  ENGLISH_US: 'en-US',
  ENGLISH_UK: 'en-GB'
}

const COMPANIES = [
    'Apple',
  'Samsung',
  'Huawei',
  'One Plus',
  'Google',
  'Sony',
  'Vivo',
  'LG'
];

const loading = false;
const showLG = false;

const generateData = () => {
    const res = [];
  let counter = 0;
  for(let i=1; i<250; ++i) {
    if (counter <= 6) {
        res.push({id: i, type: COMPANIES[counter]});
      ++counter;
    }
    else {
        counter = 0;
      res.push({id: i, type: COMPANIES[counter]});
      ++counter;
    }
  }
  res.push({id: 25, type: 'LG'});
  return res;
}

const data = {
  elements : {
      language: 'en-US',
      phones: generateData(),
    }
}

function foo() {
  const typesCount = data?.elements?.phones?.reduce((acc, { type }) => {
    if (acc[type] === undefined) {
      acc[type] = 0
    }
    return { ...acc, [type]: acc[type] + 1 };
  }, {});

  const isLGPresent = !!typesCount['LG'];

  COMPANIES.forEach(type => {
    delete typesCount[type];
  })

  const unsupportedTypes = !!Object.values(typesCount).length;

  const lgCheck = !showLG && !isLGPresent;

  const isLangSupported = Object.values(LANGUAGES).includes(data?.elements?.language);

  const isSupported = !unsupportedTypes && lgCheck && isLangSupported;

  if (!loading && !isSupported) {
    // console.log('foo')
  }
}

function bar() {
  const isPhoneSupported = data?.elements?.phones?.every(
    ({ type }) => COMPANIES.includes(type),
  );

  const lgCheck = !showLG
    && data?.elements?.phones?.every(({ type }) => type !== 'LG');

  const isLangSupported = Object.values(LANGUAGES).includes(
    data?.elements?.language,
  );

  const isSupported = isPhoneSupported
    && lgCheck
    && isLangSupported;

  if (!loading && !isSupported) {
    // console.log('bar')
  }
};

// for warm up
let start = performance.now();
foo();
let end = performance.now();


let start1 = performance.now();
foo();
let end1 = performance.now();
let timeTaken1 = end1 - start1;


let start2 = performance.now();
bar();
let end2 = performance.now();
let timeTaken2 = end2 - start2;


console.log(`Time taken 1: ${timeTaken1}`);
console.log(`Time taken 2: ${timeTaken2}`);
console.log(`Difference: ${timeTaken2 - timeTaken1}`);

内容的提问来源于stack exchange，提问作者newbie