我对这些东西还很陌生，我需要你的帮助。
我应该构建一个高效的简单算法，该算法返回大小为 n 的数组中的最大值，其中包含重复的数字 1,2,...n。
然后我必须确定最佳运行时间、平均运行时间和最差运行时间。
所以我有两个问题：
首先，我试图理解这个简单算法需要有效解决方案的想法是什么。据我了解，我应该只有一个从 1 到 n 的简单循环并寻找最大值。 “高效”算法是否指出，如果我在数组中找到值 n，我可以停止搜索更多值，因为这是数组中的最大值？
在计算平均运行时间时，如何使用均匀分布这一事实来确定最佳运行时间和平均运行时间。
也就是说，数组中的每个单元格都有 1/n 的机会成为最大值。
预先非常感谢！
最好的情况 - 找到最大元素作为第一个（O(1)），最坏的情况 - 它是最后一个检查的元素（O(n)).
棘手的部分是平均情况。
为了找到平均情况 - 我们需要expected http://en.wikipedia.org/wiki/Expected_value迭代次数！
由于找到最大值后就可以停止，因此我们可以将问题分为两部分：
-
[0,n-1): Since on average (assuming uniform independent distribution for each element) - the number n has probability 1/n to be in each place, then the expected number of iterations for this part is 1/n + 2*((n-1)/n)/n + 3 * ((n-1)/n)^2/n + ... + (n-1) * ((n-1)/n)^(n-2)/n 1
The above formula yields an ugly formula which is O(n) http://www.wolframalpha.com/input/?i=sum%20j*%28%28n-1%29/n%29%5E%28j-1%29%20*%20%281/n%29%20j%20from%201%20to%20n-1%20
- 如果前 n-1 个元素不包含该值，则将检查最后一个元素
n: 所以你需要添加到上面n* ((n-1)/n)^(n-1)，即O(n)以及（极限到无穷大是1/e * n).
这总计为O(n)平均时间解。
(1)：各元素的计算公式为j*((n-1)/n)^(j-1) * (1/n)因为：
-
j- 检查的元素数量（迭代次数）
-
((n-1)/n)^(j-1)- 不存在的概率n在前面的元素中
-
(1/n)- 这个数字的概率是n.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
