為一個問題尋找算法的過程，有點像一個窮舉過程：搜索已有知識，并進行重組的過程。所以把常用的算法記住，然后一個一個試用，看是否可行，不失為一個好方法。
如果這個方法不行呢？不妨寫出最直觀的解答（即用“蠻力法”），然后從中看出可以優化的地方在哪里，進而進行優化。
如何確定該問題可以用哪類方法來解答呢？首先，需要對這些常用的算法的基本思想非常熟悉。
常用的算法可以分為以下幾類：
1. Divide & conquer
分治算法：將問題分為兩個1／2規模大小的子問題，然后解決。如merge sort
2. Decrease & conquer
減治法 : 將問題規模從 n 變為 n - 1，然后在規模n-1的基礎上解決此問題。 如insertion sort
這不是遞歸么？
3. Transform & conquer
變治法 ：變換結構。如heap sort
4. Brute force
蠻力算法，可以說是必殺技吧，大部分問題都可以用此方法解決。 如selection sort
使用蠻力法的優點是簡單不容易出錯，缺點是復雜度有時很高，所以我們可以在窮舉法的基礎上進行改進，這樣能達到一舉雙得的效果。
Backtracking(
回溯法) 是 Brute fore搜索算法的一種，它通常用最簡單的遞歸方法來實現，在最壞的情況下，回溯法會導致一次復雜度為指數時間的計算。其比較經典的運用是：N皇后問題。
其次，數據結構有時候會決定算法，例 Transform & conquer。
另外在TopLanguage上看到的一些有用的觀點：
1. 算法里面極大一部分內容是如何有效地進行搜索，這里的"有效"可以分為：避免不必要的計算（如A*尋路以及所有的啟發式剪枝），緩存重復計算（如所有的動 態規劃）。
2.本質上，練習并不產生新能力。然而練習最重要的一個作用就是將
外顯記憶轉化為
內隱記憶。用大白話來說就是將平時需要用腦子去想（參與）的東西轉化為內在的習慣。譬如我們一開始學騎自行車的時候需要不斷提醒自己注意平衡，但隨著不斷的聯系，這種技能就內化成了所謂的
程序式記憶 這就是熟能生巧吧。
posted on 2011-08-24 21:39
hex108 閱讀(613)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm