这个简单算法的计算复杂性

Question

我在java中计算了这个算法的最佳案例复杂度,平均值和最差值,我认为如果O (1)在最坏的情况下是好的O (n),但我不知道是否平均!你能帮我解决一下吗？谢谢!

public boolean searchFalse(boolean[] b){ 
 boolean trovato=false; 
  for(int i=0;i<b.length;i++){
   if(b[i]==false){
 trovato=true;
 break;
   }
  }return trovato;
}

Answer 1

我无法抗拒重写它

public boolean searchFalse(boolean[] bs){
    for (boolean b : bs) if(!b) return true;
    return false;
}

这在第一个元素可能为O(1)之后停止.

如果所有布尔值都是随机的,则平均搜索时间为O(1),因为平均执行2次搜索,或者如果在随机位置通常有一个假值,则平均值为O(N)

如果必须一直搜索,最坏的情况是O(N)

总之O(N/2)= O(N)