algorithm - 简单的 "maximum value in array"和复杂度计算

Question

我对这些东西很陌生，我需要你的帮助。

我应该构建一个高效的简单算法，该算法返回大小为 n 的数组中的最大值，该数组包含数字 1,2,...n 并有重复。

然后我必须确定最佳运行时间、平均运行时间和最差运行时间。

所以我有两个问题:

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

2. 我如何确定最佳运行时间和平均运行时间，在计算平均运行时间时，它是一个均匀分布的事实。即数组中的每个单元格都有1/n的机会为最大值。

提前致谢!

Answer 1

最好的情况 - 找到最大元素作为第一个 (O(1))，最坏的情况 - 它是检查的最后一个元素 (O(n))。

棘手的部分是平均情况。
要找到平均情况 - 我们需要 expected迭代次数!

既然找到最大值就可以停下来，我们可以把问题分成两部分:

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 ¹
   The above formula yields an ugly formula which is O(n)
2. 如果前 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 的概率。