淺談三分法

本篇随筆簡單講解一下算法中的三分算法。

一、前置知識

要學三分的話，首先要對二分有一個了解和掌握。這是肯定的了。

尤其是二分答案，把求解轉化為判定。

剛剛已經提到過，二分答案是把求解轉化成判定，但是其有一個很重要的适用範圍：答案一定要滿足單調性。這很顯然。

但是如果答案函數就不是一個單調函數，而是一個類似于二次函數的波峰、波谷函數的話，怎麼辦呢？顯然，二分是無勇武之地的。

那就三分呗。

是的，三分法可以求解波峰波谷函數的極值問題。（怎麼感覺高中數學講過呢？）

三分其實就是每次把可行區間分成三等分，進行判斷後縮小區間的過程也是三分之一三分之一地縮小。是以其複雜度應該是以3為底的對數。這也不是很嚴格的。

那麼三分為什麼是對的呢？

現在你把可行區間分成了三份，因為隻有一個最值，那麼你的三等分點一定是同時處于答案一側或者分别處于答案兩側。這個時候顯然隻需要判斷兩個三等分點的函數值大小，決定函數值往左右移動即可。這個考場畫圖即可正确模拟。