最佳，最差和平均情況下運行時間

任何人都可以簡單地解釋我什麼是算法的最佳，最差和平均情況下運行時間？最佳，最差和平均情況下運行時間

來源

2012-03-05 Grant

你試過搜索嗎？ – utopianheaven 2012-03-05 03:22:31

我刪除了「操作系統」標籤，因爲它對問題沒有任何作用。 – ffriend 2012-03-05 03:23:30

是的......但我找不到完美的答案 – Grant 2012-03-05 03:23:47

在最簡單的術語，對於一個問題，其中輸入大小是Ñ：

最好的情況 =最快的時間來完成的，具有最佳的輸入選擇。
例如，排序算法的最佳情況是已經排序的數據。
最壞情況 =最慢的時間完成，選擇最佳輸入。
例如，排序算法的最壞情況可能是按相反順序排序（但取決於特定算法）的數據。
平均情況 =算術平均值。運行該算法很多次，使用許多不同的輸入，這些輸入的大小分別爲n，這些輸入來自某些生成這些輸入的分佈（在最簡單的情況下，所有可能的輸入具有相同的可能性），計算總運行時間（通過添加單個時間），除以試驗次數。您可能還需要根據輸入集的大小對結果進行歸一化。

複雜性和運行時間中的「大O符號」，它是用來描述算法需要完成的大概時間，基於其輸入的大小通常表示。 Rob Bell用非常明確的例子寫了一個excellent overview。

最常用的大O描述是

O（1）總是終止於大約相同的時間量，而與輸入大小無關。
O（logN）在每次輸入大小加倍時需要一個固定的額外時間量。
如果輸入大小加倍，O（N）需要兩倍的時間才能完成。
O（N ）需要四倍的時間，如果輸入大小加倍。
O（2 ^N）隨着輸入尺寸的增加呈指數增長。

從下表可以看出，對於小輸入尺寸，差異很小，但隨着輸入尺寸增加一點點，差異會變得很大。

 
Input Size    Time to Complete 
       O(1) O(logN) O(N) O(N²) O(2^N) 
    1   1  1  1  1  1 
    2   1  2  2  4  4 
    4   1  3  4  16  16 
    8   1  4  8  64  256 
    16   1  5  16  254 65536

來源

2012-03-05 03:22:50

錯了。首先，三個都是固定的輸入大小'n'。否則，「最差」或「最佳」可能沒有明確定義。其次，平均情況意味着對所有*輸入（該給定大小）的平均值取平均值，通過一些概率分佈（通常是統一的）進行加權。 – Raphael 2012-03-05 11:33:12

最好的時間就像是如果東西已經排序，那麼就不需要做任何工作。最糟糕的情況（取決於您的算法），但想想會導致您的算法花費最長的時間。

來源

2012-03-05 03:23:01

將算法看作程序。這個程序需要一些數據，攪動一段時間，然後吐出答案。當然，我們關心程序在給出答案之前會在數據上產生多長時間。

但有一個問題：對於許多算法，運行時間取決於數據本身。例如，對於已排序的數據，許多排序算法更快，而對於按相反順序排序的數據，一些排序算法最慢。

那麼讓我們來思考數據來自何處。也許你最好的朋友可以選擇數據。你的朋友選擇的數據可以讓程序快速運行，我們稱該運行時爲最佳情況，因爲算法永遠不會比這更好。也許你最大的敵人（在教科書中稱爲敵手）選擇數據。你最糟糕的敵人會選擇導致程序運行緩慢的數據，我們稱該運行時爲最壞情況，因爲算法永遠不會做得更差。也許一個巨大的輪盤賭可以選擇你的數據。然後，您可以在一堆輪盤數據上運行算法，並平均所有運行時間以獲得平均情況時間。

來源

2012-03-05 03:23:31

::::: ... thnnks的答案和幫助我:) – Grant 2012-03-05 03:33:14

算法的運行時間取決於輸入的大小和「複雜度」。

例如在某些尺寸的輸入運行插入排序的時間Ñ的最好的情況下Ñ成正比，即Ç * Ñ時間對於某一常數Ç取決於單位在計算模型的比較，算術......的成本（時間）上。所述最壞的情況下運行該算法（插入排序）的時間正比於Ñ * Ñ。要對的平均時間做出聲明，我們需要對輸入數據的分佈進行一些假設：例如，如果輸入是隨機數據（因此可能未排序），則平均運行時間再次與n * n成比例。

如果您對輸入數據有更多瞭解，例如它是按照遞減值排序的（並且我們按遞增值進行排序）平均運行時間是與n * n相比較的平均運行時間，但常數因子更高（因爲平均搜索時間爲最小值（將插入排序的子列表末尾）需要更長的時間）。

另一個更復雜的例子是快速排序：它的平均和最佳運行時間的隨機數據成正比ň *登錄ñ。最糟糕的種姓時間仍然是ň * ñ（通常爲一個已排序輸入，但是這依賴於算法來找出在分步樞軸元素）。

來源

2012-03-05 14:52:35 Stefan

最壞的情況通常是由漸近記法，即大（o）表示

最好的情況是漸近記法，即大（OMEGA）表示

來源

2013-09-05 23:21:33 TANYA

最壞情況分析（通常完成） 在最壞的情況在案例分析中，我們計算算法運行時間的上限。我們必須知道引起最大執行次數的情況。對於線性搜索，當要搜索的元素（上述代碼中的x）不存在於數組中時，會發生最糟糕的情況。當x不存在時，search（）函數將它與arr []的所有元素逐一比較。因此，線性搜索的最壞情況時間複雜度將是Θ（n）。

平均情況分析（有時完成） 在平均情況分析，我們採取所有可能的輸入和計算的計算時間對所有的輸入。將所有計算值相加，並將總和除以總輸入數量。我們必須知道（或預測）案件的分佈情況。對於線性搜索問題，讓我們假設所有的情況是均勻分佈的（包括x不存在於數組中的情況）。所以我們對所有的情況進行求和並且把和除以（n + 1）。以下是平均案例時間複雜度的值。

最佳案例分析（假冒） 在最佳案例分析中，我們計算算法運行時間的下限。我們必須知道導致執行最少操作次數的情況。在線性搜索問題中，當x出現在第一個位置時發生最好的情況。最佳情況下的操作次數是恆定的（不依賴於n）。所以在最好情況下的時間複雜度將是Θ（1）

來源

2016-03-17 10:50:37

最佳，最差和平均情況下運行時間

回答

相關問題