用于检查子集的 js 函数的大 O 表示法

Big O notation for a js Function to check subset

我写了一个函数来检查数组的子集。 对于big-o notation,这个函数怎么解释? 这个函数只是 O(n) 吗?

function isSubset(arr1, arr2) {
  return arr2.filter(function(e) { return arr1.indexOf(e) < 0 })==0;
}

isSubset(['A','B','C','D','E'],['A','D','Z'])  -> false

isSubset(['A','B','C','D','E'],['A','E','D']) -> true


Javascript filter 函数将遍历所有元素,因此其复杂度为 O(n)。在这里找到函数原型 Array.prototype.filter

在遍历 filter 中的每个元素时,您正在使用 indexOf 函数,该函数还会遍历第二个数组中的所有元素,直到找不到匹配的字符,因此它的复杂度也是O(m)。在这里找到函数原型 Array.prototype.indexOf

由于 indexOf 是嵌套的,因此其复杂度将乘以 filter 复杂度,即 O(n*m)

所以 isSubset 复杂度将是 O(n*m)

0(n)分类有4条规则。

规则 1:总是最坏的情况。

规则 2: 删除常量。

规则 3:不同的输入应该有不同的变量。

  1. (+) for steps in order.

  2. (*) for nested steps.

规则 4: 删除非主导词。

因此,您输入的两个数组的大小不同。因此,根据规则 3,您的时间复杂度将为 0(n*m).