最坏，平均和最佳运行时间(Worst, Average and Best Cases)（转）

yuyang911220

来自http://www.cnblogs.com/zhurui1322/p/5351668.html
我们从三个方面分析算法：
1.最坏情况
2.平均情况
3.最佳情况

这是一段很简单的线性查找的代码 从arr[] 中查找x
[url=][/url]
// Linearly search x in arr[].  If x is present then return the index,// otherwise return -1int search(int arr[], int n, int x){    int i;    for (i=0; i<n; i++)    {       if (arr == x)         return i;    }    return -1;} /* Driver program to test above functions*/int main(){    int arr[] = {1, 10, 30, 15};    int x = 30;    int n = sizeof(arr)/sizeof(arr[0]);    printf("%d is present at index %d", x, search(arr, n, x));     getchar();    return 0;}[url=][/url]

最坏情况分析（通常都是可以完成的）Worst Case Analysis (Usually Done)
在最坏运行时间分析中，我们计算运行时间的上界限。这种最坏情况下，一定会运行最大的操作数量（maximum number of operations）在线性搜索中，最坏的情况时发生在x不在array[]中，所以search()会用x和所有在array[]中的元素比较，所以最坏时间复杂度是O(n);

平均情况分析 （ 有时可以完成）Average Case Analysis (Sometimes done)
在平均情况分析中，我们计算所有可能的输入的运行时间，把所有的时间加起来除以数量，我们必须知道这些情况的分布。在线性搜索算法下，我们假设所有的情况是平均分布的（包括x不在array[]的情况.(在一个有n个数的数组里 x的位置有n+1种情况)
average case time = = = O(n)

最佳情况分析Best Case Analysis (Bogus)
在最佳情况分析中，我们计算运行时间的下界限，算法用最少的操作就可以完成，在线性搜索中，最佳的情况是x的位置就是第一个，所以说总的操作次数是固定的，不取决于n的大小。所以在最佳情况下时间复杂度是O(1)。

在大多数情况下，我们用最差情况来分析算法，我们可以保证运行时间的上界限，这对于算法来说是一个好的信息。
对于平均情况的分析，对于很多具体的例子不是很容易分析。因为我们必须知道输入的分布情况。
而对于最佳情况的分析就不是很好了，保证下界限并不能提供任何信息尤其是在最坏的情况下，有可能你的算法要运行很久甚至一年。
对于一些算法，这三种情况的渐进分析都是一样的，例如没有最坏，最佳的情况。例如归并排序，所有的情况的时间复杂度都是O(nlogn) 。而对于其他大多数排序算法都有最坏情况和最佳情况，例如基本的快速排序（选择基准的时候pivot 选最左或最右的元素）。那么最坏情况就是输入的数组已经是排序好的，最好的情况就是数组总是能分成两个大小一样的子数组。对于插入排序，最坏的情况就是输入数组是逆序，最好的情况是输入数组是已排序的。