如何计算Javascript中固有的对象方法并用Big-O表示

How do you evaluate inherent object methods in Javascript and express it in Big-O?

本文关键字：方法 对象 表示 Big-O 何计算 计算 Javascript      更新时间：2023-09-26

当计算大0符号时，我们也评估固有的javascript方法吗?如果没有，我有理由肯定这是O(N)如果我们这样做，我该如何用大写字母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]});

你必须考虑那些不是你写的代码

要正确地确定一段代码的大o(效率顺序)，请想象您将所有方法调用替换为它们背后设置的实际代码。

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

我不能100%肯定这些方法的效率，但我可以做一些猜测。

假设

  • 匹配0 (m)，
  • push为0 (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)时间更差)。

Big-O符号总是表示某物的量，您可以指定谈论的是哪个"某物"。有时候这样做真的很重要。当有人说"归并排序是O(n log n)"时，他们的意思是它执行O(n log n)比较和O(n log n)拷贝，其中n是要排序的项数。如果比较和复制总是在常量时间内运行，那么结果将是归并排序运行在O(n log n) time。但这并不总是正确的!例如，字符串比较不是常量时间的。

程序对myString.match()进行25次调用。它执行0 (1)match es。

每次匹配所需的时间取决于正则表达式。它可以是O(n)，其中n是字符串的长度。情况可能会更糟;特别是糟糕的正则表达式可能需要指数级的时间来运行，O(2n)。

假设所有正则表达式在O(n)时间内运行。那么该程序运行时间为0 (n)，其中n为myString的长度。

相关文章：