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