五大演算法總結

之前的幾篇文章里，為大家介紹了幾種常用的演算法思想，其中貪心、分治、動態規劃、回溯、分支限界這五種演算法思想並稱為五大演算法。它們各舉各的特點、優點，很常用。同樣的，枚舉以簡單易懂、不會錯過任何解等等一些獨特的優勢，經常在寫「暴力」的時候，也是很好用的演算法，於是在這裡，我把它也放入了基本演算法思想里。

如果對這些內容還很陌生，不妨來來回顧一下，

在這裡再簡單的總結一下，

0）枚舉法

枚舉法簡單暴力，沒有什麼問題是搞不定的，只要你肯花時間。同時對於小數據量，枚舉法是很優秀的演算法。枚舉法簡單，人人都能會，能解決問題，但它最大的缺點就是耗時。

1）貪心演算法

貪心演算法可以獲取到問題的局部最優解，不一定能獲取到全局最優解，同時獲取最優解的好壞要看貪心策略的選擇。特點就是簡單，能獲取到局部最優解，再通過局部最優解找到全局最優解。不同的貪心策略會導致得到差異非常大的結果。

2）分治演算法

分治演算法的邏輯更簡單了，就是一個詞，分而治之。分治演算法就是把一個大的問題分為若干個子問題，然後在子問題繼續向下分，一直到問題的規模足夠小時，通過子問題的解決，一步步向上，最終解決最初的大問題。分治演算法是遞歸的典型應用。

3）動態規劃演算法

當最優化問題具有重複子問題和最優子結構的時候，就是動態規划出場的時候了。動態規劃演算法的核心就是提供了一個記憶來緩存重複子問題的結果，避免了遞歸的過程中的大量的重複計算。動態規劃演算法的難點在於怎麼將問題轉化為能夠利用動態規劃演算法來解決，也就是遞推式的推導過程。

4） 回溯演算法

回溯演算法是深度優先策略的典型應用，回溯演算法就是沿著一條路向下走，如果此路不同了，則回溯到上一個分岔路，再選擇一條路走，一直這樣遞歸下去，直到遍歷完所有的路徑。簡單的來說，能進則進，不進則退。

5） 分支限界演算法

和回溯法是一對兄弟，回溯是深度優先，那麼分支限界法就是廣度優先的一個經典的例子。回溯法一般來說是遍歷整個解空間，獲取問題的所有解，而分支限界法則是獲取一個解（一般來說要獲取最優解）。

在後面的文章里會圍繞這幾大基本演算法思想，來介紹一些經典演算法。二分搜索、背包問題、最短路徑、並查集、最小生成樹......

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！