gr8vyguy@Blogjava

算法分析时为什么偏爱最差情况?

算法(Algorithms)的复杂度(Complexity)是指运行一个算法所需消耗的资源(时间或者空间)。同一个算法处理不同的输入数据所消耗的资源也可能不同,所以分析一个算法的复杂度时,主要有三种情况可以考虑,最差情况(Worst Case)下的,平均情况(Average Case)的, 最好情况(Best Case)下的。不管是在实际应用中,还是计算机理论的研究中,大多都只考虑最差情况下的复杂度分析。为什么呢?这里给出四点原因,
  1. 最差情况下的复杂度是所有可能的输入数据所消耗的最大资源,如果最差情况下的复杂度符合我们的要求,我们就可以保证所有的情况下都不会有问题。
  2. 某些算法经常遇到最差情况。比如一个查找算法,经常需要查找一个不存在的值。
  3. 也许你觉得平均情况下的复杂度更吸引你,可是平均情况也有几点问题。第一,难计算,多数算法的最差情况下的复杂度要比平均情况下的容易计算的多,第二,有很多算法的平均情况和最差情况的复杂度是一样的. 第三,什么才是真正的平均情况?如果你假设所有可能的输入数据出现的概率是一样的话,也是不合理的。其实多数情况是不一样的。而且输入数据的分布函数很可能是你没法知道。
  4. 考虑最好情况的复杂度更是没有意义。几乎所有的算法你都可以稍微修改一下,以获得很好的最好情况下的复杂度(要看输入数据的结构,可以是O(1))。怎样修改呢? 预先计算好某一输入的答案,在算法的开始部分判断输入,如果符合,给出答案。


转载请保留http://www.blogjava.net/xilaile/archive/2007/03/30/107374.html

posted on 2007-03-29 22:52 gr8vyguy 阅读(4335) 评论(1)  编辑  收藏 所属分类: 计算机科学基础

评论

# re: 算法分析时为什么偏爱最差情况? (内含一个小问题) 2007-04-02 06:06 liigo

说的很有道理,逻辑性强。  回复  更多评论   


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


网站导航:
 
<2007年3月>
25262728123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

公告

  • 转载请注明出处.
  • msn: gr8vyguy at live.com
  • 常用链接

    留言簿(9)

    随笔分类(68)

    随笔档案(80)

    文章分类(1)

    My Open Source Projects

    搜索

    积分与排名

    最新评论