Randomized_Select这种算法是什么？

Question

我正在学习"Introduction to Algorithms"教科书第 2 版。在第 9 章（中位数和顺序统计）中，我不明白为什么我们在 Randomize_Select 算法中需要这个额外的 k。考虑一下书中算法的伪代码。

RANDOMIZED-SELECT(A, p, r, i)
1   if p = r
2       then return A[p]
3   q ← RANDOMIZED-PARTITION(A, p, r)
4   k ← q - p + 1
5   if i = k    ▹ the pivot value is the answer
6       then return A[q]
7   elseif i < k
8       then return RANDOMIZED-SELECT(A, p, q - 1, i)
9   else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

我的问题是为什么我们需要k？我以这种方式实现了算法并且它有效（对于我测试算法的所有示例）。

RANDOMIZED-SELECT(A, p, r, i)
1   if p = r
2       then return A[p]
3   q ← RANDOMIZED-PARTITION(A, p, r)
4   if i = q    ▹ the pivot value is the answer
5       then return A[q]
6   elseif i < q
7       then return RANDOMIZED-SELECT(A, p, q - 1, i)
8   else return RANDOMIZED-SELECT(A, q + 1, r, i)

由于分区过程中的 q returned 是一个索引，其中包含排序后它应该包含的集合中的元素，如果该索引是我们搜索的内容，我们就 return 它，如果不是，我们在包含该元素的部分上以相同的方式递归。为什么需要k？为什么算法会关心每个子集中元素的顺序？为什么我们不关心索引呢？我的更改是否适用于所有情况？

Answer 1

返回RANDOMIZED-SELECT中i的定义。 i在数组A的p到r开始的函数的传递数组范围内。因此，选定值 q 应该从指定的第一个数组 A 计算得出。因此，我们应该计算与 p.

起始索引相关的 k （传递的数组中的位置）

此外，由于这里的索引是1，所以k应该是q - p + 1。

例如，假设A是一个大小为10的数组，p = 5,r = 8。因此，i 由 1 更改为 3。因此，我们应该映射 5 和 8 之间的 q 应该从 1 缩放到 3；所以，k 与 i 具有相同的比例，而 q 没有！

Randomized_Select这种算法是什么？

Whay is Randomized_Select Algorithm in this way?

algorithm

selection