這個簡單算法的計算複雜度

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

來源

2013-01-09 Enzo

n即等於b的長度。 – pratikch

通過嵌套循環的方式對某些實現過程的複雜性進行簡單評估。 – user1929959

我無法抗拒重寫它

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-09 10:49:13

感謝您的幫助！ :) – Enzo

只有在數組中只有一個「false」時才爲真。如果每個值的概率是相同的，那麼我們有一個O（1）。所以O（N/2）沒有假設是錯誤的。 –

@LoïcFévrier好點。如果布爾值是隨機的，則平均時間爲O（logN） –

平均情況也將是爲O（n）

來源

2013-01-09 10:45:14 Renjith

平均情況將是O（n）的作爲最壞的情況，因爲它的陣列迭代。

來源

2013-01-09 10:46:20

你能解釋一下「你的數組迭代」是什麼意思嗎？謝謝！ – Enzo

你正在迭代一個總是給出O（n）的數組'bs'，但是這裏額外的中斷可能發生在1-n或n/2之間的任何地方，它變成O（n/2）= O（n） –

因爲這是BOOLEAN陣列I事情平均複雜度將是恆定O（1.5），最差的O（n）。

來源

2013-01-09 10:50:46 partlov

這是如何與數組類型鏈接的？ – Andremoniy

你能解釋一下你的答案嗎？這與數組的類型有什麼關係？ – micha

一個平均的布爾數組將有一半的元素爲真，一半的元素爲假。所以平均而言，我們會在第一或第二個元素中發現錯誤。如果數組將會是例如double類型的，將會是不同的。 – partlov

算法的複雜性是O（N）。如果需要平均迭代次數，它將是（1/1 + 1/2 + 1/4 + ... + 1/N）=（2 - 1/N）如果數組有隨機數布爾值。

來源

2013-01-09 13:27:40

這個簡單算法的計算複雜度

回答

相關問題