分而治之 - 它爲什麼起作用？

Question

我知道，像歸併排序和快速排序算法使用分而治之的模式，但我不知道爲什麼它在降低了時間複雜度工作...

爲什麼通常不會是「分而治之」的算法工作比非分而治之更好？

Answer 1

分而治之作品，因爲數學支持它！

考慮這幾個分治法：

1）二進制搜索：該算法降低了你的輸入空間各佔一半時間。直觀地表明這比線性搜索更好，因爲我們會避免查看很多元素。

但是有多好？我們得到的複發率（注：這是復發的最壞情況分析）：

T(n) = T(n/2) + O(1)

數學意味着T(n) = Theta(log n)。因此這比線性搜索指數地更好。

2）合併排序：在這裏我們分成兩個（幾乎）相等的一半，排序一半，然後合併它們。爲什麼這應該比二次方好？這是復發：

T(n) = 2T(n/2) + O(n)

可以從數學上（說使用主定理），其T(n) = Theta(n log n)。因此T（n）漸近地好於二次方。

觀察該天真快速排序結束了給我們最壞的情況下復發的

T(n) = T(n-1) + O(n)

其中數學，出來是二次，並在最壞的情況下，也不好過冒泡排序（漸近地說）。但是，我們可以證明，在一般情況下，快速排序是O（n log n）。

3選擇算法：這是一個征服算法來尋找第k個最大的元素。這種算法是否優於排序（或者甚至不是二次的）並不明顯。

但在數學上，其復發（再次最壞情況）出來是

T(n) = T(n/5) + T(7n/10 + 6) + O(n)

可以證明數學是T(n) = O(n)，因此它比分揀好。

也許一個共同的方式來看待他們：

你可以看一下算法，樹，其中每個子問題成爲當前的一個子樹和節點可以用的工作量進行標記完成，然後可以爲每個節點添加全部工作。

對於二分查找，工作是O（1）（只是一個比較）和其中一個子樹，工作是0，所以工作的總量是O（log n）（本質上是一個路徑，就像我們在二叉搜索樹中做的那樣）。

對於合併排序，對於有k個孩子的節點，工作是O（k）（合併步驟）。在每個級別完成的工作是O（n）（n，n/2 + n/2，n/4 + n/4 + n/4 + n/4等），並且有O（log n）級別，所以合併排序是O（n log n）。

對於快速排序，在最壞的情況下，二叉樹實際上是一個鏈表，因此完成的工作是n + n-1 + ... + 1 = Omega（n^2）。

對於選擇排序，我不知道如何可視化它，但我相信把它看作一個有3個孩子（n/5,7n/10和其餘）的樹可能仍然有幫助。

Answer 2

分而治之的算法不「通常更好」。正如其他非分而治之算法一樣，它們只是起作用。它們不會降低排序的複雜性，它們和其他算法一樣好。

Answer 3

分而治之算法的工作速度更快，因爲他們最終只做更少的工作。

考慮二進制搜索的經典分而治之算法：與其查看N項目以查找答案，二分搜索最終僅檢查其中的Log2N。當然，當你做更少的工作時，你可以更快地完成;這正是分而治之算法的發展方向。

當然，結果很大程度上取決於你的策略在分工方面的表現如何：如果分部在每一步中或多或少都公平（即將工作劃分爲一半），則可以獲得完美的速度。但是，如果分割並不完美（例如最壞的快速排序情況，當它將O(n^2)排序爲數組，因爲它在每次迭代中只消除了一個元素），那麼分治策略並沒有什麼幫助，因爲您的算法不會不減少工作量。

Answer 4

因爲在某些情況下，最好將問題分成較小的子問題，這比原始問題要容易得多。即使增加了合併（合併）部分解決方案的複雜性。

我認爲現實世界與戰爭類比（消除敵人）是準確的。分開你的敵人，分開摧毀它們，比同時處理它們更好。

而且作爲alestanis已經說過，分治算法只是一類算法，並不能保證它比不分割和征服要快。例如，堆排序與合併排序具有相同的漸近複雜性。另一方面，Quicksort的複雜程度比他們兩個都差，但平均表現更好....