确定带有断点的循环的大O值

Determining Big O of a loop with a break

本文关键字：循环 断点      更新时间：2023-09-26

给定一个查找素数的函数:

function find_the_prime(number) {
  var found = false;
  for(var i = 0; i < number; i++) {
    if(number%i == 0) {
      found = true; 
      break;
    }
  }  
  return found;
}

如果没有断点，函数在最佳情况下为O(1)，在最坏情况下为O(n)，一般情况为O(n)。

你能解释一下中断是如何影响大0的吗?真的吗?

你的代码是0(1)，因为它总是在第二次循环时退出，因为数字%1 == 0。

如果您将代码更正为:

for(var i = 2; i < number; i++) {

那么它将是O(n)，原因与@zmf所说的相同。

如果没有中断，即使在"最佳情况"下，它也可以更正确地称为O(n)，因为它仍然随输入缩放。最小的输入不是"最佳情况"，否则所有的算法都是微不足道的最佳情况O(1)。

因此，没有中断的O(n)和中断的O(n)，但这并不意味着中断后的效果和速度没有明显改善。大o符号是关于算法如何随着输入的大小而扩展，而不是(一定)它有多快。有时候，对于特定的输入，O(n)算法可能比O(log n)算法更快。

这仍然是O(N)，即使这是最坏的情况，O(N)是你对这个算法的称呼。其生长速率仍依赖于n

(如果你修复了这个bug)

实际上，有趣的是，你的答案是0(1)。不管你输入的是什么数字(只要它> 0)，它总是在1

处中断
相关文章：