获取时间复杂度

Question

我写了这个算法。你能帮我计算一下 'the time complexity' 吗？我没有嵌套函数，但在地图中有 .includes。

function prime(num) {
  for (var i = 2; i < num; i++) if (num % i === 0) return false;
  return num > 1;
}

const function = (dataA, dataB) => {
  let temp = {};
  let tempArray = [];
  dataB.forEach(function (x) {
    temp[x] = (temp[x] || 0) + 1;
  });
  dataA.map(item => {
    if (dataB.includes(item) && !prime(temp[item])) {
      tempArray.push(item);
    } else if (!dataB.includes(item)) {
      tempArray.push(item);
    }
  });
  return tempArray;
};

console.log('Input A:', A);
console.log('Input B:', B);
console.log('Output:', function(A, B));

Answer 1

您的 isPrime 函数的最坏情况时间复杂度为 O(n)。

forEach 函数是一个单独的 O(n) 函数。

map 函数计算 dataA 中的每个项目并在每个 includes 和 isPrime 函数中执行 O(n)。

因此，总时间复杂度为 O(n^2)。

Answer 2

一些观察：

B.includes 的时间复杂度为 O(B.length)
isPrime 的时间复杂度为 O(num)。由于参数是 B 中某个值的频率，它受 B 的大小限制，因此它的最坏情况为 O(B.length)，因为 isPrime 仅在 B.includes 被调用，因此它与整体时间复杂度无关。
因为B.includes被调用的次数和A中的值一样多，总的时间复杂度是O(A.length * B.length)

可以通过将B.includes(item)替换为count[item]来降低复杂度，然后isPrime成为确定。如果 isPrime 通过记忆扩展，所有 isPrime 调用的总成本是 O(A.length + B.length)，所以这也是整体时间复杂度。

这不能进一步减少，因为即使不调用 isPrime，对两个输入数组的迭代也是必要的，并且已经代表了时间复杂度。

获取时间复杂度

Getting the time complexity

javascript

algorithm

time-complexity