计算js alghortim的复杂度

Question

我正在尝试用大 O 表示法计算以下方法的复杂性

function algorithm(n,m){
    let result = [];

    for (let i = 0; i < n.length; i++) {
      const total = m.filter((x) => x === n[i]).length;
  
      if (PrimalityTest(total)) {
        result.push(n[i]);
      }
    }
    return result;
  };


function PrimalityTest(c){
    if (c <= 1) {
        return false;
      } else if (c === 2) {
        return true;
      } else {
        for (let i = 2; i * i <= c; i++) {
          if (c % i === 0) {
            return false;
          }
        }
        return true;
      }
}

所以，首先是一个复杂度为 O(n) 的循环，然后是嵌套循环和素数测试函数，这意味着所有的复杂度都是 O(n * m * sqrt(c))?

能否请您确认一下我的理解是否正确？

Answer 1

循环for (let i = 0; i < n.length; i++) 执行了n次。函数 m.filter((x) => x === n[i]).length 检查 m 中的每个元素，因此执行 m-times。所以我们有 O(n*m) 的执行时间。

正在考虑

if (PrimalityTest(total)) {
      result.push(n[i]);
}

执行了n次，因为和上面在同一个循环中。所以最坏的情况是 O(n*sqrt(c))

总结起来就是：O(n*m)+O(n*sqrt(c))。因为 O(n*m) 超过 O(n*sqrt(c)) 我们得到结果：O(n*m).

您的解决方案意味着过滤器功能集成了 PrimalityTest 方法。

计算js alghortim的复杂度

Calculating complexity of js alghortim

javascript

big-o

complexity-theory