javascript - 你如何评估 Javascript 中固有的对象方法并用 Big-O 表达它？

Question

在计算大 O 符号时，我们是否也评估固有的 javascript 方法？如果我们不这样做，我有理由相信这是 O(N)。如果我们这样做，我将如何用 big-O 表达他的想法？您是如何得出这个结论的？

注意 1:这篇文章已经过编辑，将“x”更改为 25，循环已修复注2:字符串可以是任意大小

// the string can be any size
while( i++ < 25) {//edited from previous post - this was formerly "x"

    regex = RegExp( MyArray[i],'g' );    
    if ( (myString.match(regex)||[]).length ){      
        myObj.push([   
            myArray[i], (myString.match(regex)||[]).length
        ]);    
        myString = myString.replace(regex,'');
    }   
}
myObj.sort(function(a, b) {return b[1] - a[1]});

Answer 1

您确实必须考虑不是您编写的代码。

要正确确定一段代码的 big-O(效率顺序)，假设您将所有方法调用替换为它们背后设置的实际代码。

---

在您给出的示例中，您必须考虑 while 循环的效率，每次调用 myString.match，调用 myObj.push，调用myString.replace，以及对 myObj.sort 的调用。

---

我不是 100% 确定每种方法的效率，但我会做一些猜测。

假设

• 匹配是 O(m)，
• 推送是 O(1)，
• 替换为 O(m) 和
• 排序复杂度为 O(n log n)

其中 m 是 myString.length 而 n 是 myObj.length。

那么你的代码就是 O(x * (3m + 1) + n log n)

减少到大约 O(x*m)

---

编辑

由于您的循环现在是固定次数的迭代，因此计算将是 O(1 * (3m + 1) + n log n)

通过此编辑，新的近似值是O(n log n)，因为效率取决于排序函数的顺序(只要排序在更差 比 O(m) 时间。