1. 項目概述從“三分”到“凸函數(shù)”的精確求解在算法競賽和許多工程優(yōu)化問題中我們常常會遇到一類特殊的函數(shù)它們只有一個“谷底”或“峰頂”。想象一下你在山里找最低點或者在海面上找最高點你不需要走遍每一寸土地只需要用一種高效的策略逐步縮小搜索范圍。這就是“三分法”要解決的核心問題。它不是一個簡單的數(shù)值方法而是一個基于函數(shù)凸凹性質(zhì)的確定性搜索算法專門用于在連續(xù)區(qū)間上尋找單峰函數(shù)的極值點。我最初接觸它是在解決一些最優(yōu)路徑、資源分配和參數(shù)調(diào)優(yōu)的問題時發(fā)現(xiàn)暴力枚舉效率低下而導(dǎo)數(shù)法又因為函數(shù)形式復(fù)雜或不可導(dǎo)而無法應(yīng)用。三分法以其簡潔的思想和穩(wěn)定的性能成為了我工具箱里的常客。所謂“三分”顧名思義就是將當(dāng)前的搜索區(qū)間等分成三份通過比較兩個中間分界點的函數(shù)值來果斷地舍棄掉不可能包含最值的那三分之一區(qū)間。這個過程反復(fù)迭代區(qū)間迅速縮小直到滿足我們的精度要求。它解決的是這樣一個明確的需求給定一個在區(qū)間[l, r]上先嚴(yán)格單調(diào)增、后嚴(yán)格單調(diào)減或先減后增的函數(shù)f(x)找到那個讓f(x)取得最大值或最小值的x。這個“單峰”的性質(zhì)就是“凸函數(shù)”在此語境下的實際含義更嚴(yán)格地說用于找最小值的是凸函數(shù)找最大值的是凹函數(shù)。本文將為你徹底拆解這個算法的原理、實現(xiàn)細(xì)節(jié)、各種變體以及實戰(zhàn)中那些教科書上不會講的坑。無論你是正在備賽的選手還是遇到類似優(yōu)化問題的工程師這份“凸函數(shù)模板”的深度解析都能讓你不僅會套用更能理解其筋骨靈活應(yīng)用于各種場景。2. 算法核心原理與思路拆解2.1 為什么是“三分”—— 與二分法的本質(zhì)區(qū)別很多人熟悉二分法它用于在單調(diào)序列中查找目標(biāo)值。三分法可以看作是二分法在尋找函數(shù)極值問題上的一個類比和擴展。但它們有一個根本性的不同二分法依賴于區(qū)間的單調(diào)性而三分法依賴于區(qū)間的單峰性。二分法每次比較中點值與目標(biāo)值的關(guān)系總能舍棄一半?yún)^(qū)間因為它明確知道目標(biāo)在中點的左邊還是右邊。但對于一個單峰函數(shù)你只知道極值點在某處比較一個點的函數(shù)值無法告訴你極值點在其左還是右。例如對于一個“先增后減”的函數(shù)如果你在上升段取一個點函數(shù)值很大但極值點最大值既可能在它右邊繼續(xù)上升也可能在它左邊已經(jīng)過了頂點開始下降。單個點提供的信息不足以做出決策。于是三分法的智慧就體現(xiàn)出來了通過兩個點來探測函數(shù)的“走勢”。將區(qū)間[l, r]分為三段取兩個中間點m1 l (r - l) / 3和m2 r - (r - l) / 3。比較f(m1)和f(m2)如果f(m1) f(m2)對于找最大值的單峰函數(shù)先增后減說明峰值點不可能在m1的左邊。因為如果峰值在左邊那么從峰值到m1是下降的而m1到m2是上升的這與“先增后減”的定義矛盾。因此我們可以安全地將左端點l更新為m1舍棄[l, m1)這段區(qū)間。如果f(m1) f(m2)同理峰值點不可能在m2的右邊可以將右端點r更新為m2舍棄(m2, r]。如果f(m1) f(m2)那么峰值點一定在[m1, m2]之間我們可以同時收縮左右端點令l m1,r m2。這樣每一次迭代我們都能夠確保極值點始終留在新的、更小的區(qū)間內(nèi)并且區(qū)間長度以大約2/3的比例縮小。這是一種非常樸素而強大的“夾逼”思想。2.2 “凸函數(shù)”在算法中的具體含義在數(shù)學(xué)優(yōu)化中凸函數(shù)的定義涉及二階導(dǎo)數(shù)非負(fù)或Jensen不等式。但在三分法的實用語境下我們所說的“凸函數(shù)”通常指的是單峰函數(shù)。更準(zhǔn)確地當(dāng)我們尋找最小值時我們要求函數(shù)是凸函數(shù)形狀像碗U型。當(dāng)我們尋找最大值時我們要求函數(shù)是凹函數(shù)形狀像拱∩型。對于算法本身它只關(guān)心函數(shù)的單峰性質(zhì)在定義域內(nèi)存在唯一極值點且在該點左側(cè)函數(shù)單調(diào)右側(cè)函數(shù)單調(diào)方向相反。你的模板必須明確你是在找最大值還是最小值因為這決定了f(m1)和f(m2)比較后該舍棄哪一段區(qū)間。一個健壯的模板應(yīng)該能通過一個參數(shù)或簡單的邏輯切換來適應(yīng)這兩種情況。注意實際編程中很多“凸函數(shù)”并非嚴(yán)格的數(shù)學(xué)凸函數(shù)可能由多個分段函數(shù)組成但只要在搜索區(qū)間上滿足單峰性三分法就適用。這是其應(yīng)用廣泛的重要原因。2.3 算法流程與復(fù)雜度分析標(biāo)準(zhǔn)三分法的流程可以清晰地分為以下幾步初始化確定搜索區(qū)間[l, r]和精度要求eps例如1e-7。迭代收縮當(dāng)區(qū)間長度(r - l)大于eps時循環(huán)執(zhí)行 a. 計算兩個三等分點m1 l (r - l) / 3,m2 r - (r - l) / 3。 b. 計算函數(shù)值f(m1)和f(m2)。 c.根據(jù)尋找最值的類型進(jìn)行比較 - 找最小值若f(m1) f(m2)則r m2否則l m1。 - 找最大值若f(m1) f(m2)則l m1否則r m2。返回結(jié)果迭代結(jié)束后區(qū)間[l, r]內(nèi)的任意點通常取(lr)/2都可作為極值點的近似。時間復(fù)雜度每次迭代區(qū)間長度乘以2/3。假設(shè)初始區(qū)間長度為L要求最終長度小于eps則迭代次數(shù)k滿足L * (2/3)^k eps解得k ≈ log_{3/2}(L/eps)。這是一個對數(shù)復(fù)雜度效率非常高。例如對于L1000,eps1e-7迭代次數(shù)大約在 60-70 次左右?？臻g復(fù)雜度為O(1)只需要常數(shù)級別的變量存儲。3. 核心實現(xiàn)細(xì)節(jié)與模板解析3.1 浮點數(shù)三分模板針對連續(xù)函數(shù)這是最經(jīng)典的形式用于自變量為連續(xù)實數(shù)的函數(shù)。模板的核心在于循環(huán)條件和比較邏輯。// 尋找凸函數(shù)的最小值 double ternary_search_min(double l, double r) { const double eps 1e-10; // 精度根據(jù)題目要求調(diào)整 while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { r m2; // 最小值在 [l, m2] 區(qū)間 } else { l m1; // 最小值在 [m1, r] 區(qū)間 } } return (l r) / 2.0; // 返回近似極值點 } // 尋找凹函數(shù)的最大值 double ternary_search_max(double l, double r) { const double eps 1e-10; while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { l m1; // 最大值在 [m1, r] 區(qū)間 } else { r m2; // 最大值在 [l, m2] 區(qū)間 } } return (l r) / 2.0; }關(guān)鍵細(xì)節(jié)與解釋精度eps的選擇這是浮點數(shù)三分的靈魂。eps太小可能因浮點數(shù)精度問題陷入無限循環(huán)或產(chǎn)生誤差eps太大結(jié)果不精確。通常如果答案要求輸出小數(shù)點后k位eps可以設(shè)為1e-(k2)。例如要求輸出6位小數(shù)eps1e-8是個穩(wěn)妥的選擇。有時也采用固定迭代次數(shù)如循環(huán)100次來替代精度判斷這樣更穩(wěn)定。中間點計算務(wù)必使用l (r - l) / 3.0而非l (r - l) / 3后者在C/C中會導(dǎo)致整數(shù)除法。更安全的寫法是m1 l (r - l) / 3和m2 r - (r - l) / 3因為(r-l)是浮點數(shù)除以整數(shù)3會得到浮點結(jié)果。函數(shù)f的實現(xiàn)f(x)需要根據(jù)具體問題實現(xiàn)。它可能是一個簡單的數(shù)學(xué)表達(dá)式也可能是一個需要復(fù)雜模擬的過程如計算某種配置下的代價。確保f(x)在[l, r]上是單峰的這是算法正確的前提。3.2 整數(shù)三分模板針對離散函數(shù)當(dāng)自變量是整數(shù)或者函數(shù)定義在整數(shù)域上時我們需要整數(shù)三分。因為區(qū)間長度是整數(shù)當(dāng)區(qū)間縮小到很短時m1和m2可能重合需要不同的處理邏輯。// 在整數(shù)區(qū)間 [l, r] 上尋找凸函數(shù)的最小值 int ternary_search_int_min(int l, int r) { while (r - l 2) { // 當(dāng)區(qū)間長度大于2時循環(huán) int m1 l (r - l) / 3; int m2 r - (r - l) / 3; if (f(m1) f(m2)) { r m2; } else { l m1; } } // 區(qū)間長度小于等于3暴力枚舉剩余點 int min_val f(l); int ans l; for (int i l 1; i r; i) { int val f(i); if (val min_val) { min_val val; ans i; } } return ans; }整數(shù)三分的特殊之處循環(huán)條件常用while (r - l 2)。因為當(dāng)區(qū)間長度小于等于3時兩個三分點m1和m2可能相等或無法有效分割區(qū)間此時直接暴力枚舉區(qū)間內(nèi)所有整數(shù)點更簡單可靠。中間點計算使用整數(shù)除法。由于是整數(shù)(r-l)/3會向下取整。這保證了m1和m2是整數(shù)且l m1 m2 r。最終處理循環(huán)結(jié)束后區(qū)間[l, r]通常只剩下2到3個點。對這些點逐一計算函數(shù)值并比較得到最終的最優(yōu)整數(shù)解。這是確保結(jié)果正確的關(guān)鍵步驟。3.3 通用模板與參數(shù)化設(shè)計一個更通用的模板可以整合尋找最大值和最小值甚至允許自定義比較函數(shù)提高代碼復(fù)用率。// 通用三分模板 // cmp: 一個函數(shù)接受兩個double/整數(shù)參數(shù)a,b當(dāng)a優(yōu)于b時返回true。 template typename T, typename Func T ternary_search(T l, T r, Func f, bool (*cmp)(T, T)) { const double eps 1e-10; // 對于浮點數(shù) while (r - l eps) { // 整數(shù)版本需改為 while (r - l 2) T m1 l (r - l) / 3; T m2 r - (r - l) / 3; if (cmp(f(m1), f(m2))) { // 如果f(m1)比f(m2)更優(yōu)根據(jù)三分邏輯更新端點 // 對于找最小值更優(yōu)意味著更小cmp less // 對于找最大值更優(yōu)意味著更大cmp greater // 更新邏輯需要根據(jù)cmp的具體含義來寫通常需要特化 // 更實用的寫法是下面兩個特化版本 } else { // 更新另一個端點 } } return (l r) / 2; } // 實踐中更清晰的寫法是提供兩個特化函數(shù) double ternary_search_min(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) r m2; else l m1; } return (l r) / 2; } double ternary_search_max(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) l m1; else r m2; } return (l r) / 2; }4. 實戰(zhàn)應(yīng)用場景與問題剖析三分法模板之所以重要是因為它能解決一系列看似棘手的問題。下面結(jié)合幾個典型場景看看如何將問題抽象成單峰函數(shù)求極值。4.1 場景一距離最值問題如“燈泡人”問題問題描述在一條數(shù)軸上有n個點其位置為a[i]?，F(xiàn)在要在這條數(shù)軸上找一個點x使得這個點到所有n個點的距離之和f(x) Σ|a[i] - x|最小。這是經(jīng)典的絕對值和最小問題最優(yōu)解是中位數(shù)。但如果代價不是距離而是距離的平方和f(x) Σ(a[i] - x)^2呢最優(yōu)解是平均數(shù)。如果代價是更復(fù)雜的函數(shù)比如f(x) Σ sqrt((a[i] - x)^2 C)C為常數(shù)這就沒有簡單的解析解了。抽象與求解函數(shù)f(x) Σ sqrt((a[i] - x)^2 C)是一個凸函數(shù)可以證明其二階導(dǎo)非負(fù)。因此我們可以直接在數(shù)軸的可能范圍例如[min(a[i]), max(a[i])]內(nèi)使用三分法尋找最小值點x。實現(xiàn)時只需編寫計算f(x)的函數(shù)然后套用浮點數(shù)三分求最小值的模板即可。實操心得這類問題的關(guān)鍵在于確定搜索區(qū)間[l, r]。通常極值點不會超出數(shù)據(jù)點的范圍所以將l設(shè)為min(a[i])r設(shè)為max(a[i])是安全的起點。有時根據(jù)問題物理意義區(qū)間可能需要適當(dāng)擴大。4.2 場景二最優(yōu)參數(shù)搜索如機器學(xué)習(xí)中的超參數(shù)調(diào)優(yōu)問題描述假設(shè)你有一個機器學(xué)習(xí)模型其性能如準(zhǔn)確率是某個連續(xù)超參數(shù)λ例如正則化系數(shù)的函數(shù)P(λ)。通過實驗?zāi)惆l(fā)現(xiàn)P(λ)隨著λ從0開始增大先上升后下降形成一個單峰曲線。你需要找到使準(zhǔn)確率最高的λ。抽象與求解將P(λ)視為定義在λ的合理范圍如[0, 10]上的函數(shù)。由于它是單峰的我們可以用三分法來搜索最優(yōu)的λ。這里的f(λ)就是模型在參數(shù)λ下的評估指標(biāo)計算函數(shù)可能涉及訓(xùn)練和驗證計算代價較高。注意事項計算成本每次計算f(λ)都可能需要重新訓(xùn)練或驗證模型非常耗時。因此在設(shè)定三分精度eps時要權(quán)衡精度和計算成本?？赡苤恍枰械染染湍苷业阶銐蚝玫某瑓?shù)。非嚴(yán)格單峰實際中的P(λ)可能不是嚴(yán)格的單峰可能存在多個局部極值。三分法只能找到局部最優(yōu)且依賴于初始區(qū)間。在這種情況下三分法可能不如網(wǎng)格搜索或隨機搜索可靠。因此在將三分法應(yīng)用于此類問題前務(wù)必通過初步實驗驗證函數(shù)在選定區(qū)間上的單峰性。4.3 場景三幾何最值問題如“穿越沙漠”問題描述一個經(jīng)典問題是從點A到點B中間需要經(jīng)過一條直線L。在A和B位于直線同側(cè)的情況下求從A到B經(jīng)過直線L上一點P的最短路徑。這是一個光的反射原理問題解是使得入射角等于反射角的點。但如果速度在直線兩側(cè)不同呢問題就變成了在直線L上找一點P最小化|AP|/v1 |PB|/v2v1,v2為速度。抽象與求解設(shè)P點的坐標(biāo)由其在直線上的某個參數(shù)t表示例如P A0 t * dir其中A0是直線上一點dir是方向向量。那么總時間T(t) |A - P(t)| / v1 |B - P(t)| / v2?？梢宰C明T(t)是關(guān)于t的凸函數(shù)。因此我們可以對參數(shù)t在其有效范圍內(nèi)進(jìn)行三分搜索尋找使T(t)最小的t。實現(xiàn)技巧計算f(t)時涉及距離計算。確保距離函數(shù)正確并且參數(shù)t的搜索區(qū)間[l, r]涵蓋了所有可能的P點通?？梢酝ㄟ^幾何關(guān)系確定。由于是連續(xù)函數(shù)使用浮點數(shù)三分模板。5. 常見陷阱、調(diào)試技巧與優(yōu)化5.1 陷阱一函數(shù)非單峰這是三分法失敗的最主要原因。如果函數(shù)在搜索區(qū)間內(nèi)有多個極值點多峰三分法很可能會收斂到某個局部極值點而非全局最優(yōu)。排查與驗證繪制函數(shù)圖像如果可能在應(yīng)用三分法前用程序在搜索區(qū)間內(nèi)以較粗的粒度采樣并繪制f(x)的曲線圖直觀檢查單峰性。隨機測試在區(qū)間內(nèi)隨機選擇大量的點對(x1, x2, x3)且x1 x2 x3檢查是否滿足凸性條件對于最小化問題f(x2) max(f(x1), f(x3))應(yīng)大致成立。如果大量違反則函數(shù)非凸。領(lǐng)域知識從問題本身分析。很多物理、幾何問題天然具有凸性。經(jīng)濟(jì)學(xué)的效用函數(shù)、距離的度量等也常常是凸的。5.2 陷阱二浮點數(shù)精度與循環(huán)終止浮點數(shù)運算存在精度損失。如果eps設(shè)置得過小如1e-15可能會因為浮點數(shù)誤差導(dǎo)致r - l始終無法小于eps從而陷入無限循環(huán)或提前終止在錯誤的位置。解決方案設(shè)置合理的eps根據(jù)問題對答案的精度要求來設(shè)定。通常比輸出要求高2個數(shù)量級足夠安全。使用迭代次數(shù)限制這是更穩(wěn)健的做法。根據(jù)對數(shù)復(fù)雜度預(yù)先計算一個足夠的迭代次數(shù)。double ternary_search_min(double l, double r) { for (int i 0; i 100; i) { // 循環(huán)100次精度足夠高 double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) { r m2; } else { l m1; } } return (l r) / 2; }循環(huán)100次區(qū)間長度將縮小到原來的(2/3)^100 ≈ 2.5e-18倍對于絕大多數(shù)問題都綽綽有余。避免直接比較浮點數(shù)相等在比較f(m1)和f(m2)時如果擔(dān)心精度問題可以使用f(m1) eps f(m2)這樣的比較方式但通常直接比較在三分法中問題不大因為決定方向的是大小關(guān)系而非精確相等。5.3 陷阱三整數(shù)三分的邊界處理在整數(shù)三分中當(dāng)區(qū)間長度很小時m1和m2可能相等。如果此時仍然按照f(m1)和f(m2)的比較來更新區(qū)間會導(dǎo)致區(qū)間無法繼續(xù)收縮。正確做法如前文模板所示當(dāng)r - l 2時跳出主循環(huán)然后暴力枚舉區(qū)間[l, r]內(nèi)的所有整數(shù)點。這是最安全、最清晰的做法。切勿嘗試在m1 m2時進(jìn)行特殊邏輯處理那樣容易出錯。5.4 調(diào)試技巧打印日志在循環(huán)內(nèi)打印l, r, m1, m2, f(m1), f(m2)的值。觀察區(qū)間是否在穩(wěn)步縮小以及函數(shù)值的比較是否符合你對函數(shù)形狀的預(yù)期。驗證單峰性在最終區(qū)間內(nèi)或隨機點上多計算幾個f(x)的值檢查是否滿足“先減后增”或“先增后減”的規(guī)律。與暴力枚舉對比對于小范圍問題可以寫一個暴力枚舉所有可能解以很小步長采樣的程序?qū)⑷址ǖ慕Y(jié)果與暴力枚舉的結(jié)果進(jìn)行對比驗證正確性。檢查函數(shù)實現(xiàn)確保你編寫的f(x)函數(shù)是正確的。這是三分法的基礎(chǔ)往往錯誤就出在這里。特別是當(dāng)f(x)涉及復(fù)雜計算或模擬時要單獨測試這個函數(shù)。5.5 性能優(yōu)化三分法本身已經(jīng)非常高效。優(yōu)化點主要在于昂貴的f(x)計算記憶化如果f(x)是純函數(shù)且計算昂貴可以考慮緩存記憶化已經(jīng)計算過的x對應(yīng)的f(x)值。但在三分法中x是連續(xù)值很難直接命中緩存除非離散化。并行計算在一次迭代中f(m1)和f(m2)的計算是獨立的可以并行進(jìn)行以提升速度。縮小初始區(qū)間盡可能利用問題性質(zhì)縮小[l, r]的初始范圍減少迭代次數(shù)。例如通過求導(dǎo)、不等式分析或粗略估計確定極值點的大致位置。6. 模板的變體與擴展6.1 黃金分割法三分法將區(qū)間分成三等份。一個自然的想法是有沒有更優(yōu)的分割比例黃金分割法0.618法就是一種選擇它每次迭代將區(qū)間長度縮小到原來的約0.618倍黃金分割比。與三等分相比黃金分割法的優(yōu)勢在于它每次迭代只需要計算一個新的函數(shù)值因為其中一個點可以復(fù)用上一次迭代的點而三分法需要計算兩個新值。當(dāng)f(x)計算非常昂貴時黃金分割法更有優(yōu)勢。double golden_section_search(double l, double r) { const double phi (sqrt(5) - 1) / 2; // 約 0.618 double m1 r - phi * (r - l); double m2 l phi * (r - l); double f1 f(m1), f2 f(m2); while (r - l eps) { if (f1 f2) { // 找最小值 r m2; m2 m1; f2 f1; m1 r - phi * (r - l); f1 f(m1); } else { l m1; m1 m2; f1 f2; m2 l phi * (r - l); f2 f(m2); } } return (l r) / 2; }6.2 自適應(yīng)三分與牛頓法對于導(dǎo)數(shù)容易求得的凸函數(shù)牛頓法或梯度下降法的收斂速度更快二階收斂。但三分法的優(yōu)勢在于不需要導(dǎo)數(shù)信息適用性更廣。有一種混合策略先使用幾次三分法快速縮小區(qū)間然后在足夠小的區(qū)間內(nèi)使用牛頓法進(jìn)行精確求解。這結(jié)合了三分法的穩(wěn)健性和牛頓法的快速收斂性。6.3 高維空間的最優(yōu)值搜索標(biāo)準(zhǔn)的二分法和三分法只適用于一維搜索。對于多維變量的凸函數(shù)優(yōu)化我們需要其他方法如梯度下降、共軛梯度法或更高級的優(yōu)化算法。然而有時多維問題可以轉(zhuǎn)化為一系列一維問題例如坐標(biāo)輪換法每次固定其他變量只優(yōu)化一個變量這時就可以在該維度上使用一維搜索方法包括三分法。7. 從理解到精通思維訓(xùn)練與題目推薦要真正掌握三分法不能只停留在套模板。我建議通過以下步驟進(jìn)行思維訓(xùn)練證明單峰性拿到一個問題首先嘗試從數(shù)學(xué)上證明或至少說服自己目標(biāo)函數(shù)在搜索區(qū)間上是單峰的。思考它的導(dǎo)數(shù)符號變化或者利用幾何意義、不等式來論證。手動模擬對于一個小例子用紙筆手動模擬三分法的迭代過程感受區(qū)間是如何一步步縮小的。修改模板嘗試自己編寫支持尋找最大值、最小值的統(tǒng)一模板并增加對整數(shù)域和浮點數(shù)域的支持。解決變體問題嘗試解決一些三分法的變體問題例如尋找一個函數(shù)滿足f(x) target的x如果函數(shù)是單調(diào)的用二分如果是凸的可能需要結(jié)合三分和函數(shù)值比較。經(jīng)典練習(xí)題推薦可在各大在線判題平臺搜索基礎(chǔ)/模板題直接考察三分法實現(xiàn)通常給出一個明顯的凸函數(shù)讓你求極值點。距離問題變種如前面提到的帶權(quán)距離和、復(fù)雜距離函數(shù)如加上平方根的最小化問題。幾何問題光線傳播、最佳觀測點、最短時間路徑等問題常能轉(zhuǎn)化為凸函數(shù)優(yōu)化。物理問題涉及能量、時間最優(yōu)的問題往往具有凸性。經(jīng)濟(jì)模型一些簡單的成本、收益模型在特定假設(shè)下也是凸的。最后記住三分法是一個工具它的威力在于將“尋找最優(yōu)”這個模糊的目標(biāo)轉(zhuǎn)化為一個可以通過機械迭代精確逼近的過程。當(dāng)你遇到一個求最值的問題并且感覺函數(shù)值隨著參數(shù)變化是“先好后壞”或“先壞后好”時不妨想想這會不會是一個單峰函數(shù)能不能用三分法來試試這種思維習(xí)慣的養(yǎng)成比記住十個模板更有價值。在實際編碼中我習(xí)慣將三分法函數(shù)封裝好并附上清晰的注釋說明是用于找最大值還是最小值輸入?yún)^(qū)間和精度要求是什么。這樣在競賽或項目遇到相關(guān)問題時我可以像調(diào)用庫函數(shù)一樣快速、準(zhǔn)確地應(yīng)用它把精力集中在問題建模和函數(shù)f(x)的實現(xiàn)上。