主题：时间复杂度问题，挺郁闷的～
便签
[专家分：40] 发布于 2006-05-10 22:58:00
是有关并归排序的，由于有好几个递归，不知道怎么求了
void mergesort(int i,int j)
{
int m;
if(i!=j)
{
m=(i+j)/2;
mergesort(i,m);//这两句挺烦的，不知道如何解决，主要是有两个递归，一个的话能解
mergesort(m+1,j);//决.
merge(i,j,m);
}
}
回复列表 （共4个回复）
沙发
hanshuyujifen [专家分：800] 发布于 2006-05-11 01:58:00
merge(i,j,m)是什么?
将数分成两部分
mergesort(i,m);//先弄前一半
mergesort(m+1,j);//再弄后一半
没什么难理解的呀?
主要操作应该是交换什么吧!!
初学!!有不对的地方,清指正!!
板凳
便签 [专家分：40] 发布于 2006-05-11 11:10:00
呵呵，也是初学，归并的算法理解，就是时间复杂度，不知怎么求。
3 楼
boxertony [专家分：23030] 发布于 2006-05-11 11:14:00
主要还得看你的 merge函数的实现，
"mergesort(i,m);//这两句挺烦的，不知道如何解决，主要是有两个递归，一个的话能解" 根本不用你管，因为是递归的呀
假设merge的时间复杂度是g(n)，mergesort的是f(n)，则
f(n) = 2f(n/2) + g(n)
然后根据这个递推公式求出通项公式就可以了呀。
既然是归并排序，肯定g(n)＝n
所以f(n)=2f(n/2)+n = 2[2f(n/4)+n/2] + n
= 4f(n/4) + 2n = 2^k*f(n/2^k) + k*n
如果k=log2(n)
则f(n) = n*f(1) + n*log2(n)
4 楼
便签 [专家分：40] 发布于 2006-05-11 11:18:00
谢谢楼上朋友，正解啊！！！
我来回复
您所在位置：