algorithm - 随机算法模仿

Question

我正在阅读 CLRS，但我被困在问题 5.1-2 上。

描述仅调用 RANDOM(0,1) 的过程 RANDOM(a,b) 的实现。作为 a 和 b?

此处编写的解决方案提供了 O(lg(b-a)) 的复杂度。

http://sites.math.rutgers.edu/~ajl213/CLRS/Ch5.pdf

我也写了一个算法，我需要一些关于它的建议。

Random[a,b]
arr[]={a,....,b}
if(high-low <= 1)
 if(Random[0,1])
  new_arr[high]
  return
 else
  new_arr[low]
  return

if(Random[0,1])
 new_arr[a+b/2,.......,b]
else
 new_arr[a,...........,a+b/2-1]

我的解决方案是基于分而治之的，复杂度也是 O((b-a+1))。

请告诉我我的解决方案是否正确？

Answer 1

当 b-a+1 不是 2 的幂时会出现问题(如果我正确理解您的代码，但其中缺少一些东西)。

例如考虑数组 [1,2,3]。你有 0.5 的概率去 [1] 和 0.5 的概率去 [2,3]。这意味着最后，选择每个数字的概率是:

• 1 : 0.5
• 2 : 0.25
• 3 : 0.25

即使您将数组划分为 [1,2]/[2,3]，概率也不正确，您将拥有

• 1 : 0.25
• 2 : 0.5
• 3 : 0.25