J2EE之巅

 

算法的时间复杂度

 

相信大家对于算法的时间复杂度O都不会陌生,不过你知道一个算法的时间复杂度是如何计算出来的吗?

以前在学习算法和数据结构的时候,对于每种算法的复杂度都是死记的并没有真正的去研究他们是如何计算出来,最近突然对算法产生了兴趣,迫使自己研究了一下算法复杂度的计算方法。

概念

O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者

另外除了这个官方概念,个人认为大O表示的是问题规模n和算法中语句执行次数的关系。

以二分查找为例,我们求解它的时间复杂度

1 设规模为n个元素时,要执行T(n)次

T(n)=T(n/2)+1

T(n)=[T(n/4)+1]+1

T(n)=T(n/2^m)+m

n=2^m

T(n)=T(1)+log2n

T(1)=1

所以其算法复杂度为O(log2n)

posted on 2010-06-18 15:26 超越巅峰 阅读(3543) 评论(1)  编辑  收藏 所属分类: Computer Science

评论

# re: 算法的时间复杂度 2010-06-22 10:43 爱之谷

所以其算法复杂度为O(log2n)  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 

导航

统计

常用链接

留言簿(12)

随笔分类(54)

随笔档案(59)

文章分类(2)

文章档案(1)

相册

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜