4.二分，三分。

前幾天聽同學說，現(xiàn)在8K已經(jīng)招不到會寫二分的程序員了，當然這句話有夸張的成分啦，^-^ 可見二分在程序設計中的常用性。

其實這個可以并列到枚舉算法那中，只是這種枚舉效率很高，很多地方比如SQL數(shù)據(jù)庫里面的查找方式就是二分，二分枚舉，三分枚舉，時間復雜度都是對數(shù)級的，在程序設計中是相當高效的算法。

二分的條件：數(shù)據(jù)的單調(diào)性。 比如在一組從小到大排序的數(shù)中尋找數(shù)x 這樣就可以二分枚舉 每次可以把范圍縮小一半，無論數(shù)據(jù)多大，就算超出int類型，都能很快找出來。

比如求函數(shù)8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == K 在區(qū)間[0,100]的解 由于這個函數(shù)在[0,100]是單調(diào)遞增的，所以二分是個不錯的選擇。

三分的條件: 數(shù)據(jù)的有凸性。

比如求函數(shù)6*x^7 + 8*x^6 + 7*x^3 + 5*x^2 – K*x 在區(qū)間[0,100]的最小值

這個函數(shù)在[0,100]是一個先減后增(或者完全單調(diào)，主要看K)的函數(shù)，所以三分求解。

當然這個問題可以轉(zhuǎn)換為二分，將函數(shù)求導，二分其在0的位置即可，這個涉及到高等數(shù)學，不贅述了。

具體過程可以去查資料 二分前一般也需要排序操作的。

5.隨機算法

很多時候在要解決的問題沒有任何思路，枚舉數(shù)據(jù)量又太大的情況下，可以使用一些隨機算法。

常見的隨機算法，蟻群算法，模擬退火等等。

簡單說說模擬退火(后面我打算專門寫一篇模擬退火的隨筆)

比如平面內(nèi)有成千上萬個點，要在平面選一個圓，覆蓋所有點，問最小的半徑是多少?

第一次接觸這個問題的時候我有想到一種做法(不敢保證正確)：

根據(jù)1 還是可以得出結(jié)論，最優(yōu)情況圓上面一定有2個點，否則的話可以把圓繼續(xù)縮小平移，使它上面有2個點，結(jié)果更優(yōu)。

所以枚舉任意2個點，圓心一定在這2點中垂線上，這里是對的。 然后假設這個圓心在在中垂線上移動，如果滿足要求，包圍了所有點。

那么我猜測這個圓在移動過程中半徑先減小后增大。(感覺而已，未證明，也未測試，太麻煩了。) 這里可以使用上述的三分枚舉，因為半徑函數(shù)是下凸性的。

我上面這個方法正確性先不說，復雜度是有一點的，枚舉2點，再三分。O(n^2*logV) 當然，數(shù)據(jù)很小的情況下，比如只有幾千個點的話，結(jié)果秒出，數(shù)據(jù)大了，效率降低了。

這里說一下模擬退火的思想。 大概依照一個這樣的理論，假設現(xiàn)在有1個位置pos,如果最優(yōu)解圓心位置在pos上面，那么如果往pos下面搜，搜到的圓心一定比在pos的位置時候大。

依照這個理論，我們就可以現(xiàn)在平面內(nèi)隨機生成一些點，然后貪心的隨機移動它們，直到達到一定程度停止。這個算法在時間復雜度上是O(n)的 正確性很高，運行也相當?shù)目臁?/p>

6.最后一個問題轉(zhuǎn)化

有的時候遇到問題，不能立即想出策略，這個時候嘗試下將這個問題轉(zhuǎn)化為常見的模型，利用常見模型和經(jīng)典的算法解決它。

最常見的還是一些圖論上的問題，將實際問題轉(zhuǎn)化為流網(wǎng)絡或者二分圖。