疯子的算法总结12--倍增
最近發(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 洛谷 2016 战略游戏(树形DP)
- 下一篇: Linux的用户空间与内核空间是什么意思