算法分析（複雜度）

Question

如何分析算法？是什麼讓快速排序有O(n^2)最糟糕的表現，而合併排序有O(n log(n))最差的表現？

Answer 1

這是整個學期的話題。最終，我們正在討論算法完成之前必須完成的操作次數的上限，作爲輸入大小的函數。我們不包括coeffecients（即10N vs 4N^2），因爲對於N足夠大，它已經不重要了。

如何證明一個算法的大噢可能是相當困難的。它需要一個正式的證據，並有許多技術。通常，一種很好的特殊方法是隻計算算法產生的數據通過次數。例如，如果您的算法嵌套for循環，則對於N個項目中的每一個，您必須操作N次。那通常是O（N^2）。

至於合併排序，你一次又一次地分割數據。這需要log2（n）。並且對於每個分組，您對數據進行傳遞，這會得到N log（n）。

快速排序有點棘手，因爲在平均情況下它也是n log（n）。你必須想象如果你的分區分裂了數據，那麼每當你在分區的一側只有一個元素時會發生什麼。那麼你將需要分割數據n次而不是log（n）次，這使得N^2。快速排序的優勢在於它可以在適當的位置完成，而且我們通常可以接近N log（n）性能。

Answer 2

quicksort和merge sort將數組分成兩部分，遞歸地對每個部分進行排序，然後合併結果。 Quicksort通過選擇「pivot」元素進行分割，並將數組分割爲更小或更大的數據，然後將數據分割爲數據透視。合併排序可以任意分割，然後以線性時間合併結果。在這兩種情況下，單個步驟是O（n），並且如果每次數組大小減半，則這會給出對數數量的步驟。所以我們期望O（n log（n））。

然而，快速排序有一個最壞的情況，即分裂總是不均勻的，所以你沒有得到與n的對數成比例的許多步驟，而是與n成正比的許多步驟。合併排序完全分爲兩部分（或儘可能接近），所以它沒有這個問題。

Answer 3

• 快速排序有許多變種取決於樞選擇
• 假設我們總是在數組中選擇第一個項目爲支點

如果輸入數組進行排序，然後快速排序將只有一個種類選擇排序！ 因爲你並不是真的把數組分開..你只是在每個週期中挑選第一個項目

另一方面，合併排序總是會以相同的方式分割輸入數組，無論其內容如何！

另請注意：分割和征服時分割長度相等時的最佳性能！

Answer 4

1. 這是算法課程資料的入門分析。

2. 操作被定義（即乘法），並且分析是按空間或時間進行的。

3. 此操作按空間或時間計算。通常，分析按照輸入大小時間作爲因變量執行。

實施例的僞代碼：

foreach $elem in @list 

    op(); 

endfor 

會有Ñ操作來執行，其中Ñ是@list大小。如果你不相信我，請自己計算一下。

要分析quicksort和mergesort需要一個體面的水平的所謂的數學成熟。鬆散地，你可以求解一個由遞歸關係導出的離散微分方程。