一千萬個為什麽

搜索

在數組中查找最小值所需的分配數量?

有人問我一個腦筋急轉彎,我不知道;我的知識在攤銷分析後變慢,在這種情況下,這是O(n)。

public int findMax(array) {
  int count = 0;
  int max = array[0];
  for (int i=0; i max) {
      count++;
      max = array[i];
    }
  } 
  return count;
}

對於大小為n的數組, count 的期望值是多少?

從均勻分布中隨機挑選數字。

最佳答案

設f(n)為平均分配數。

然後,如果最後一個元素不是最大的,則f(n)= f(n-1)。

如果最後一個元素是最大的,那麽f(n)= f(n-1)+ 1。

由於最後一個數字最大,概率 1/n ,而不是最大概率(n-1)/ n ,我們有:

f(n) = (n-1)/n*f(n-1) + 1/n*(f(n-1) + 1)

展開並收集條款以獲得:

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

並且f(1)= 0.所以:

f(1) = 0
f(2) = 0 + 1/2
f(3) = 0 + 1/2 + 1/3
f(4) = 0 + 1/2 + 1/3 + 1/4

也就是說,f(n)是第n個“諧波數”,您只能以封閉形式獲得大約。 (好吧,比第n個諧波數少一個。如果你將 max 初始化為 INT_MIN 並讓循環運行,那麽問題會更漂亮,所以f(1)= 1.)

以上並不是一個嚴格的證據,因為我對預期值與實際值的關系很草率。但我相信答案是正確的:-)。

轉載註明原文: 在數組中查找最小值所需的分配數量?