算法分析|集2（最差、平均和最佳情况）-yiteyi-C++库

在以前的职位，我们讨论了渐近分析如何克服分析算法的简单方法的问题。在本文中，我们将以线性搜索为例，用渐近分析法对其进行分析。我们可以用三种情况来分析算法： 1）最坏的情况 2）普通病例 3）最佳案例让我们考虑下面的线性搜索的实现。

null

C++

                         // C++ implementation of the approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // 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;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 10, 30, 15 };                       
                                                 int                                     x = 30;                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << x <<                                     " is present at index "                       
                                                 << search(arr, n, x);                       
           
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed                       
                         // by Akanksha Rai                       

C

                         // C implementation of the approach                       
                         #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;                       
                         }                       
           
                         /* 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;                       
                         }                       

JAVA

                         // Java implementation of the approach                       
           
                         public                                     class                                     GFG {                       
           
                                                 // Linearly search x in arr[].  If x is present then                       
                                                 // return the index, otherwise return -1                       
                                                 static                                     int                                     search(                                     int                                     arr[],                                     int                                     n,                                     int                                     x)                       
                                                 {                       
                                                 int                                     i;                       
                                                 for                                     (i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (arr[i] == x) {                       
                                                 return                                     i;                       
                                                 }                       
                                                 }                       
                                                 return                                     -                                     1                                     ;                       
                                                 }                       
           
                                                 /* Driver program to test above functions*/                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     10                                     ,                                     30                                     ,                                     15                                     };                       
                                                 int                                     x =                                     30                                     ;                       
                                                 int                                     n = arr.length;                       
                                                 System.out.printf(                                     "%d is present at index %d"                                     , x,                       
                                                 search(arr, n, x));                       
                                                 }                       
                         }                       
           
                         /*This code is contributed by PrinciRaj1992*/                       

Python3

                         # Python 3 implementation of the approach                       
           
                         # Linearly search x in arr[]. If x is present                       
                         # then return the index, otherwise return -1                       
           
           
                         def                                     search(arr, x):                       
                                                 for                                     index, value                                     in                                     enumerate                                     (arr):                       
                                                 if                                     value                                     =                                     =                                     x:                       
                                                 return                                     index                       
                                                 return                                     -                                     1                       
           
           
                         # Driver Code                       
                         arr                                     =                                     [                                     1                                     ,                                     10                                     ,                                     30                                     ,                                     15                                     ]                       
                         x                                     =                                     30                       
                         print                                     (x,                                     "is present at index"                                     ,                       
                                                 search(arr, x))                       
           
                         # This code is contributed                       
                         # by PrinciRaj1992                       

C#

                         // C# implementation of the approach                       
                         using                                     System;                       
                         public                                     class                                     GFG {                       
           
                                                 // Linearly search x in arr[].  If x is present then                       
                                                 // return the index, otherwise return -1                       
                                                 static                                     int                                     search(                                     int                                     [] arr,                                     int                                     n,                                     int                                     x)                       
                                                 {                       
                                                 int                                     i;                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] == x) {                       
                                                 return                                     i;                       
                                                 }                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
           
                                                 /* Driver program to test above functions*/                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 1, 10, 30, 15 };                       
                                                 int                                     x = 30;                       
                                                 int                                     n = arr.Length;                       
                                                 Console.WriteLine(x +                                     " is present at index "                       
                                                 + search(arr, n, x));                       
                                                 }                       
                         }                       
           
                         /*This code is contributed by PrinciRaj1992*/                       

PHP

                         <?php                       
                         // PHP implementation of the approach                       
           
                         // Linearly search x in arr[]. If x                       
                         // is present then return the index,                       
                         // otherwise return -1                       
                         function                                     search(                                     $arr                                     ,                                     $n                                     ,                                     $x                                     )                       
                         {                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] ==                                     $x                                     )                       
                                                 return                                     $i                                     ;                       
                                                 }                       
                                                 return                                     -1;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 10, 30, 15);                       
                         $x                                     = 30;                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         echo                                     $x                                     .                                     " is present at index "                                     .                       
                                                 search(                                     $arr                                     ,                                     $n                                     ,                                     $x                                     );                       
           
                         // This code is contributed                       
                         // by Akanksha Rai                       

Javascript

                         <script>                       
                         // javascript implementation of the approach                       
           
                                                 // Linearly search x in arr. If x is present then                       
                                                 // return the index, otherwise return -1                       
                                                 function                                     search(arr , n , x) {                       
                                                 var                                     i;                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] == x) {                       
                                                 return                                     i;                       
                                                 }                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
           
                                                 /* Driver program to test above functions */                       
                                   
                                                 var                                     arr = [ 1, 10, 30, 15 ];                       
                                                 var                                     x = 30;                       
                                                 var                                     n = arr.length;                       
                                                 document.write(x+                                     " is present at index "                                     + search(arr, n, x));                       
           
                         // This code is contributed by gauravrajput1                       
                         </script>                       

输出：

30 is present at index 2

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

一般案例分析（有时完成） 在平均案例分析中，我们会获取所有可能的输入，并计算所有输入的计算时间。对所有计算值求和，然后除以输入总数。我们必须知道（或预测）病例的分布情况。对于线性搜索问题，假设所有情况都是均匀分布（包括阵列中不存在x的情况）。所以我们求和所有的情况，然后除以（n+1）。以下是平均案例时间复杂度的值。

Average Case Time =

图片[1]-算法分析|集2（最差、平均和最佳情况）-yiteyi-C++库

图片[2]-算法分析|集2（最差、平均和最佳情况）-yiteyi-C++库

= Θ(n)

最佳案例分析（伪造） 在最佳情况分析中，我们计算算法运行时间的下限。我们必须知道导致执行最少操作数的情况。在线性搜索问题中，当x出现在第一个位置时，会出现最佳情况。最佳情况下的操作数是恒定的（不依赖于n）。因此，最佳情况下的时间复杂度为Θ（1）大多数情况下，我们会做最坏情况分析来分析算法。在最坏的分析中，我们保证算法的运行时间有一个上界，这是好的信息。在大多数实际案例中，普通案例分析并不容易，而且很少进行。在平均案例分析中，我们必须知道（或预测）所有可能输入的数学分布。最好的案例分析是假的。保证算法的下限不会提供任何信息，因为在最坏的情况下，算法可能需要数年才能运行。对于某些算法，所有情况都是渐近相同的，即不存在最坏和最佳情况。例如合并排序 .合并排序在所有情况下都执行Θ（nlogn）操作。大多数其他排序算法都有最坏和最好的情况。例如，在快速排序的典型实现中（选择pivot作为角元素），最坏的情况发生在输入数组已经排序时，最好的情况发生在pivot元素总是将数组分成两半时。对于插入排序，最坏的情况发生在数组反向排序时，最好的情况发生在数组按与输出相同的顺序排序时。

https://youtu.be/rlZpZ8es_6k

接下来—— 算法分析|集3（渐近符号） 参考资料： 麻省理工学院关于算法介绍的视频讲座1 . 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章