已知有向图G=(V,E),其中...
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
浙ICP备号-2
扫一扫，把题目装进口袋请问，归并排序在平均情况下的时间复杂度为什么是O(nlgn)？
[问题点数：20分]
请问，归并排序在平均情况下的时间复杂度为什么是O(nlgn)？
[问题点数：20分]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2013年5月 高性能开发大版内专家分月排行榜第二2013年4月 高性能开发大版内专家分月排行榜第二
2013年5月 高性能开发大版内专家分月排行榜第二2013年4月 高性能开发大版内专家分月排行榜第二
2013年5月 高性能开发大版内专家分月排行榜第二2013年4月 高性能开发大版内专家分月排行榜第二
本帖子已过去太久远了，不再提供回复功能。&1&//&cycly&moving&left&middle&-&first&vacancies&2&template&typename&RandomIterator&&3&void&rotate(RandomIterator&first,&RandomIterator&middle,&RandomIterator&last)&4&{&5&&if(first&==&middle&||&last&&==&middle)&return;&6&&&reverse(first,&&middle);&7&&reverse(middle,&last);&8&&&while(first&!=&middle&&&&middle&!=&last)&9&&{10&&&&swap(*first,&*--last);11&&&&++12&&}13&&if(first&==&middle)14&&&&reverse(middle,&last);15&&else16&&&&reverse(first,&middle);17&}18&19&//&find&the&lower&bound,&the&returned&value&is&the&address&of&that&bound20&template&&typename&RandomIterator,&typename&T,&typename&Compare&21&RandomIterator&lower_bound(RandomIterator&first,&RandomIterator&last,22&&&&&&&&&&&&&&&&&&&&&&&&&&&&&const&T&&value,&Compare&cmp)23&{24&&&int&len&=&last&-&first,&25&&&RandomIterator&26&&&while(len&&&0)27&&&{28&&&&&half&=&len&&&&1;29&&&&&middle&=&first&+&30&&&&&if(cmp(*middle,&value))31&&&&&{32&&&&&&&first&=&33&&&&&&&++34&&&&&&&len&=&len&-&half&-&1;35&&&&&}36&&&&&else37&&&&&&&len&=&38&&&}39&&&return&40&}41&42&//&find&the&upper&bound,&the&returned&value&is&the&address&of&that&bound43&template&&typename&RandomIterator,&typename&T,&typename&Compare&44&RandomIterator&upper_bound(RandomIterator&first,&RandomIterator&last,45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&const&T&&value,&Compare&cmp)46&{47&&&int&len&=&last&-&first,&48&&&RandomIterator&49&50&&&while(len&&&0)51&&&{52&&&&&half&=&len&&&&1;53&&&&&middle&=&first&+&54&&&&&if(cmp(value,&*middle))55&&&&&&&len&=&56&&&&&else57&&&&&{58&&&&&&&first&=&59&&&&&&&++60&&&&&&&len&=&len&-&half&-&1;61&&&&&}62&&&}63&&&return&64&}&1&//&no&heap&memory&needed&to&merge&two&sequence&2&template&&typename&RandomIterator,&typename&Compare&&3&void&merge_without_buffer(RandomIterator&first,&RandomIterator&middle,&4&&&&&&&&&&&&&&&&&&&&&&&&&&&RandomIterator&last,&int&len1,&int&len2,&Compare&cmp)&5&{&6&&&if(0&==&len1&||&0&==&len2)&return;&7&&&if(2&==&len1&+&len2)&8&&&{&9&&&&&if(cmp(*middle,&*first))&swap(*first,&*middle);10&&&&&return;11&&&}12&&&RandomIterator&first_cut&=&first,&second_cut&=&13&&&int&len11&=&0,&len22&=&0;14&&&if(len1&&&len2)15&&&{16&&&&&len11&=&len1&&&&1;17&&&&&first_cut&+=&len11;18&&&&&second_cut&=&lower_bound(middle,&last,&*first_cut,&cmp);19&&&&&len22&=&second_cut&-&20&&&}21&&&else22&&&{23&&&&&len22&=&len2&&&&1;24&&&&&second_cut&+=&len22;25&&&&&first_cut&=&upper_bound(first,&middle,&*second_cut,&cmp);26&&&&&len11&=&first_cut&-&27&&&}28&&&rotate(first_cut,&middle,&second_cut);29&&&RandomIterator&new_middle&=&first_cut&+&(second_cut&-&middle);30&&&merge_without_buffer(first,&first_cut,&new_middle,&len11,&len22,&cmp);31&&&merge_without_buffer(new_middle,&second_cut,&last,&len1&-&len11,&len2&-&len22,&cmp);32&}33&34&//&inplace&merge&sort35&template&&typename&RandomIterator,&typename&Compare&36&void&inplace_merge_sort(RandomIterator&first,&RandomIterator&last,&Compare&cmp)37&{38&&&if(last&-&first&&&17)39&&&{40&&&&&insertion_sort(first,&last,&cmp);41&&&&&return;42&&&}43&&&RandomIterator&middle&=&first&+&((last&-&first)&&&&1);44&&&inplace_merge_sort(first,&middle,&cmp);45&&&inplace_merge_sort(middle,&last,&cmp);46&&&merge_without_buffer(first,&middle,&last,&middle&-&first,&last&-&middle,&cmp);47&}以上代码实现中用到了直接插入排序，该部分内容见本主页的快排介绍。
随笔分类(106)
随笔档案(68)
部分开源操作系统
部分免费工具软件
主页或博客
评论排行榜将两个长度为n的有序表归并为一有序表时,算法的时间复杂度是_百度知道查看: 25288|回复: 10
为什么快速排序空间复杂度为o（log2n）
主题帖子积分
考研年份2012
报考学校华南理工大学
本科学校广东工业大学
书本上说要用深o（log2n）的栈实现递归，但是归并排序同样有递归啊，为什么归并只需o（n）的空间复杂度？
这里我看得不很懂，严奶奶的视频里也没有讲解到这个部分，请大家指点一下，多谢
主题帖子积分
考研年份2011
报考学校浙江大学
本科学校南昌大学
归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O（n）。
快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。
Never stop!
主题帖子积分
考研年份2012
报考学校华南理工大学
本科学校广东工业大学
zhengxiang3014
& & 关于归并排序的空间复杂度，还是不是很了解...归并排序在层层递归的时候，分到最底层，不也是需要O(log2n)深的栈空间来实现递归吗？而每层需要o（n）个空间，这样不是应该o（nlog2n）的空间复杂度吗....
原谅我的纠缠不休，因为这里我真的不懂....
主题帖子积分
考研年份2011
报考学校浙江大学
本科学校南昌大学
呵呵&&这里本来就应该是学习交流的平台的。
你可以这样看：栈空间是全局的，而辅助空间是局部的，每次用完就释放掉了。不能简单的相乘。。。
Never stop!
主题帖子积分
考研年份2012
报考学校华南理工大学
本科学校广东工业大学
zhengxiang3014
你能就这个图给我讲解下吗？
递归的栈深为O（log2n），除此外还有一个O（n）的辅助空间，在图中看出的确是释放掉了一层栈，但我还是不知道是怎么算出空间复杂度为O（n）的...
希望你能就这个图给我讲解下，不好意思我脑筋不太好用....在这里纠结了好久....多谢你了....
本帖子中包含更多资源
才可以下载或查看，没有帐号？
主题帖子积分
考研年份2012
报考学校华南理工大学
本科学校广东工业大学
为什么空间复杂度不用算上栈？
主题帖子积分
考研年份2011
报考学校浙江大学
本科学校南昌大学
古巢二飞曹
& & 并不是说不考虑栈空间，而是你可以认为空间上界不会超过O(n+log2n)，从而还是O（n）
Never stop!
主题帖子积分
王道论坛初级道友, 积分 65, 距离下一级还需 135 积分
王道论坛初级道友, 积分 65, 距离下一级还需 135 积分
考研年份2012
报考学校北京科技大学
本科学校北京科技大学
古巢二飞曹
& & 楼主。。。实在不清楚的话。。。你可以试着把你上的图里的这个归并过程进行下去。。。
& & 看看每一步递归栈的长度和辅助空间中元素所占的长度加起来看会不会超过n。。。然后看
& & 清每一步的过程中递归栈长度和辅助空间中元素所占长度的变化，然后慢慢来理解。。
主题帖子积分
王道论坛初级道友, 积分 118, 距离下一级还需 82 积分
王道论坛初级道友, 积分 118, 距离下一级还需 82 积分
考研年份2010
报考学校山东大学
本科学校曲阜师范大学
楼主，归并排序可以不用递归，只用循环就完成。
第一趟设归并长度为1，两两归并；第二趟归并长度为2，……；最后一趟递归为n/2即可。
这里其实还涉及一个问题就是并不是所有的递归算法转非递归的时候都要使用栈的。像递归排序这种没有返回值的程序在转非递归时就不需要使用栈；而快速排序每次递归都会返回一个中间值的位置，必须使用栈。所以空间复杂度就是栈用的空间。
主题帖子积分
考研年份2008
报考学校Nil
本科学校Nil
楼主把递归的树状图画出来吧。或者找本讲了递归的书看看。
第4期王道安卓方向已开放报名（5月中旬开班）。
报名地址：
第13期王道C/C++方向开放报名（3月初开班）。
报名地址：
主题帖子积分
王道论坛实习道友, 积分 1, 距离下一级还需 19 积分
王道论坛实习道友, 积分 1, 距离下一级还需 19 积分
本科学校天津理工
快排的递归需要返回值吗？& & /7984670
《指导全书》辅导员}