我是pretty的新的这个东西，我需要你的帮助。

I'm pretty new to this stuff and I need your help.

我要建立一个高效的算法简单，它返回的最大值与n个大小的数组包含数字1,2，...，n，其中重复。

I should build an efficient simple algorithm which returns the maximum value in an array with size of n which contains the numbers 1,2,...n with repetitions.

然后，我要确定最佳运行时间，平均运行时间和最坏运行时间。

Then I have to determine the best running time, average running time and worst running time.

所以，我有两个问题：

首先我想了解什么是需要为这个简单的算法有效的解决方案的想法。据我了解，我应该只需要一个简单的循环，从1到n，寻找最大值。是高效的算法指出，如果我发现数组中的n的值，我可以停止搜索更多的价值，因为这是在数组中的最大值？

First of all I'm trying to understand what's the idea of requiring an efficient solution for this simple algorithm. As far as I understand I should only have a simple loop from 1 to n and look for the maximum value. Is the "efficient" algorithm points out that If I find the value n in the array I can stop searching more values because this is the maximum value in the array?

我如何确定最佳的运行时间和平均运行时间使用的事实，而计算的平均运行时间，它是一个均匀分布。 即，阵列中的每个单元具有1 / n的机会成为最大值。

How do I determine the best running time and average running time using the fact, while calculating the average running time, that It's a uniform distribution. That is, each cell in the array has a chance of 1/n to be the maximum value.

感谢很多提前！

推荐答案

最好的情况 - 寻找最大的元素作为第一个（ O（1）），最坏的情况 - 这是检查的最后一个元素（ O（N））。

Best case - finding the max element as the first (O(1)), worst case - it is the last element checked (O(n)).

最棘手的部分是平均情况。 要找到平均情况 - 我们需要反复的预计号

The tricky part is the average case. To find the average case - we need the expected number of iterations!

既然你可以停止后，你会发现最大的，我们可以分割问题分为两个部分：

Since you can stop after you find the maximum, we can split the problem into two parts:

[0，N-1）：由于平均（假设均匀独立分布的每个元素） - 数 N 的概率为1 / N是在每个地方，迭代这部分则期望的数量 1 / N + 2 *（（N-1）/ N）/ N + 3 * （第（n-1）/ N）^ 2 / N + ... +（N-1）*（（N-1）/ N）^（N-2）/ N 1 上面的公式得到一个丑陋的公式是 O（N） 在最后一个元素是要进行检查，如果前n-1个元素不包含值 N ：所以你需要添加上述 N *（（N-1）/ N）^（N-1），这是 O（N）以及（LIM到无穷远的 1 / E * N ）。 [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) The last element is going to be checked if the first n-1 elements did not contain the value n: so you need to add to the above n* ((n-1)/n)^(n-1), which is O(n) as well (lim to infinity is 1/e * n).

这总计在 O（N）平均时间的解决方案。

This totals in O(n) average time solution.

（1）：公式为每一个元素都是Ĵ*（（N-1）/ N）^（J-1）*（1 / N），因为

(1): The formula for each element is j*((n-1)/n)^(j-1) * (1/n) because:

Ĵ - 为选中的元素的数量（迭代次数） （（N-1）/ N）^（J-1） - 概率不存在 N 在previous元素 （1 / N） - 概率这个数字是 N j - for the number of elements checked (number of iterations) ((n-1)/n)^(j-1) - Probability that there is no n in the previous elements (1/n) - Probability this number is n.