简单＆QUOT;在阵列QUOT最大值;和复杂的计算 [英] Simple "maximum value in array" and complexity calculations

问题描述

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

1. 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:

1. [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 ¹
   <一href="http://www.wolframalpha.com/input/?i=sum%20j%2a%28%28n-1%29/n%29%5E%28j-1%29%20%2a%20%281/n%29%20j%20from%201%20to%20n-1%20"相对=nofollow>上面的公式得到一个丑陋的公式是 O（N）
2. 在最后一个元素是要进行检查，如果前n-1个元素不包含值 N ：所以你需要添加上述 N *（（N-1）/ N）^（N-1），这是 O（N）以及（LIM到无穷远的 1 / E * N ）。

1. [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 ¹
   The above formula yields an ugly formula which is O(n)
2. 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.

这篇关于简单＆QUOT;在阵列QUOT最大值;和复杂的计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！