1樓：
基本不等式吧。假設假設解決輸入size為的問題的開銷為而且，是乙個嚴格遞增的函式。
這個顯然不斷細分下去，每次最優解都是在的時候求得。
2樓：
除去前面一些答主講的數學原因之外，我覺得還有一點就是目前的指令結構。通常基本指令是兩數比較。二中選一就是一次比較，而並沒有三選一的指令，三選一必須比較2次。
所以三分在實現上就是兩次2分，其中有一次還切偏了。而兩次2分可以細化到1/4的範圍了，當然比三分要好。
3樓：李陶冶
lz這個算冪的方法還真未必是最優的，印象中還有因子法和加法鏈法（在事先知道某些條件的情況下也許效果更好），因為涉及大數運算，所以常數級的微小差別也會被考慮進去（我自己是不喜歡考慮常數級差別的，但確實有不少喜歡研究細節問題的人）。不過二分及二分的思想，確實是演算法設計中最重要也是最有趣的一部分。我印象中只在少數問題上見到過比二分更有效率的方法，比如牛頓迭代、內插法、大數以及矩陣乘法的分治。
4樓：
就你的具體例子：
二分時所需的乘法次數大約為： log(b) / log(2) = 1.44 log(b)
3分時所需的乘法次數大約為： log(b) / log(3) * 2 = 1.82 log(b) //因為需要把3個數相乘，需要兩次乘法。
可以證明這個 log(b) / log(k) * k 在 k>=3的時候是單調遞增的，所以k=2時所需的乘法次數最少。
大部分二分演算法都可以按這個思路證明。
注意這裡只考慮最少的乘法次數。實際上，很多演算法和資料結構都是k分的，而不是二分，例如 B-tree，外部排序等等。另外，當資料規模較小的時候，二分的演算法實現的效率往往會反而不好，例如在資料量小的時候插入排序等O(n^2)的排序演算法，反而比O(nlogn)的快速排序和歸併排序要快。
所以，要具體問題具體分析。沒有「最優」。
東方文明和西方文明是否是「二分法」
把人類文明分為 西方文明 與 東方文明 是典型的二分法。有 西方文明 圖中深藍色 但是沒有 東方文明 在人文上的東方 東亞 南亞 東南亞 有 日本文明 粉色 中華文明 紅色 佛教文明 黃色 印度教文明 橙色 伊斯蘭文明 綠色 等五大文明。 東方文明一般指東亞文明圈，西方文明一般指歐洲文明圈 此外還有...
二分法求函式的零點，如何確定初始區間，使得該區間能覆蓋所有的零點？
Moore Donnely 確定不了。二分法本來就不是萬能的,就算你找到了乙個包含所有根的區間又怎麼樣，你還是沒有辦法把所有根全解出來。舉個例子，考慮乙個三次函式f x x 3 1 3 x 2 x 1 12,你發現f 1 f 1 0,說明函式在 1,1 上至少有乙個根。然後你就用二分法求這個函式的根...
三門問題為什麼不是二分之一？
好好逛逛 這裡三個門，兩個是羊 乙個是車 很顯然你抽到羊的概率是2 3，抽到車的概率是1 3假設你抽到了羊，你換了 得到車 假設你抽到了車，你換了 得到羊 換句話說，假如你抽了之後換，得到車的概率就是2 3，因為你抽到羊的概率是2 3。 火花 假設你選擇的是1號門，主持人開啟一扇有羊的門，有以下幾種...