Sherwood算法（舍伍德算法）

在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度。这时可用舍伍德算法消除算法所需计算时间与输入实例间的这种联系。联系例子，在快速排序中，我们是以第一个元素为基准开始排序时，为了避免这样的情况，可以用舍伍德算法解决，也就是使第一个基准元素是随机的。
当然，舍伍德算法也不是万能的。有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。

image.png

dlogRH(g, a, p) { // 求logg,pa, a = gx mod p，求x
        // Sherwood算法
        r ← uniform(0..p-2);
        b ← ModularExponent(g, r, p); //求幂模b=gr mod p
        c ← ba mod p; //((gr modp)(gxmodp))modp=gr+xmodp=c
        y ← logg,pc; // 使用确定性算法求logp,gc, y=r+x
        return (y-r) mod (p-1); // 求x
    }

1. Log g,p (st mod p) = (log g,p s + log g,p t) mod (p - 1)
2. Log g,p (g ^r mod p) = r, 0 <= r <= p – 2

dlogRH(g, a p) {           // 求 log g,p a, a = g^x mod p,求 x          Sherwood算法
     r ← uniform(0..p-2);
    b ← ModularExponent(g, r, p);    //求幂模 b=g^r mod p,定理 1 真数的一部分
    c ← ba mod p;        //((g^r modp)(g^x modp))modp=g ^(r+x)modp=c, 定理 2 中的真数
    y ← log g,p c;            // 使用确定性算法求 log p,g c, y=r+x,定理 2
    return (y-r)mod(p-1);      //求x,定理1
}

在这里,唯一耗费时间的是 b ← ModularExponent(g, r, p),它的执行时间与a,p 的取值无关,只与随机取出的 r 有关

写一Sherwood算法搜索有序表

#include<iostream>
#include<ctime>
#include<set>
#include<cmath>
using namespace std;

const int N = 15;
int val[N] = { RAND_MAX, 2, 3, 13, 1, 5, 21, 8, 29, 87, 56, 69, 72, 83, 45 }; //N==15
int ptr[N] = { 4, 2, 5, 6, 1, 7, 8, 3, 14, 0, 11, 12, 13, 9, 10 };
int ComCount = 0; //用于Search算法查找需要的次数

//设x≥val[i]且x在表中，则从位置i开始查找x的算法
int Search(int x, int i)
{
    ComCount = 0;
    while (x > val[i])
    {
        i = ptr[i];
        ++ComCount;
    }
    return i;
}
//在表val[1..n]中从最小值开始查找x的算法为：
int A(int x)
{
    return Search(x, ptr[0]);
}



//在val数组的前sqrt(n)个元素中找y<=x的最大整数y，从y开始查找。
//在这里假设了val的元素是均匀分散的
int B(int x)
{
    int i = ptr[0];
    int max = val[i];
    for (int j = 1; j <= (int)sqrt((double)N); ++j)
    {
        int y = val[j];
        if (max < y && y <= x)
        {
            i = j;
            max = y;
        }
    }
    return Search(x, i);
}

//随机选择val数组中的一个数做为开始，随机sqrt(n)次，选取y<=x的最大整数y，从y开始查找，
//此算法比B算法有更好的平均性能
int C(int x)
{
    int i = ptr[0];
    int max = val[i];
    for (int j = 1; j <= (int)sqrt((double)N); ++j)
    {
        int k = rand() % N;
        int y = val[k];
        if (max < y && y <= x)
        {
            i = k;
            max = y;
        }
    }
    return Search(x, i);
}

//随机选一个指针位置(0~n-1)开始查找，本例n=8
int D(int x)
{
    int i = rand() % N; //C++ 从零开始，最后不必加1 
    int y = val[i];
    if (x < y)
    {
        return Search(x, ptr[0]);
    }
    else if (x > y){
        return Search(x, ptr[i]);
    }
    else{
        return i;
    }

}
int main()
{
    int totalA = 0;
    int totalB = 0;
    int totalC = 0;
    int totalD = 0;
    int i = 0;
    //对有序表中的元素逐个进行查找，得出所用的总比较次数。
    int temp(1);
    while (ptr[i] != 0)
    {
        A(val[ptr[i]]);
        totalA += ComCount;
        B(val[ptr[i]]);
        totalB += ComCount;
        C(val[ptr[i]]);
        totalC += ComCount;
        D(val[ptr[i]]);
        totalD += ComCount;
        i = ptr[i];
        temp++;
    }
    cout << "对有序表中的元素逐个进行查找，得出所用的总比较次数。\n遍历的元素表中的个数N=" << temp << endl << endl;
    cout << "算法A比较总次数:" << totalA << endl;
    cout << "算法B比较总次数:" << totalB << endl;
    cout << "算法C比较总次数:" << totalC << endl;
    cout << "算法D比较总次数:" << totalD << endl;
    system("pause");
    return 0;

}

image.png