首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

时间复杂度怎么计算

2012-03-30 
时间复杂度如何计算某个算法的时间复杂度满足 T(n)2T(n/2)+O(n),比如快速排序,怎么解出来时间复杂度 T(n)

时间复杂度如何计算
某个算法的时间复杂度满足 T(n)=2T(n/2)+O(n),比如快速排序,怎么解出来时间复杂度 T(n)=O(nlogn) 的啊


[解决办法]
这个证明比较复杂,老师上课没有讲,叫我们记住即可
[解决办法]
T(n)=2T(n/2)+O(n)这是个递归式:
也就是,要从N对规到1,递归的方式是n/2,这个次数是:logn。即2的logn次方等于n
当然了递归时还要计算O(n)
所以就是O(nlogn),参数2在这种情况下不计算。

热点排行