算法分析 | 第二套（最差、平均和最佳情况）

在上一篇文章中，我们讨论了渐近分析如何克服算法分析方法幼稚的问题。在这篇文章中，我们将以线性搜索为例，并使用渐近分析对其进行分析。
我们可以用三种情况来分析算法：

1. 最坏情况
2. 平均情况
3. 最好情况
   让我们考虑以下线性搜索的实现。

该方法的 C++ 实现

#include <bits/stdc++.h>
using namespace std;

// 在 arr[] 中线性搜索 x。
// 如果 x 存在则返回索引，否则返回 -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]);
	cout << x << " is present at index "
		<< search(arr, n, x);

	getchar();
	return 0;
}

该方法的C实现

#include <stdio.h>

// 在 arr[] 中线性搜索 x。
// 如果 x 存在则返回索引，否则返回 -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;
}

该方法的Java实现

public class HY {

	// 在 arr[] 中线性搜索 x。
        // 如果 x 存在则返回索引，否则返回 -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;
	}

	/* 测试上述功能的驱动程序*/
	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));
	}
}

该方法的 Python 3 实现

// 在 arr[] 中线性搜索 x。
// 如果 x 存在则返回索引，否则返回 -1

def search(arr, x):
	for index, value in enumerate(arr):
		if value == x:
			return index
	return -1

#驱动程序代码
arr = [1, 10, 30, 15]
x = 30
print(x, "is present at index",
	search(arr, x))

输出:

30 is present at index 2

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

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

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

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

最佳案例分析（虚假）

在最佳案例分析中，我们计算算法运行时间的下限。我们必须知道导致执行最少操作数的情况。在线性搜索问题中，最好的情况发生在 x 出现在第一个位置时。最佳情况下的操作次数是恒定的（不依赖于 n）。所以最好情况下的时间复杂度是 Θ(1)

大多数时候，我们会做最坏情况分析来分析算法。在最坏的分析中，我们保证算法的运行时间有一个上限，这是一个很好的信息。

在大多数实际案例中，平均案例分析并不容易进行，而且很少进行。在平均情况分析中，我们必须知道（或预测）所有可能输入的数学分布。

最佳案例分析是假的。保证算法的下限不会提供任何信息，因为在最坏的情况下，算法可能需要数年才能运行。

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

以上就是本篇文章的全部内容

我真的希望你能从这篇文章中得到一些有用的东西。这里汇总了我的全部原创及作品源码：GitHub 如果大家能给我的 Github 存储库上添一些星星就更好了😊。

我已经写了很长一段时间的技术博客，这是我的一篇 响应式网站的 CSS 单位教程。我乐于通过文章分享技术与快乐。您可以访问我的华为云博客主页： 华为云-海拥、个人博客：haiyong.site 以了解更多信息。希望你们会喜欢！

💌 欢迎大家在评论区提出意见和建议！💌

如果你真的从这篇文章中学到了一些新东西，喜欢它，收藏它并与你的小伙伴分享。🤗最后，不要忘了❤或📑支持一下哦。

下一篇——算法分析 | 第 3 组（渐近符号）