0

I am struggling with my homework and need a little push- the question is to design an algorithm that will in O(nlogm) time find multiple smallest elements 1<k1<k2<...<kn and you have m *k. I know that a simple selection algorithm takes o(n) time to find the kth element, but how do you reduce the m in your recurrence? I though to do both k1 and kn in each run, but that will only take out 2, not m/2.

Would appreciate some directions. Thanks

4

1 回答 1

2

如果我正确理解了这个问题，您有一个包含 m 个索引的向量 K，并且您想为 K 中的每个 k 找到 A 的第 k 个排名元素。如果 K 包含最小的 m 个索引（即 k=1,2， ...,m) 那么这可以通过使用快速选择找到元素 k_m 在线性时间 T=O(n) 内轻松完成（因为所有较小的元素将在快速选择结束时位于左侧）。所以我假设 K 可以包含任何一组 m 索引。

实现此目的的一种方法是同时对所有 K 运行快速选择。这是算法

QuickselectMulti(A,K)
If K is empty, then return an empty result set
Pick a pivot p from A at random
Partition A into sets A0<p and A1>p.
i = A0.size + 1
if K contains i, then remove i from K and add (i=>p) to the result set.
Partition K into sets K0<i and K1>i
add QuickselectMulti(A0,K0) to the result set
subtract i from each k in K1  
call QuickselectMulti(A1,K1), add i to each index of the output, and add this to the result set
return the result set

如果 K 只包含一个元素，这与随机快速选择相同。要了解为什么平均运行时间为 O(n log m)，首先考虑当每个枢轴将 A 和 K 都精确地一分为二时会发生什么。在这种情况下，你得到两个递归调用，所以你有

T = n + 2T(n/2,m/2)
  = n + n + 4T(n/4,m/4)
  = n + n + n + 8T(n/8,m/8)

由于 m 每次下降一半，那么将在此求和中n显示次数。log m要实际推导出预期的运行时间需要更多的工作，因为您不能假设枢轴会将两个数组分成两半，但是如果您通过计算工作，您会发现运行时间实际上是 O(n log m) 的平均值。

编辑时：该算法的分析可以通过运行 p=Quickselect(A,k_i) 来选择枢轴来简化此过程，其中 k_i 是 K 的中间元素，而不是随机选择 p。这将保证 K 每次都被分成两半，因此递归调用的数量将恰好是 log m，并且由于 quickselect 在线性时间内运行，结果仍然是 O(n log m)。

于 2013-10-09T12:03:35.833 回答