java - 这个简单算法的计算复杂度

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

如果所有 boolean 值都是随机的，则平均搜索时间为 O(1)，因为您平均执行 2 次搜索，或者如果随机位置通常有一个错误值，则平均值为 O(N)

如果要一路寻找，最坏的情况是O(N)

简而言之 O(N/2) = O(N)