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