在上一篇文章中，我们讨论了渐近分析如何克服算法分析方法幼稚的问题。在这篇文章中，我们将以线性搜索为例，并使用渐近分析对其进行分析。 我们可以用三种情况来分析算法：
- 最坏情况
- 平均情况
- 最好情况 让我们考虑以下线性搜索的实现。
该方法的 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) 操作。大多数其他排序算法都有最坏和最好的情况。例如，在快速排序的典型实现中（其中枢轴被选为角元素），最坏的情况发生在输入数组已经排序时，而最好的情况是枢轴元素总是将数组分成两半。对于插入排序，最坏的情况发生在数组反向排序时，最好的情况发生在数组按与输出相同的顺序排序时。
