注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

hhfighting的博客

以责人之心责己,以恕己之心恕人

 
 
 

日志

 
 
 
 

归并排序的算法时间复杂度  

2014-07-20 03:03:32|  分类: C & C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
昨天看了MIT算法导论视频的第一节,第一次了解到了如何计算归并排序的算法时间复杂度。记得在大学时数据结构课程上学习了各种算法,老师也提到了该算法的时间复杂度,当时只是记住了,应付了考试,根本不知道是如何得来的。对自己对追求知识的态度,深表惭愧。不废话了,记录一下学习心得。
先记录一下学习到的一些英语表述:
merge sort--- 归并排序   asymptotic---渐进的   recurrence---递归
归并排序的思想是将两个有序的序列合并为一个有序序列。其时间复杂度是o(nlogn),计算是通过绘制递归函数的递归树得来的。注:时间复杂度用o(*)表示是一个weak notation,忽略了一些常数项。
 首先看时间复杂度的计算公式:
归并排序及其时间复杂度分析 - 珑儿 - 顾影自怜
如果仅一个数,那当然是1了。merge sort的递归过程是不断对序列进行二分,直到只剩一个数,也就是上述的2T(n/2),上述的o(n)是将两个有序序列合并成一个有序序列对应的asymptotic时间复杂度。用递归树描述整个过程为:
归并排序及其时间复杂度分析 - 珑儿 - 顾影自怜
上图中用cn表示o(n),这是基于asymptotic的概念(和n相比,忽略了常数c)。对一个具有n个元素的序列进行二分(n/2m=1,m=log2n),树的深度为log2n,得到total=cnlog2n+cn,因此算法的asymptotic时间复杂度为o(nlog2n).
但是所有的参考资料中均把时间复杂度记为o(nlog2n)。上网google到一篇博文“http://blog.codinglabs.org/articles/why-logarithm-base-of-asymptotic-time-complexity-always-two.html”提到了三分式归并排序的时间复杂度,计算过程显示其算法复杂度为o(nlog3n),博主提到nlog3n和nlog2n仅相差了一个常数,在asymptotic分析的观点上,o(nlog3n)和o(nlog2n)应该是等同。这也许是归并排序的asymptotic时间复杂度时用o(nlogn)的原因的一个解释。个人理解具体是否关注底数是几,或者是否重要,要看当时的比较对象是谁。如果拿归并排序和选择排序进行比较的话,选择排序的时间复杂度是o(n*n),因此只需留意归并排序的时间复杂度是o(nlogn)就足够得出结论:在时间复杂度上归并排序要优于选择排序。但如果是比较二分和三分归并排序的时间复杂度,我个人认为底数还是重要的,不可以忽略的。
  评论这张
 
阅读(714)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017