更好的时间复杂度一定对应更快的运行速度吗？以LeetCode珠宝与石头题为例

这种情况十分常见，核心原因是时间复杂度的理论定义和实际小数据量下的执行表现存在差异，具体可以分为三点说明：

• 时间复杂度描述的是数据规模趋近于无穷大时，执行效率的增长趋势，仅在数据量足够大时才能体现出阶数优势。本题的LeetCode测试用例规模极小，题目约束中jewels长度最多为50，stones长度最多为50，哪怕是O(n*m)的平方级解法，总运算量也只有2500次，和线性解法的运算量差距极小，不足以抵消常数项的开销差。
• 解法1的常数项开销更高：首先你的哈希表实现存在冗余操作，题目明确说明jewels中的字符互不重复，不需要对jewels的字符做计数，只要标记是否存在即可，多余的计数逻辑增加了不必要的开销；其次两次字符串转数组、两次forEach遍历、普通对象作为哈希表的属性读写都是JS层面的执行逻辑，额外开销更高。
• 解法2调用的都是JS引擎内置方法：split、reduce、includes都是JS引擎底层用C/C++实现的原生方法，经过了极致的性能优化，执行效率远高于手写的JS层面逻辑，哪怕算法阶数更高，小数据量下总耗时反而更短。

如果把测试用例规模放大两个数量级，比如jewels长度到10^{4，stones长度到10}5，线性复杂度的解法性能就会远超平方复杂度的解法，复杂度阶数的优势才会真正体现。

解法1（哈希表实现） #

var numJewelsInStones = function(jewels, stones) {
  let obj = {}
  const jewelsArr = jewels.split('')
  let count = 0
  jewelsArr.forEach((el, i) => {
      obj[el] ? obj[el]++ : obj[el] = 1   
  })
  const stonesArr = stones.split('')
  stonesArr.forEach((el, i) => {
    if (obj[el]) {
      count++
    } })
  return count
};

解法2（数组方法实现） #

var numJewelsInStones = function(J, S) {
  return S.split('').reduce((a, c) => a += Number(J.includes(c)), 0);
};

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