加载中…
个人资料
了不起de狐狸爸爸
了不起de狐狸爸爸
  • 博客等级:
  • 博客积分:0
  • 博客访问:53,378
  • 关注人气:42
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

关于时间复杂度

(2011-09-14 20:18:08)
标签:

杂谈

分类: 课堂随笔

很多学生,学了四年计算机专业,很多程序员,做了很长时间的编程工作,却始终弄不明白算法的时间复杂度的估算,这是很可悲的一件事情。因为弄不明白,所以也就从不深究自己写的代码是否效率低下,是不是可以通过优化让计算机更加快速高效。

 

他们通常的借口是,现在CPU越来越快,根本不用考虑算法的优劣。实现功能即可,用户感觉不到算法好快造成的快慢。可事实真的是这样么?让我们用数据来说话吧。

 

假设CPU在短短几年内,速度提高了10呗。虽有有摩尔定律,这其实已经很夸张了。而我们的某个算法本可以写出时间复杂度是O(n)的算法,却写成了O(n^2)的程序,仅仅因为容易想到,也容易写。即在O(n^2)的时间复杂度程序下,速度其实只提高了10(根下100=10)倍。而对于O(n)时间复杂度的算法来说,那才是真的100倍。

 

也就是说,一台老式CPU的计算机运行O(n)的程序和一台速度提高100倍新式CPU运行O(n^2)的程序,最终效率高的胜利方却是老式CPU的计算机。原因在于算法的优劣直接决定了程序运行的效率。

 

由此可见,时间复杂度是非常重的一个衡量算法好快的事前估算的方法。它是数据结构课本中的第一个知识点也是各类考试的常见考点。我曾经说过,如果出数据结构考题的老师不是太痴呆的话,时间复杂度是必考的。去年研究生考试的第一个选择题也印证了这句话。

 

关于时间复杂度的计算方法不再赘述。这里说一下最坏情况与平均情况的时间复杂度。当你早上起床准备出去吃饭上课的时候,到了宿舍楼下才突然响起来,手机忘记带了。这年头,钥匙、钱包、手机三大件,哪样也不能少啊。回宿舍打开门一看,手就在对门的窗台上放着。这当然是比较好的,基本没花什么时间。可是如果不在那里,你就得到处找。可能翻遍了书桌和壁橱,等找到的时候都快8点了,匆匆去上课,早饭算是泡汤了。

 

找东西有运气好的时候,也有怎么都找不到的时候,但在现实中,通常我们碰到的绝大多数既不是最好也不最坏的,所以算下来是平均情况居多。

 

算法分析也是如此,在n个随即数中查找某个数字,最好的情况是第一个数字就是,此时时间复杂度为O(1),若最后一个数字才是我们要找的,那么时间复杂度是O(n),这是最坏的情况。而平均运行时间是从概率的角度看,若数字在每一个位置都可能出现,则平均查找次数为n/2次。

 

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。可现实中,平均运行时间很难通过分析得到,一般都是通过运行一定数量的实验数据后估算而来的。而最坏运行时间是一种保证,那就是运行时间不会再坏了。在应用中,这是最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况下的运行时间。即,时间复杂度是最坏情况下的时间复杂度。

 

也许你就可以深刻的感受到,愚公移山固然可敬,但发明推土机和炸药,更加实在和聪明。希望大家在今后的学习中,好好利用算法分析的工具,改进自己的代码,让计算机轻松一点,这样你就能更胜一筹。

 

 

关于时间复杂度

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有