用中断确定循环的大O.

Question

给定这样的函数来查找素数:

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).

你能解释一下这个突破是如何影响大的吗？它有吗？

Answer 1

你的代码是O(1),因为它总是会在第二个循环上退出,因为数字%1 == 0.

如果您将代码更正为:

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

然后由于@zmf说的相同的原因,它将是O(n).

如果没有中断,O(n)即使是"最佳情况" 也会更准确地调用它,因为它仍然可以根据输入进行扩展.最小的输入不是"最佳情况",否则所有算法都是最好的情况O(1).

所以它O(n)没有休息和O(n)休息,但这并不意味着休息时它显然不会更好更快.big-O表示法是关于算法如何根据输入的大小缩放,而不是(必然)它的速度.有时,O(n)算法可能比O(log n)特定输入的算法更快.