algorithm - 在数组中查找最大值时的预期写入次数是多少？

Question

我有一个长度为 N 的正整数随机访问列表，我有一个变量 MAX，我知道我的列表中的最大数是 M(数组中可能没有 M，但不能超过 M ).该算法是我可以随机访问我的列表，在每次访问中我写入值存在于变量 MAX 中，当且仅当它包含的值大于 MAX。

现在我想知道如何使用此算法计算对变量 MAX 的预期写入次数？

希望这个例子更清楚:

List: 2 - 5 - 3 - 1 - 9
Read 2 => Max = 2 (1 write)
Read 5 => Max = 5 (2 writes)
Read 3 => Max = 5 (2 writes) (do not write)
Read 1 => Max = 5 (2 writes) (do not write)
Read 9 => Max = 9 (3 writes) 

Answer 1

对于均匀分布，前 n 个数中第 n 个数最大的概率是 1/n。

这意味着预期的写入次数是1 + 1/2 + 1/3 + 1/4 + 1/5 + .. + 1/N，大约是 ln N(参见:harmonic series)