概率选择算法

Question

给定：

一个长度为N的数组。

该数组包含整数。

这些整数不一定是有序的。

找到一个算法：

返回(近似的)第K小的数组元素。

具有O(N log N)的运行时间复杂度和O(log N)的空间复杂度。

该算法不必是确定性的。在概率算法的情况下，也需要提供一个衡量近似结果质量的指标。

- Algos

---

请提供更多信息。正在修改什么“选择算法”？如果这是一项作业，请将其标记为作业。 - payne

@Algos - 这是作业吗？如果是的话，那么我确定它的目的是让你自己解决答案。 - Stephen C

我们需要一个高概率下时间复杂度为 O(n log n) 的随机算法。 - Algos

@Jeremiah， 也许一个例子就足够了.. :) - Algos

@Moron - 随机选择枢轴点以使其随机化。 - aaz

Answer 1

将问题视为类似于快速排序。给定数组中的一个元素，您可以在O（n）时间和O（lg n）空间内获取其排名。您可以使用二分查找在O（lg n）次迭代中找到具有给定排名的元素，总共需要O（lg n）空间和O（n lg n）时间。

- Jeremiah Willcock

---

@Algos：您可以在O(n)时间内获取给定元素的排名；我们正在尝试解决的是获取具有给定排名的元素。 - Jeremiah Willcock

@Algos: 假设排名0是最小的数组元素。获取数组的最大和最小元素（称为lo和hi）及其排名（lo_rank和hi_rank）。标记A：然后，在lo和hi之间选择一些元素m（在O(n)时间内），并计算其排名m_rank（在O(n)时间内）。如果m_rank == k，则完成。如果m_rank < k，则将lo和lo_rank替换为m和m_rank，并转到A；如果m_rank > k，则用hi执行相同的操作，并转到A。 - Jeremiah Willcock

@Algos：不，我的意思是排名，就是你展示的那些定义（0和n是排名的限制，你要搜索排名在它们之间的元素）。 - Jeremiah Willcock

我不清楚如何递归，如果m_rank <> k。你能给一个例子吗？ - Algos

我已经阅读了它们，我认为这不符合要求。运行时间为O(n log v)，其中v = 数组中最大值 - 数组中最小值。 - IVlad

Answer 2

不要构建分区。描述分区（在常数空间内），并在此基础上递归选择。

每个快速选择递归到的子数组可以用其边界（最小和最大元素值，而不是它们的索引）来描述。遍历所描述的子数组需要O(n)次比较，这些比较在每个递归级别上都进行，平均情况下与快速排序一样深度为O(log n)。

快速排序在每个递归级别上也进行O(n)次比较，而普通的排列快速选择在平均情况下总共进行O(n)次比较（因为它总是只递归到一个分区中）。

这里有一个示例实现，用于具有普通快速选择实现的不同元素进行比较。：示例实现链接

- aaz

---

@Moron - 你想要每次迭代的时间复杂度为O(1)。"小于给定元素的数字"。 - aaz

@Moron - 你对所有排名低于100的元素进行递归。假设你在排名为50的元素上找到了一个元素，那么你将会对排名在50和100之间的所有元素进行递归。迭代现在不再是免费的，而是每个递归使用2*n次比较。 - aaz

@Moron - 这不是我的假设，我也不需要一个连续的子数组。lo和hi是元素_值_。在每一步中，我将遍历原始数组的所有n个元素，但我将忽略那些不满足lo ≤ x ≤ hi的x。 - aaz

@Moron - 只是一种直观的方法。随机快速选择每步使用 O(n) 次比较，并且期望递归 O(log n) 次，因此运行时间为 O(n log n)。这每步使用额外的 2 n 次比较，并且与快速选择完全相同地递归，因此仍然是 O(n log n)。 - aaz

@白痴 - 是的，快速排序的深度在很大概率下是有界的（1，2，3）。这里的证明甚至稍微简单一些，因为只有一条递归路径，不像快速排序那样必须递归到每个分区。 - aaz

Answer 3

1. 遍历一次数组以找到最小和最大元素。
2. 遍历数组以找到介于最小和最大（不包括）之间的随机元素pivot。
3. 遍历数组并计算小于或等于pivot的元素数目（numSmallerEqual）和大于pivot的元素数目（numBigger）。
   1. 如果K ≤ numSmallerEqual，则设置maximum=pivot。
   2. 否则，设置minimum=pivot。
4. 如果(maximum - minimum)==0，则输出minimum并终止。
5. 如果(maximum - minimum)==1
   1. 如果K ≤ numSmallerEqual，则输出minimum。
   2. 否则，输出maximum。
   3. 终止。
6. GOTO 2：

编辑：已更正lVlad指出的错误，但尚未经过测试。

- Dave O.

---

实际上，这并不需要O(lg n)的空间限制，而是O(1)。非常好！ - corsiKa

除非它是错误的。1 3，k = 2。枢轴= 2，最小值= 1，最大值= 3，numSmallerEqual = 1，最小值= 2。枢轴= 2，numSmallerEqual = 1，最小值= 2...无限循环。 - IVlad

@Dave - 如果我有解决方案，我会建议一个。我不确定如何避免无限循环。 - IVlad

我还没有仔细考虑过你更新的算法的正确性，但值得指出的是它实际上并没有遵循要求。复杂度为O(n log v)，其中v是数组中最大值和最小值之间的差异，而不是O(n log n)。v可以独立于n。 - IVlad

你为什么改变了问题？ - Aryabhatta

Answer 4

你可以采取参数化的方法：

由于问题中给定了 k，我们可以将其视为常数，因此 O(k log N) 的空间应该是可以接受的。

1. 将数组分成等长的 k 个分区（每个分区的边界只需要占用 log N 的空间，因此需要 O(1) 的时间和 O(k log N) 的空间来存储）
2. 在每个分区中找到最小的元素（需要 O(N) 的时间和 O(k log N) 的空间来存储最小元素）
3. 返回你所拥有的 k 个元素中的最大值（需要 O(k) 的时间）

由于算法中还有改进的空间，因此可能还有更好的方法。另外，请注意这种方法在排好序的数组上的性能非常差...

- jswolf19