用于检查子集的 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)
.