当前位置：首页 → 问答吧 → 【求数学达人解释】用分治法求最大子段和中，复杂度为O(nlogn)是怎么算出来的？？

【求数学达人解释】用分治法求最大子段和中，复杂度为O(nlogn)是怎么算出来的？？

时间：2010-08-25

来源：互联网

RT,在复习算法过程中，讲到用分治法解决最大子段和问题时，说该算法所需的计算时间T（n）满足典型的分治法递归式子：
               O(1)                   n<=c
   T（n）=
                     2T(n/2) +O(n)    n>c


      然后书上就说 T(n)=O(nlogn)，这个是怎么推导出来的呢？？求达人解释下啊啊啊啊啊啊啊啊啊啊啊啊啊啊

(我知道数学符号不容易敲入，如果哪位达人知道上面问题的解释并可以上传图片的话，能否写在纸上并照相并上传上来呢？？？？？？感谢ing~~~~~~~~~~~)

作者: glq2000 发布时间: 2010-08-25

本帖最后由 davelv 于 2010-08-25 17:08 编辑

在线公式编辑器见
http://www.codecogs.com/latex/install.php
可以快速生成图片，而且可以在线引用和根据URL得到公式源码

至于那个计算方法，可以用递归树或主定理的方法去解决，楼主可以google下这两个方法，或者参考《算法导论》的描述

作者: davelv 发布时间: 2010-08-25

算法，算法，可恶的算法

作者: d19890104 发布时间: 2010-08-25

还照相上来给你啊，真是强大，

作者: ecjtubaowp 发布时间: 2010-08-25

如果估计的话，可以这么算：
架设n往大取，n=2^s
那么公式就变成了：
T(2^s)=2T(2^(s-1))+2^s
两边同除2^s：
T(2^s)/(2^s)=T(2^(s-1))/(2^(s-1))+1
设a_s=T(2^s)/(2^s)并假设a_1=1，原式化为：
a_s=a_(s-1)+1
为等差数列，于是a_s=s
于是：
T(2^s)/(2^s)=s
那么T(2^s)=s*2^s
你再把n=2^s带入就是
T(n)=nlogn了

作者: daybreakcx 发布时间: 2010-08-25

【求数学达人解释】用分治法求最大子段和中，复杂度为O(nlogn)是怎么算出来的？？

热门阅读

热门下载