嵌套循环解决方案的时间复杂度如何比使用缓存的解决方案更差？

Question

我在 leetCode 上解决一个练习，我提供了两个解决方案。练习是这样说的：您得到的字符串 J 代表宝石类型，S 代表您拥有的宝石。 S 中的每个字符都是您拥有的一种石头。您想知道您拥有的宝石中有多少也是珠宝。

J中的字母保证不同，J和S中的字符都是字母。字母区分大小写，因此 "a" 被认为是与 "A" 不同类型的石头。 https://leetcode.com/problems/jewels-and-stones/

所以我给出了这两个解决方案：

const numJewelsInStones = function(J, S) {
let counter = 0;
let jArr = J.split('');
let sArr = S.split('');

for(let i = 0; i < jArr.length; i++) {
    for(let j = 0; j < sArr.length; j++) {
        if(jArr[i] === sArr[j]) {
            counter++; }
    }
}

return counter;

};```

这个有两个不同的循环，应该是 O(n):

  const numJewelsInStones = function(J, S) {
  let counter = 0;
  let cache = {};

  for(let i = 0; i < J.length; i++) {
    cache[J[i]] = true;
  }

  for(let i = 0; i < S.length; i++) {
    if(cache[S[i]]) {
      console.log(S[i])
      counter++
    }
  }
  return counter;
}

根据 leetCode，第一个解决方案需要 44 毫秒，第二个需要 80 毫秒。怎么会这样？

Answer 1

J 最多 52 个字符（所有字母）。

所以我们处理的是小数字，O() 表示法不是很有用...O(s*j) <= O(52s)！

在第二种情况下，构建缓存的时间也不会一致，具体取决于它是否需要调整大小以及为什么您假设查找是 O(n)？仅仅因为你的循环很简单并不意味着它调用的东西很简单。

但运行时间在任何情况下都将真正依赖于输入。

考虑到 s 可能比 j 大得多并且您可以在打印后退出循环，我会重写。

嵌套循环解决方案的时间复杂度如何比使用缓存的解决方案更差？

How can time complexity be worst on nested loop solution than one with cache?

javascript

performance

big-o