线性搜索分析（最差平均和最佳案例）

我们可以有三种情况来分析算法：

1. 最糟糕的情况

2. 平均情况

3. 最佳案例

   #include <stdio.h>
   
   // Linearly search x in arr[].  If x is present then return the index,
   
   // otherwise return -1
   int search(int arr[], int n, int x)
   {
       int i;
       for (i=0; i<n; i++)
       {
           if (arr[i] == x)
            return i;
       }
   
       return -1;
   }
   

   / *驱动程序来测试上面的函数* /

   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;
   }   
   

最坏情况分析（通常完成）

在最坏的情况分析中，我们计算算法运行时间的上限。我们必须知道导致执行最大操作数的情况。对于线性搜索，最坏的情况发生在数组中不存在要搜索的元素（上面代码中的 x）时。当 x 不存在时，search() 函数将它与 arr []的所有元素逐一进行比较。因此，线性搜索的最坏情况时间复杂度为Θ（n）

平均案例分析（有时完成）

在平均案例分析中，我们采用所有可能的输入并计算所有输入的计算时间。将所有计算值相加并将总和除以输入总数。我们必须知道（或预测）案件的分配。对于线性搜索问题，让我们假设所有情况都是均匀分布的（包括 x 不存在于数组中的情况）。因此，我们总结所有情况并将总和除以（n + 1）。以下是平均案例时间复杂度的值。

https://i.stack.imgur.com/UyxRr.jpg

最佳案例分析（假）

在最佳案例分析中，我们计算算法运行时间的下限。我们必须知道导致执行最少操作数的情况。在线性搜索问题中，当 x 出现在第一个位置时，会出现最佳情况。最佳情况下的操作数是恒定的（不依赖于 n）。因此，最佳情况下的时间复杂度将为Θ（1）大多数情况下，我们进行最差情况分析以分析算法。在最糟糕的分析中，我们保证算法运行时间的上限，这是一个很好的信息。在大多数实际案例中，平均案例分析并不容易，很少进行。在平均案例分析中，我们必须知道（或预测）所有可能输入的数学分布。最佳案例分析是假的。

对于某些算法，所有情况都是渐近相同的，即没有最差和最好的情况。例如，合并排序。合并排序在所有情况下都执行Θ（nLogn）操作。大多数其他排序算法都有最差和最好的情况。例如，在快速排序的典型实现中（其中枢轴被选为角元素），最糟糕的情况发生在输入数组已经排序时，最好的情况发生在枢轴元素总是将数组分成两半时。对于插入排序，最坏的情况发生在数组反向排序时，最好的情况发生在数组以与输出相同的顺序排序时。