最近發(fā)現(xiàn)倍增講的很少，這可以理解為二分新姿勢！

我們設(shè)想一個背景，公主被邪惡的王八抓走了，馬里奧大叔這次要去救公主了，如果他到的不及時公主就要被殺死了，他能抱得美人歸嗎？馬里奧有一種神奇的能力，它可以在一秒鐘之內(nèi)走任意距離！已經(jīng)知道了王八城堡很高，在哪里都能看見！

憨批馬里奧：地球是圓的，我向相反的方向走，額。。。走多少米呢？不知道唉，于是他走了N圈地球后公主被殺了。

淳樸馬里奧：我每次直走一米，我一定不會錯過，那我每次走兩米，也不會錯過太多，那要是我一開始走三步，然后走一步也不會超過太多，到底怎么走呢？只能摸索的前進了，過了倒回來，于是公主也被殺了。

倍增馬里奧：我第一次走1米，第二次我走2米，第三次我走4米。。。。。。。第N我走2^(n-1)米，要是我走過了那么我會在少走一半，要是在多走，我會回去少走一半，那么 次方式 的增長所需要時間絕對是少的，于是他拯救公主成功了，怎么成功的呢？我們看看他的策略：

雖然在這里我們還是覺得他的操作次數(shù)太多了，但是當這個距離很長的時候，按指數(shù)倍增長后?的次數(shù)不會多很多，就像1000最大也不過是9+9步，其實沒這么多10步多一點，這時候倍增的好處就體現(xiàn)出來了。

關(guān)于倍增比較基礎(chǔ)的算法就是ST表，靜態(tài)RMQ算法：戳這里

總結(jié)

以上是生活随笔為你收集整理的疯子的算法总结12--倍增的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。