1

我在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;
}
4

5 回答 5

6

忍不住重写

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)

于 2013-01-09T10:49:13.053 回答
1

算法的复杂度是O(N)。

如果您需要平均迭代次数，则如果数组带有随机布尔值，则预期为 (1/1 + 1/2 + 1/4 +.. + 1/N) = ( 2 - 1/N ) 次迭代。

于 2013-01-09T13:27:40.383 回答
0

平均情况也是 O(n)

于 2013-01-09T10:45:14.633 回答
0

平均情况将是 O(n) 作为最坏情况，因为它的数组迭代。

于 2013-01-09T10:46:20.913 回答
0

因为这是 BOOLEAN 数组，所以平均复杂度是常数 O(1.5)，最差的 O(n)。

于 2013-01-09T10:50:46.227 回答