algorithm - 选择第 i 个最小数的算法

Question

我正在阅读《算法导论》一书，第二版，有关中位数和阶次统计的章节。我有一些关于随机和非随机选择算法的问题。

问题: 给定一个无序整数数组，找到数组中第 i 个最小元素

a. Randomized_Select 算法很简单。但我无法理解解释工作时间的数学。是否可以在不进行深入数学的情况下以更直观的方式解释这一点？对于我来说，我认为它应该适用于 O(nlog n)，在最坏的情况下它应该是 O(n^2)，就像快速排序一样。 avg randomizedPartition 返回靠近数组中间的位置，并且每次调用将数组分为两部分，并且下一次递归调用只处理数组的一半。 RandomizedPartition 的成本为 (p-r+1)<=n，因此我们的复杂度为 O(n*log n)。在最坏的情况下，它会每次选择数组中的最大元素，并将数组分为两部分 - 每一步 (n-1) 和 (0)。这是 O(n^2)

下一个(选择算法)比上一个更难以理解:

b.和以前相比有什么区别。平均速度更快吗？

c.该算法由五个步骤组成。在第一个中，我们将数组分为 n/5 个部分，每个部分有 5 个元素(除了最后一个元素之外)。然后使用插入排序对每个部分进行排序，并选择每个部分的第三个元素(中位数)。因为我们已经对这些元素进行了排序，所以我们可以确定前两个 <= 这个主元元素，而后两个 >= 那么它。然后我们需要在中位数中选择 avg 元素。书中指出，我们对这些中位数递归地调用Select算法。我们怎样才能做到这一点？在选择算法中，我们使用插入排序，如果我们要交换两个中位数，我们需要交换每个中位数的“子”元素的所有四个(或者甚至更多，如果是更深入的步骤)元素。或者我们是否创建仅包含先前选择的中位数的新数组，并在其中搜索中位数？如果是，我们如何将它们填充到原始数组中，因为我们之前更改了它们的顺序。

其他步骤非常简单，类似于 randomized_pa​​rtition 算法。

Answer 1

随机选择的运行时间复杂度为 O(n)。看this analysis .

Algorithm :
Randomly choose an element
split the set in "lower than" set L and "bigger than" set B
if the size of "lower than" is j-1 we found it
if the size is bigger, then Lookup in L
or lookup in B

总成本是以下各项的总和:

• 拆分大小为 n 的数组的成本
• 在 L 中查找的成本或在 B 中查找的成本

已编辑:我尝试重组我的帖子

您可以注意到:

• 我们总是选择元素数量较多的集合中的下一个
• 该集合中的元素数量为 n - rank(xj)
• 1 <= rank(xi) <= n所以1 <= n - rank(xj) <= n
• 元素的随机性 xj直接影响元素个数的随机性 更大xj (并且小于 xj )

如果 xj 是所选元素，那么您就知道成本为 O(n) + cost(n - rank(xj)) 。我们调用rank(xj) = rj .

为了给出一个好的估计，我们需要获取总成本的期望值，即

T(n) = E(cost) = sum {each possible xj}p(xj)(O(n) + T(n - rank(xj)))

xj是随机的。之后就是纯数学了。 我们得到:

T(n) = 1/n *( O(n) + sum {all possible values of rj when we continue}(O(n) + T(n - rj))) )
T(n) = 1/n *( O(n) + sum {1 < rj < n, rj != i}(O(n) + T(n - rj))) )

在这里您可以更改变量，vj = n - rj

T(n) = 1/n *( O(n) + sum { 0 <= vj <= n - 1, vj!= n-i}(O(n) + T(vj) ))

我们将 O(n) 放在总和之外，得到一个因子

T(n) = 1/n *( O(n) + O(n^2) + sum {1 <= vj <= n -1, vj!= n-i}( T(vj) ))

我们把 O(n) 和 O(n^2) 放在外面，丢掉一个因子

T(n) = O(1) + O(n) + 1/n *( sum { 0 <= vj <= n -1, vj!= n-i} T(vj) )

查看有关如何计算的链接。

对于非随机版本:

你自己说: 平均随机分区返回数组中间附近。

这正是随机算法起作用的原因，也正是它用于构建确定性算法的原因。理想情况下，您希望确定性地选择枢轴，以便它产生良好的分割，但良好分割的最佳值已经是解决方案!因此，在每一步中，他们都需要一个足够好的值，“至少是枢轴下方数组的 3/10，至少是上方数组的 3/10”。为了实现这一目标，他们在每一步将原始数组分成 5 个，这也是一个数学选择。