中国品牌设计公司,湘潭关键词优化服务,长沙百度文化传播有限公司,个人优秀网站BFPTR算法是由Blum、Floyed、Pratt、Tarjan、Rivest这五位牛人一起提出来的#xff0c;其特点在于可以以最坏复杂度为O(n)O(n)O(n)地求解top−ktop-ktop−k问题。所谓top−ktop-ktop−k问题就是从一个序列中求解其第k大的问题。 top−ktop-ktop−k问题有许多解决方法#xff…BFPTR算法是由Blum、Floyed、Pratt、Tarjan、Rivest这五位牛人一起提出来的其特点在于可以以最坏复杂度为O(n)O(n)O(n)地求解top−ktop-ktop−k问题。所谓top−ktop-ktop−k问题就是从一个序列中求解其第k大的问题。
top−ktop-ktop−k问题有许多解决方法其他解决方法总结可以看我之前的一篇博客传送门
这个算法的介绍更详细的可以参照算法导论9.3节 Selection in worst-case linear time这里记录一下我对这个算法的理解、实现以及复杂度的证明。
下面详细的介绍一下BFPTR算法
算法思想
宏观来看BFPTR算法是快速排序思想的一种应用 每次我们找到枢纽元素然后按照枢纽元素将数组划分为两部分就可以得到左边x个元素都是比枢纽元素小的右边y个元素都是比枢纽元素大的 然后根据我们想要查找的k决定到哪边进行递归查找 假设我们想要查找第k小如果xy则枢纽元素就是需要查找的元素如果xk则到左边继续查找如果xk则去右边的区间查找第k-x个元素
典型的分治思想。问题的关键在于如何查找枢纽以及如何划分如果这两步做的不够好那么将会导致子问题的规模不能够很快的缩小从而使复杂度退化为O(n2)O(n^2)O(n2)
关于如何划分主要就是快速排序的划分思想我在另一篇博客中已经详细介绍了各种划分方法的优劣如果有兴趣可以移步传送门。
而BFPTR算法的精髓就在于如何选择枢纽以保证复杂度不会退化。
选择枢纽
将数组五个五个划分为┌n/5┐\ulcorner n/5 \urcorner┌n/5┐个小块求出每个块的中位数递归求出这些中位数的中位数将这个数当做枢纽如何做到这点呢我们BFPTR不就是求第k大吗我们递归地调用BFPTR就可以了。
我在网上仔细研究了其他人实现BFPTR的代码个人觉得他们的代码并没有按照算法原本的思想操作如果我理解的有问题欢迎大家批评指正,他们的做法都是将第一步划分的中位数再递归地划分为五个块求取中位数直到最后不足五个元素直接返回中位数作为枢纽。代码如下
void 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;GetPovit(a,l,lcnt);
}虽然这样仍然可以解决问题但是我觉得这样并不是BFPTR算法的思想我们可以参见算法导论中对这一步骤的描述 其中第三步中的递归地选择这些中位数中的中位数这显然不是再将其划分为五个五个的小块求取中位数。因为我们再将其划分为五个五个的小块是不能保证最后选出来的是中位数的如果这样可行的话就会有一种求中位数的方法是这样分块递归了但是现实是我们现在做的正是这个算法。所以我认为他们的做法是不对的可行的原因也只是这是类似于一种随机选取枢纽的操作。同样佐证这一点的是后面对于复杂度的分析如果使用上面网上的做法那么是无法进行复杂度分析的。
我自己的做法是对于选出来的中位数调用BFPTR算法得到中位数。
实现代码
首先是主体部分
int BFPTR(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 BFPTR(a,l,j,k);else return BFPTR(a,j1,r,k-num);
}这里的划分方法有一点点不同于我快速排序文章中的方法主要是这里我将枢纽放在了中间因为这样我们有可能直接返回枢纽而不必一定要将区间划分为1才返回。我认为可以一定程度上降低复杂度。 这里我返回的是需要查找的数在数组中的位置觉得位置包含了更多的信息我们知道位置以后可以直接得到查询的数字可是返回查询的数字无法直接得到位置。
下面是最重要的获取枢纽的操作
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;}
}int BFPTR(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 BFPTR(a,l,lcnt,cnt/2);
}
其中上面是一个简单的插入排序下面是将数组划分为五个五个的小段求取中位数以后放在数组的前面然后再调用BFPTR函数得到中位数的中位数。之所以放在数组前面是因为这样可以原地操作而不用占用其他的空间。
完整的测试代码会附在最后也会附上网上大家的代码供大家测试。
复杂度分析
对于一个规模为n的输入其最坏的时间复杂度为T(n)T(n5)Θ(n)T(7n10)Θ(n)T(n)T(\frac{n}{5})\Theta(n)T(\frac{7n}{10})\Theta(n)T(n)T(5n)Θ(n)T(107n)Θ(n)
其中T(n5)Θ(n)T(\frac{n}{5})\Theta(n)T(5n)Θ(n)为求解其中位数的中位数的复杂度。我们首先将其划分为┌n/5┐\ulcorner n/5 \urcorner┌n/5┐个小块然后求解每个小块的中位数是常数操作因此总共是Θ(n)\Theta(n)Θ(n)前面的T(n5)T(\frac{n}{5})T(5n)是BFPTR递归求解中位数的复杂度
最后的Θ(n)\Theta(n)Θ(n)是划分的复杂度
比较难理解的是为什么是T(7n10)T(\frac{7n}{10})T(107n)。我们可以先看一张图算法导论上盗下来的 这里的箭头表示的含义是箭屁股的元素小于箭脑袋的元素。那么白元素的含义就很明显啦即就是每个五个元素小块里面的中位数其中的x表示中位数中的中位数。
由箭头关系我们不难看出右下方的灰色区域的元素全部小于x同理左上方区域的元素全部大于x那么我们以x为枢纽元素将数组划分以后数组的两边至少都有这些元素。这些元素最少有多少呢
白色区域大体和灰色区域的个数相等因此我们计算灰色区域的个数。总共有┌n/5┐\ulcorner n/5 \urcorner┌n/5┐列因为我们求取的是最小有多少因此我们取下界└n/5┘\llcorner n/5 \lrcorner└n/5┘灰色区域占到其中的一半每一列有三个元素因此总共有3∗┌└n/5┘/2┐3*\ulcorner \llcorner n/5 \lrcorner/2 \urcorner3∗┌└n/5┘/2┐,即最少3n10\frac{3n}{10}103n的元素在一边。
我们考虑最坏的时间复杂度因此另一边最多7n10\frac{7n}{10}107n个元素而我们总落入这一边。因此我们每次划分以后都需要再进行T(7n10)T(\frac{7n}{10})T(107n)的递归。
接下来就是解递归式T(n)T(n5)T(7n10)Θ(n)T(n)T(\frac{n}{5})T(\frac{7n}{10})\Theta(n)T(n)T(5n)T(107n)Θ(n)。 对于这样的递归式我们没有什么好方法只能选择代入法进行证明。假设T(k)ckT(k)ckT(k)ck那么我们需要证明 c∗n5c∗7n10Θ(n)cnc*\frac{n}{5}c*\frac{7n}{10}\Theta(n)cn c∗5nc∗107nΘ(n)cn
即就是 c∗n10Θ(n)c*\frac{n}{10}\Theta(n) c∗10nΘ(n)
对于足够大的ccc,上式成立。 当处于基本情况时对于足够大的ccc上式也成立。
因此BFPTR的复杂度为O(n)O(n)O(n)证毕。
为什么是?
首先我们肯定是要划分成奇数块的偶数块求中位数不好求。 其次最小可以选择的奇数是3但是如果是3的话可以证明其复杂度就不是线性的了T(n)T(n3)Θ(n)T(7n10)Θ(n)T(n)T(\frac{n}{3})\Theta(n)T(\frac{7n}{10})\Theta(n)T(n)T(3n)Θ(n)T(107n)Θ(n) 也可以选择7但是选择7的话常数会更大因此我们选择将数组划分为长度为5的小区间
测试与分析
虽然这个算法的复杂度为O(n)O(n)O(n)的但是我将按自己思路实现的代码和按网上思路实现的代码都对规模为1e81e81e8规模的数据进行了测试发现BFPTR算法不是很快。原因可能是BFPTR算法的常数比较大而网上的思路作为一种模拟的随机性快速选择算法常数比较小。但是我认为如果要使用随机性算法的话直接使用随机数常数会更小。关于随机性快速选择算法和模拟的随机性算法以及BFPTR到底哪一个更快可以看我的另一篇博客传送门
BFPTR算法代码
#include iostream
#include fstream
#include ctimeusing namespace std;typedef double T;T* CreatList(int n)
{ifstream in(TestFile);in n;T* ret new T[n];for(int i0;in;i){inret[i];}in.close();return ret;
}void Show(T* a,int n)
{for(int i0;in;i){couta[i] ;}coutendl;
}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;}
}int BFPTR(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 BFPTR(a,l,lcnt,cnt/2);
}int BFPTR(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 BFPTR(a,l,j,k);else return BFPTR(a,j1,r,k-num);
}void Query(T* a,int n)
{int k;while(true){cout请输入k:;cink;if(cin.fail() true)break;if(kn || k1){//检查输入的有效性cout请输入1~n之间的数字endl;continue;}clock_t S,E;Sclock();int idxBFPTR(a,0,n,k);Eclock();cout区间第k大的数字为:a[idx]endl;cout这次查询花费时间(double)(E-S)/CLOCKS_PER_SECsendl;}cin.clear();cin.ignore();
}int main()
{int n;T* aCreatList(n);Query(a,n);delete[] a;return 0;
}
模拟随机化选择的代码
#include iostream
#include fstream
#include ctimeusing namespace std;typedef double T;T* CreatList(int n)
{ifstream in(TestFile);in n;T* ret new T[n];for(int i0;in;i){inret[i];}in.close();return ret;
}void Show(T* a,int n)
{for(int i0;in;i){couta[i] ;}coutendl;
}void InsertSort(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 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;GetPovit(a,l,lcnt);
}int BFPTR(T* a,int l,int r,int k)
{if(r-l 1) return l; //返回找到的数字GetPovit(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 BFPTR(a,l,j1,k);else return BFPTR(a,j1,r,k-jl-1);
}void Query(T* a,int n)
{int k;while(true){cout请输入k:;cink;if(cin.fail() true)break;if(kn || k1){//检查输入的有效性cout请输入1~n之间的数字endl;continue;}clock_t S,E;Sclock();int idxBFPTR(a,0,n,k);Eclock();cout区间第k大的数字为:a[idx]endl;cout这次查询花费时间(double)(E-S)/CLOCKS_PER_SECsendl;}cin.clear();cin.ignore();
}int main()
{int n;T* aCreatList(n);Query(a,n);delete[] a;return 0;
}
