分而治之和遞歸

Question

我不知道分而治之的技巧是否總是將一個問題分解成同一類型的子問題？同樣的類型，我的意思是可以使用遞歸函數來實現它。分而治之總是可以通過遞歸來實現嗎？

謝謝！

Answer 1

「永遠」是一個可怕的詞，但我不能想到一個分而治之的情況，你不能使用遞歸。根據定義，分而治之產生與初始問題相同形式的子問題 - 這些子問題不斷分解，直到達到一些基本情況，並且分區的數量與輸入的大小相關。遞歸是這類問題的自然選擇。

查看Wikipedia article瞭解更多信息。

Answer 2

分而治之算法由定義可以通過遞歸來解決。所以答案是肯定的。

Answer 3

通常，是的！ Merge sort就是一個例子。這是相同的animated version。

Answer 4

是的。在分治算法技術中，我們將給定的更大的問題分成更小的子問題。這些較小的子問題必須與較大的問題類似，只是這些問題的尺寸較小。

例如，對大小爲N的數組進行排序的問題與對大小爲N/2的數組進行排序的問題沒有什麼不同。除了後者的問題規模小於前者。

如果較小的子問題與較大的子問題不相似，那麼分而治之技術不能用於解決更大的問題。換句話說，只有當給定的較大問題可以分解爲與更大問題類似的更小的子問題時，才能使用分而治之技術來解決給定的問題。

Answer 5

遞歸是一種編程方法，您可以根據自身定義函數。該函數通常以略微修改的參數自動調用（以便收斂）。

1. 將問題分爲兩個或更多較小的子問題。
2. 通過求解它們（遞歸）來克服子問題。
3. 將子問題的解決方案結合到原問題的解決方案中。

Answer 6

檢查合併排序算法對於這個問題就足夠了。通過分而治之（理解遞歸）瞭解合併排序算法的實現之後，您將會看到如何使它無需遞歸是多麼困難。

實際上這裏最重要的是算法的複雜性，它用合併排序的大哦表示法和nlogn表示。

對於mergesort exapmle，有另一個版本叫做自下而上合併排序。它是簡單和非遞歸的版本。

它比典型系統上的遞歸自頂向下mergesort慢大約10％。你可以參考下面的鏈接獲取更多信息。第3講講得很好。

https://www.coursera.org/learn/introduction-to-algorithms#