算法的最坏、平均和最佳情况分析

在上一篇文章中，我们讨论了渐近分析如何克服分析算法的朴素方法所存在的问题。现在让我们来学习什么是算法的最坏情况、平均情况和最佳情况：

1. 最坏情况分析（最常用）

• 在最坏情况分析中，我们计算算法运行时间的上界。我们必须知道导致执行最大数量操作的情况是什么。
• 对于线性搜索，最坏情况发生在要搜索的元素 不存在于数组中时。当不存在时，INLINECODE7fde6066 函数会将其与 INLINECODEf7dbe2c6 中的所有元素逐一进行比较。
• 这是算法分析中最常用的分析方法（我们将在下面讨论原因）。大多数时候，我们考虑会导致最大操作的情况。

2. 最佳情况分析（极少使用）

• 在最佳情况分析中，我们计算算法运行时间的下界。我们必须知道导致执行最小数量操作的情况是什么。
• 对于线性搜索，最佳情况发生在 存在于第一个位置时。最佳情况下的操作数量是常数（不依赖于）。因此，就输入大小而言，时间增长的数量级是常数。

3. 平均情况分析（很少使用）

• 在平均情况分析中，我们要获取所有可能的输入，并计算所有输入的计算时间。将所有计算出的值求和，并将总和除以输入的总数。
• 假设在线性搜索中所有情况（包括 不在数组中）的可能性均等，则平均情况通过将所有情况求和并除以 n+1 来计算，以考虑到元素可能不存在的情况。

为什么最坏情况分析最常用？

平均情况： 平均情况分析在大多数实际情况下并不容易完成，因此很少进行。在平均情况分析中，我们需要考虑每一个输入、其频率以及它所花费的时间，这在许多场景下可能是不可能的。
最佳情况： 最佳情况分析的价值有限，因为当算法的最坏情况运行时间可能非常大时，知道下界提供的见解很少。
最坏情况： 这比平均情况更容易，并且提供了一个上界，这是分析软件产品的有用信息。

关于渐近符号的有趣信息：

> A) 对于某些算法，所有情况（最坏、最佳、平均）在渐近上都是相同的。即，没有最坏和最佳之分。

>

> – 示例： 归并排序 在所有情况下都执行 n log(n) 数量级的操作。

>

> B) 而大多数其他排序算法都有最坏和最佳情况。

>

> – 示例 1： 在快速排序的典型实现中（其中基准被选择为角落元素），当输入数组已经排序时发生最坏情况，当基准元素始终将数组分成两半时发生最佳情况。

> – 示例 2： 对于插入排序，当数组反向排序时发生最坏情况，当数组按与输出相同的顺序排序时发生最佳情况。

示例及其复杂度分析：

1. 线性搜索算法：

C++


CODEBLOCK_4beb3a72


C


CODEBLOCK_5e4c4b9a


Java

`

import java.util.Arrays;

// Linearly search target in arr.
// If target is present, return the index;
// otherwise, return -1
public class GfG {
    public static int search(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 10, 30, 15};
        int x = 30;
        System.out.println(search