預計分配的數量陣列中的

在下面的Java代碼中找到最大值：預計分配的數量陣列中的

int max = arr[0]; 
for (int i = 0; i < arr.length i++) { 
    if (arr[i] > max) { 
     max = arr[i]; 
    } 
}

多少次行max = arr[i];運行假設數組是未排序的。

每次它會在數組中找到小於最大值的值。 – sAm

但是，它必須有一個數字預期的運行次數 – 12345webster12345

該代碼是最小值，而不是最大值。 –

預期值可以通過預期的線性來計算。如果此站點支持MathJax，我可以提供更嚴格的答案。

對於i = 1到n = 0（log n），答案是i = 1到n = sum 1/i的總和1 /（n-i + 1），其中n是數組的大小陣列的所有元素都是不同的）

警告，Math-sy部分在前面。

關鍵的想法是，如果我們爲每個元素分配一個詞典索引'i'，其中'i'表示該元素是'i'的最小元素，那麼只有當沒有n-i在數組中的第i個元素之前+1個更大的元素apprar。這發生在隨機數組中的概率對於所有i是1 /（n-i + 1）。然後我們使用一個指標隨機變量來應用期望線性度:)

2016-03-26 20:26:15

參見https://en.wikipedia.org/wiki/Harmonic_series_(mathematics） –

回答