平均情況複雜 - 計算線性算法

Question

只是一個簡單的問題：

如果我有一個線性搜索算法（它會經過的每一個元素，一旦達到一定的條件下），我怎麼能計算出平均情況複雜對於n = 500？最壞的情況和最好的情況很容易。

Answer 1

平均情況同樣很簡單：只要你發現的物品是獨一無二的，平均來說，你將不得不在查看列表+ 0.5的一半。

讓我們假設你查看列表中的每個項目一次。當你查找第一個項目時，你將不得不檢查一個項目。當你查看第二個項目時，你將不得不檢查2個項目，等等。檢查總數爲

1 + 2 + 3 + ... + 500 = 125250 

因此，通過500次查找，您將總共檢查125250個項目。平均而言，每次查詢的檢查次數爲250.5次。

如果您的查找模式不均勻，那麼這會使您的平均情況偏差（例如，如果您更頻繁地查找列表開頭的項目，或者某些項目被重複查找並找到其中任何項目就足夠了）

Answer 2

線性搜索算法的平均情況複雜度爲n + 2 其中n是列表中元素的數量。