Tanky Woo >> 随机化算法(3) -- 舍伍德(Sherwood)算法

Tanky Woo » 随机化算法(3) — 舍伍德(Sherwood)算法
在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度。这时可用舍伍德算法消除算法所需计算时间与输入实例间的这种联系。

联系例子，在快速排序中，我们是以第一个元素为基准开始排序时，为了避免这样的情况，可以用舍伍德算法解决，也就是使第一个基准元素是随机的。

// 交换a, b的值
template <typename Type>
void Swap(Type &a, Type &b)
{
 Type temp;
 temp = a;
 a = b;
 b = temp;
}
 
template <typename Type>
Type select(Type a[], int lt, int rt, int k)
{
 // 计算a[lt:rt]中第k小元素
 static RandomNumber rnd;
 while(true)
 {
  if(lt > rt)
   return a[lt];
  int i = lt, j = lt+rnd.Random(rt-lt+1);   // 随机选择的划分基准
  Swap(a[i], a[j]);
  j = rt+1;
  Type pivot = a[lt];
  //以划分基准为轴作元素交换
  while(true)
  {
   while(a[++i] < pivot);
   while(a[--j] > pivot);
   if(i >= j)
    break;
   Swap(a[i], a[j]);
  }
  if(j - lt + 1 == k)
   return pivot;
  a[lt] = a[j];
  a[j] = pivot;
  // 对子数组重复划分过程
  if(j - lt + 1 < k)
   {
    k = k - j + lt - 1;
    lt = j + 1;
   }
  else
   rt = j - 1;
 }
}
 
template <typename Type>
Type Select(Type a[], int n, int k)
{
 // 计算a[0: n-1]中第k小元素
 // 假设a[n]是一个键值无穷大的元素
 if(k < 1 || k > n)
  cerr << "Wrong!" << endl;
 return select(a, 0, n-1, k);
}

当然，舍伍德算法也不是万能的。有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。
Read full article from Tanky Woo » 随机化算法(3) — 舍伍德(Sherwood)算法