烟台做网站优化哪家好,用wordpress仿一个网站,深度科技有限公司,大连市建设市场综合管理平台对于快速排序和快速选择我之前的文章已经有详细的说明#xff0c;需要了解的同学可以移步
传送门#xff1a;快速排序#xff5c;快速选择(BFPTR)
所谓随机化其实就是选择枢纽的时候使用随机数选择而已#xff0c;实现起来很简单。但是我们使用随机数如何保证复杂度呢需要了解的同学可以移步
传送门快速排序快速选择(BFPTR)
所谓随机化其实就是选择枢纽的时候使用随机数选择而已实现起来很简单。但是我们使用随机数如何保证复杂度呢
首先我们假定随机数的确是随机的即我们选取任何一个元素作为枢纽都是有可能的。
我们使用指示器随机变量xix_ixi如果选择第iii个元素作为枢纽则xi1x_i1xi1否则等于0。如果还不了解什么是指示器随机变量可以看一下这篇文章觉得讲的很好传送门
简单来讲利用期望的线性性质巧妙利用指示器随机变量可以将一个复杂的问题分解为许多容易处理的简单的问题。而且它有一个很好的性质就是他的期望就是他的概率。
因为是随机算法所以我们求解的是复杂度的期望。
随机快速排序
由快速排序算法我们可以得到递归式为 E(T(n))E∑i1nxi(T(i−1)T(n−i)Θ(n))E(T(n))E\sum_{i1}^n{x_i(T(i-1)T(n-i)\Theta(n))} E(T(n))Ei1∑nxi(T(i−1)T(n−i)Θ(n)) 由期望的线性性质 E(T(n))∑i1nE(xi(T(i−1)T(n−i)Θ(n)))E(T(n))\sum_{i1}^nE({x_i(T(i-1)T(n-i)\Theta(n)))} E(T(n))i1∑nE(xi(T(i−1)T(n−i)Θ(n))) 对于一个确定的xix_ixi就确定了当前的划分但是对于进一步的递归和xix_ixi没有关系因此两者是独立的由期望的独立性性质 E(T(n))∑i1nE(xi)∗E((T(i−1)T(n−i)Θ(n)))E(T(n))\sum_{i1}^nE(x_i)*E((T(i-1)T(n-i)\Theta(n))) E(T(n))i1∑nE(xi)∗E((T(i−1)T(n−i)Θ(n))) 因为我们假定是完全随机的所以E(xi)1nE(x_i)\frac{1}{n}E(xi)n1是一个常量然后再根据期望的线性性质 E(T(n))E(xi)∗(∑i1nE(T(i−1))∑i1nE(T(n−i))∑i1nΘ(n))E(T(n))E(x_i)*(\sum_{i1}^nE(T(i-1))\sum_{i1}^nE(T(n-i))\sum_{i1}^n\Theta(n)) E(T(n))E(xi)∗(i1∑nE(T(i−1))i1∑nE(T(n−i))i1∑nΘ(n)) 仔细观察发现两个求和式是一样的因此我们可以合并 E(T(n))2n∗∑i0n−1E(T(i))Θ(n)E(T(n))\frac{2}{n}*\sum_{i0}^{n-1}E(T(i))\Theta(n) E(T(n))n2∗i0∑n−1E(T(i))Θ(n) 我们预期的时间复杂度为O(nlogn)O(nlogn)O(nlogn)因此我们用代入法证明
我们假设E(T(n))cnlognE(T(n))cnlognE(T(n))cnlogn
因为当i0和i1的时候复杂度都是常数所以我们将他们从式子中移去加入常数项这样才可以将log带入
E(T(n))2cn∗∑i2n−1ilogiΘ(n)E(T(n))\frac{2c}{n}*\sum_{i2}^{n-1}ilogi\Theta(n) E(T(n))n2c∗i2∑n−1ilogiΘ(n)
因为我们想要证明的是E(T(n))anlognE(T(n))anlognE(T(n))anlogn我们需要想办法消去后面的Θ(n)\Theta(n)Θ(n)所以我们必须在求和式上动些手脚。
下面证明 ∑i2n−1ilogi12n2logn−18n2\sum_{i2}^{n-1}ilogi\frac{1}{2}n^2logn-\frac{1}{8}n^2 i2∑n−1ilogi21n2logn−81n2
算法导论中这里提示说可以将式子分成两半 可是愚昧的我并没有想到怎么计算哪位大佬知道烦请告知。但是我尝试了一下积分发现了一个更加紧凑的上界。
我们可以将式子变成 ∑k2n−1klogk∫2n−1klogkdk\sum_{k2}^{n-1}klogk\int_{2}^{n-1}klogk\,{\rm d}k k2∑n−1klogk∫2n−1klogkdk 然后我掏出了多年没有用过的高数课本对这个式子积分然后会得到 ∑k2n−1klogk12n2logn−14ln2n2\sum_{k2}^{n-1}klogk\frac{1}{2}n^2logn-\frac{1}{4ln2}n^2 k2∑n−1klogk21n2logn−4ln21n2 而这个式子是比上面小的所以算是证明了吧。。。
然后将式子带入得到 E(T(n))cnlognΘ(n)−cn4E(T(n))cnlogn\Theta(n)-\frac{cn}{4} E(T(n))cnlognΘ(n)−4cn 对于足够大的ccc后面的为负即 E(T(n))cnlognE(T(n))cnlogn E(T(n))cnlogn 对于基本情况如果ccc足够大上式也满足证毕。
随机快速选择
这个复杂度的证明和上面的类似而且比上面的简答。
由快速选择算法有递归式 E(T(n))E∑i1nxi(T(max(i−1,n−i))Θ(n))E(T(n))E\sum_{i1}^n{x_i(T(max(i-1,n-i))\Theta(n))} E(T(n))Ei1∑nxi(T(max(i−1,n−i))Θ(n)) 之所以有maxmaxmax是因为我们求取的是上界所以我们总选取大区间
然后我们同上进行化简 E(T(n))∑i1nE(xi(T(max(i−1,n−i))Θ(n)))E(T(n))\sum_{i1}^nE({x_i(T(max(i-1,n-i))\Theta(n)))} E(T(n))i1∑nE(xi(T(max(i−1,n−i))Θ(n))) E(T(n))∑i1nE(xi)∗E((T(max(i−1,n−i))Θ(n)))E(T(n))\sum_{i1}^nE(x_i)*E((T(max(i-1,n-i))\Theta(n))) E(T(n))i1∑nE(xi)∗E((T(max(i−1,n−i))Θ(n))) E(T(n))1n∑i1nE(T(max(i−1,n−i)))Θ(n)E(T(n))\frac{1}{n}\sum_{i1}^nE(T(max(i-1,n-i)))\Theta(n) E(T(n))n1i1∑nE(T(max(i−1,n−i)))Θ(n) 然后我们去掉maxmaxmax即从┌n/2┐\ulcorner n/2 \urcorner┌n/2┐到nnn计算两边。 E(T(n))2n∑i┌n/2┐nE(T(i))Θ(n)E(T(n))\frac{2}{n}\sum_{i\ulcorner n/2 \urcorner}^nE(T(i))\Theta(n) E(T(n))n2i┌n/2┐∑nE(T(i))Θ(n)
我们假设复杂度为O(n)O(n)O(n)即E(T(k))ckE(T(k))ckE(T(k))ck再带入 E(T(n))2n∑i┌n/2┐nciΘ(n)E(T(n))\frac{2}{n}\sum_{i\ulcorner n/2 \urcorner}^nci\Theta(n) E(T(n))n2i┌n/2┐∑nciΘ(n) 求和式是一个简单的等差数列因此 E(T(n))3c4nΘ(n)cnE(T(n))\frac{3c}{4}n\Theta(n)cn E(T(n))43cnΘ(n)cn 当ccc足够大的时候上式成立。 对于基本情况当ccc足够大的时候成立证毕。
测试
既然复杂度差不多那么是否随机化的性能差别大吗怀着这个疑问我自己手动进行了测试。
快速排序
数据规模1e51e61e7三者取中0.0202470.2325562.641669随机化0.1318581.344317ten thousand yearslater
可以看出快速选择排序我们使用三者取中的方法是比随机化快很多的。
快速选择
1e51e61e7模拟随机化0.0056810.0587960.560251随机化0.0013480.0164570.159499BFPTR0.0141200.1470331.438184
可以看出当我们进行快速选择的时候随机化的选择枢纽是最快的。也验证了我在专门介绍BFPTR算法的文章中的分析。
测试代码
因为快速排序算法的测试代码我在专门介绍快速排序的时候已经写过了这里就不再贴了如果需要的话加单修改一下就可以。这里贴一下快速选择算法的测试代码
#include iostream
#include ctime
#include cstdio
#include fstream
#include cstdlibusing namespace std;typedef double T;
typedef int (*FP)(T*,int,int,int); //定义函数指针数组类型void CreatData()
{int n10;FILE* filefopen(TestFile,w);fprintf(file,%d\n,n);int t;srand(t);for(int i0;in;i){trand();fprintf(file,%d ,rand()%10);}fclose(file);return ;
}T* CreatList(int n)
{//printf(n);//CreatData();ifstream in(TestFile);in n;T* ret new T[n];for(int i0;in;i){inret[i];}in.close();return ret;
}void Init(T* a,int l,int r)
{srand((int)time(NULL));int idx rand()%(l-r)l;swap(a[idx],a[l]);return;
}void InsertSort(T* a,int l,int r)
{//插入排序int mid(lr)1; //获得中位数就足够了for(int il1;imid;i){T xa[i]; int ji-1;while(jl a[j]x){a[j1]a[j]; --j;}a[j1]x;}
}void InsertSort1(T* a,int l,int r)
{//插入排序for(int il1;ir;i){T xa[i]; int ji-1;while(jl a[j]x){a[j1]a[j]; --j;}a[j1]x;}
}void GetPovit1(T* a,int l,int r)
{int x; //将区间分割为[x,x5)int cnt0; //有多少个中位数for(xl; x5r; x5){InsertSort1(a,x,x5);swap(a[lcnt],a[x2]); //将当前区间的中位数放在最前面cnt;}if(xr){InsertSort1(a,x,r);swap(a[lcnt],a[(xr)1]);cnt;}if(1 cnt) return;GetPovit1(a,l,lcnt);
}int BFPTR1(T* a,int l,int r,int k)
{if(r-l 1) return l; //返回找到的数字GetPovit1(a,l,r); //五个一组递归求取中位数T povita[l];int il-1,jr;while(ij){do i; while(a[i]povit);do --j; while(a[j]povit);if(ij) swap(a[i],a[j]);}if(j-l1k) return BFPTR1(a,l,j1,k);else return BFPTR1(a,j1,r,k-jl-1);
}int BFPTR2(T* a,int l,int r,int k)
{if(r-l 1) return l; //返回找到的数字Init(a,l,r);T povita[l];int il,jr;while(ij){do i; while(i1 r a[i]povit);do --j; while(a[j]povit);if(ij) swap(a[i],a[j]);}swap(a[l],a[j]);int numj-l1; //povit在当前序列中排第几if(k num) return j;else if(num k) return BFPTR2(a,l,j,k);else return BFPTR2(a,j1,r,k-num);
}int BFPTR3(T* a,int l,int r,int k);T GetPovit(T* a,int l,int r)
{int x; //将区间分割为[x,x5)int cnt0; //有多少个中位数for(xl; x5r; x5){InsertSort(a,x,x5);swap(a[lcnt],a[x2]); //将当前区间的中位数放在最前面cnt;}if(xr){InsertSort(a,x,r);swap(a[lcnt],a[(xr)1]);cnt;}if(1 cnt) return l;return BFPTR3(a,l,lcnt,cnt/2);
}int BFPTR3(T* a,int l,int r,int k)
{if(r-l 1) return l; //返回找到的数字//五个一组递归求取中位数int idx GetPovit(a,l,r);T povit a[idx];swap(a[l],a[idx]);int il,jr;while(ij){do i; while(i1 r a[i]povit);do --j; while(a[j]povit);if(ij) swap(a[i],a[j]);}swap(a[l],a[j]);int numj-l1; //povit在当前序列中排第几if(k num) return j;else if(num k) return BFPTR3(a,l,j,k);else return BFPTR3(a,j1,r,k-num);
}void Show(T* a,int n)
{for(int i0;in;i){couta[i] ;}coutendl;
}void Test(FP fp[])
{for(int i0;i3;i){clock_t S,E;int Time 10;double sum0;for(int j0;jTime;j){int n;T* aCreatList(n);Sclock();int xfp[i](a,0,n,9);//0 0 1 4 4 4 6 6 8 9Eclock();//coutx:a[x] ;sum(double)(E-S)/CLOCKS_PER_SEC;//cout经过排序之后:endl;//Show(a,n);delete[] a;}coutendl;printf(BFPTR%ds times%f\n,i1,sum/Time);}
}int main()
{FP fp[3] {BFPTR1,BFPTR2,BFPTR3};Test(fp);return 0;
}
