转：算法的最坏情况与平均情况 复杂度就要看最坏情况

转自：算法的最坏情况与平均情况

如果一个程序运行多次，则有时候它会快点儿，有时候它会慢点儿。算法也一样，在输入1的情况下和输入2的情况下，其执行效率不一定一样。即算法会随着输入数据的不同而有秩序效率的不同，有时候会快点儿，有时候会慢点儿。例如，对一个已经排好序的序列进行排序就要相对容易一些。另外，输入规模的大小也影响算法的运行时间。例如，一个短的序列就比一个很长的序列容易排序。

一般来说，我们希望获得一个算法的时间效率下限，因为所有人都喜欢某种保证：即算法无论如何不会低于我们保证的效率。这种分析就是所谓的最坏情况分析。最坏情况分析指的是在给定输入尺寸的情况下，一个算法运行的效率的下限。

•  
  比如早晨上班出门后突然想起来，手机忘记带了，这年头，钥匙、钱包、手机三大件，出门哪样也不能少呀。于是回家找。打开门一看，手机就在门口玄关的台子上，原来是出门穿鞋时忘记拿了。这当然是比较好，基本没花什么时间寻找。可如果不是放在那里，你就得进去到处找，找完客厅找卧室、找完卧室找厨房、找完厨房找卫生间，就是找不到，时间一分一秒的过去，你突然想起来，可以用家里座机打一下手机，听着手机铃声来找呀，真是笨。终于找到了，在床上枕头下面。你再去上班，迟到。见鬼，这一年的全勤奖，就因为找手机给黄了。

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

算法(Algorithms)的复杂度(Complexity)是指运行一个算法所需消耗的资源(时间或者空间)。同一个算法处理不同的输入数据所消耗的资源也可能不同，所以分析一个算法的复杂度时，主要有三种情况可以考虑，最差情况(Worst Case)下的，平均情况(Average Case)的， 最好情况(Best Case)下的。

算法的分析也是类似，我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。平均情况更能反映大多数情况下算法的表现。平均情况分析就是对所有输入尺寸为n的输入，让算法运转一遍，然后取它们的平均值。当然，实际中不可能将所有可能的输入都运行一遍，因此平均情况通常指的是一种数学期望值，而计算数学期望值则需要对输入的分布情况进行假设。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。

有时候我们还需要知道最好情况是什么，这有两层意义：一是我们想知道如果运气好，能好到什么程度；二是如果我们能够证明好运气与我们同在，当然需要知道运气好的时候算法表现如何。这种最好分析就是在给定输入规模的时候，看看哪种输入能使算法的运行最有效率。当然，有人认为这种最好情况分析有点假：我们可以操控输入来使一个本来很慢的算法表现得很快，从而达到蒙蔽人的效果。

对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

•  
  我以前问过老师，为什么要分析最坏情况下的算法时间复杂性？结果老师的答案是程序就是要看最差的时间，而且最差时间比较容易计算出来。
•  
  嗯，这是个原因。大概还有下面的一些原因：

1. 最差情况下的复杂度是所有可能的输入数据所消耗的最大资源，如果最差情况下的复杂度符合我们的要求，我们就可以保证所有的情况下都不会有问题。
2. 某些算法经常遇到最差情况。比如一个查找算法，经常需要查找一个不存在的值。
3. 也许你觉得平均情况下的复杂度更吸引你，可是平均情况也有几点问题。第一，难计算，多数算法的最差情况下的复杂度要比平均情况下的容易计算的多，第二，有很多算法的平均情况和最差情况的复杂度是一样的. 第三，什么才是真正的平均情况？如果你假设所有可能的输入数据出现的概率是一样的话，也是不合理的。其实多数情况是不一样的。而且输入数据的分布函数很可能是你没法知道。
4. 考虑最好情况的复杂度更是没有意义。几乎所有的算法你都可以稍微修改一下，以获得很好的最好情况下的复杂度(要看输入数据的结构，可以是O(1))。怎样修改呢? 预先计算好某一输入的答案，在算法的开始部分判断输入，如果符合，给出答案。

延伸阅读

此文章所在专题列表如下：

1. 第一话：你的数据结构怎么学的？
2. 第二话：数据结构的历史与来由
3. 第三话：关于数据结构的一些概念
4. 第四话：数据的逻辑结构
5. 第五话：数据的物理结构
6. 第六话：关于数据类型
7. 第七话：抽象数据类型ADT
8. 第八话：补充数据结构基本概念的关系
9. 第九话：数据结构与算法的关系
10. 第10话：什么是算法？
11. 第11话：算法的五个基本特征
12. 第12话：什么样的算法才是好算法
13. 第13话：算法的性能分析
14. 第14话：如何计算算法的时间复杂度
15. 第15话：算法的最坏情况与平均情况
16. 第16话：算法的空间复杂度

原文：http://www.cnblogs.com/kira2will/p/4020007.html