最壞情況分析不等於漸近界

Question

有人可以向我解釋爲什麼這是真的。我聽到一位教授提到這是他的演講

Answer 1

這兩個概念是正交的。

你可以有最壞情況漸近線。如果f(n)表示輸入爲n的給定算法所花費的最差情況時間，則可以有例如。 f(n) = O(n^3)或其他最壞情況時間複雜度的漸近上界。

同樣地，可以有g(n) = O(n^2 log n)其中g(n)是（比方說）所採取的相同的算法的平均時間大小n的均勻分佈的（隨機的）輸入。

或者可以擁有h(n) = O(n)其中h(n)是具有大小n特別分佈式隨機輸入採取的相同的算法（例如，幾乎已排序的序列爲一個排序算法）的平均時間。

漸近表示法是一種「度量」。你必須指定要算什麼：最壞的情況下，最好的情況下，平均等

有時候，你有興趣，說明漸近下界（說）最壞情況下的複雜性。然後你寫f(n) = Omega(n^2)陳述，在最壞的情況下，複雜性至少是n^2。大歐米茄符號與大O相反：f = Omega(g)當且僅當g = O(f)。

Answer 2

漸近界是操作數達到無窮大時的預期行爲。從數學角度來說，只要n變成無窮大就是這樣。然而，最壞的情況行爲適用於有限數量的操作。

Answer 3

以quicksort爲例。快速排序的每個連續遞歸調用n具有

T（n）的運行時間複雜度T（N）= O（N）+ 2 T [（N-1）/ 2]

在

「如果未分類的輸入列表在每次調用中被分成兩個相同的大小爲（n-1）/ 2的子列表，則爲'最好的情況'。在這種情況下，求解T（n）給出O（n log n）。如果分區是不完美的，並且兩個子列表相等大小爲n的不，即

T（N）= O（N）+ T（K）+ T（N - 1 - k）時，

即使k = 1，我們仍然獲得O（n log n），只是具有較大的常數因子。這是因爲只要k> 0，處理輸入列表時，快速排序的遞歸調用的次數就呈指數級上升。

然而，在 '最壞情況' 沒有輸入列表的分裂發生，即：

T（N）= O（N）+ T（0）+ T（N - 1）= O （n）+ O（n-1）+ T（n-1）+ T（n-2）...。

發生這種情況例如如果我們將排序列表的第一個元素作爲主元素。這裏，T（0）表示得到的子列表之一是零，因此不需要計算時間（因爲子列表具有零元素）。第二個子列表需要剩餘的所有負載T（n-1）。在這種情況下，我們得到O（n²）。

如果一個算法沒有最壞的情況，它不僅是O [f（n）]，而且也是o [f（n）]（Big-O與little-o notation）。