最多可以更新多久？

Algorithm Find-Max(Array, size) 
Max = -INFINITY 
for k:= 1 to n do 
    if(A[k] > Max-sf) Then 
     Max-sf:=A[k] 
    end if

的問題是，什麼是平均時間是可變的最大更新？

我正在練習算法分析，下面是我的想法，但我不確定，所以我想徵求意見。設T（n）爲find-Max中每次調用的大小爲n的比較次數。

T(n) = T(n-1) + 1/n

其中的1/n的概率，使得最大數是在索引n。因此，

T(n-1) = T(n-2) + 1/(n-1) 
T(n-2) = T(n-3) + 1/(n-2)

通過伸縮，

T(n) = 1/n + 1/(n-1)+ 1/(n-2) + .... + 1

，這是調和級數。因此，變量Max-sf更新的平均時間是log（n））

這就是我證明它的方式。

所以，我想問3個問題：（1）上述證明是否正確？（2）有沒有辦法獲得比較數的精確值？（3）假設我們使用分而治之的方法，通過使用類似的想法作爲合併排序而不是掃描數組，更新的數量是否仍然相同？

這可能不是最好的地方問這個問題。我們是編碼員，而不是數學家。我們使用數學，但很少作爲證明的一部分。你可以參考這個數學StackExchange ... – panoptical

重複http://stackoverflow.com/questions/19075066/time-complexity-of-below-algorithm/19075448是的，它是O（log n） –

@panoptical謝謝你的建議。因爲這裏有很多程序員都非常擅長數學:) – FiveFiftyFive

1）我不確定你的證據，但我發現this one是最正式和最令人信服的證明。

2）確切的比較次數似乎是固定的。你總是在循環中進行n次比較。

3）關於分而治之選擇，它不能超過更新的最壞情況數目（其爲n）較好，因爲它的行爲就像：

T(n) = 2T(n/2) + 1

這導致T（2^n）= 2 * 2^n-1，這意味着Theta（n）複雜度。

2014-02-21 07:54:24

@Eval非常感謝。對於問題2，我犯了錯字。我的意思是更新的平均數量而不是比較。我要去探索你的證明。再次感謝你。 – FiveFiftyFive

回答