線性搜尋分析（最差平均和最佳案例）

Created: November-22, 2018

我們可以有三種情況來分析演算法：

最糟糕的情況
平均情況

最佳案例

#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）操作。大多數其他排序演算法都有最差和最好的情況。例如，在快速排序的典型實現中（其中樞軸被選為角元素），最糟糕的情況發生在輸入陣列已經排序時，最好的情況發生在樞軸元素總是將陣列分成兩半時。對於插入排序，最壞的情況發生在陣列反向排序時，最好的情況發生在陣列以與輸出相同的順序排序時。