RMQ(range ?minimum/maximum query)即查詢(xún)區(qū)間最大最小值。
對(duì)于求區(qū)間最大最小值,我們自然而然就想到了一個(gè)O(n)時(shí)間復(fù)雜度的算法,但是如果詢(xún)問(wèn)有很多呢?這樣必然超時(shí)。當(dāng)然我們可以用線(xiàn)段樹(shù)來(lái)解,使得每一次查詢(xún)的時(shí)間降到log(n),但是對(duì)于RMQ算法,只要我們做了些預(yù)處理,之后的查詢(xún)我們僅需要O(1)的時(shí)間。 Sparse_Table算法是解決RMQ問(wèn)題的一類(lèi)較好的算法, 屬于一種在線(xiàn)算法,至于什么叫在線(xiàn)什么叫離線(xiàn),先簡(jiǎn)單介紹一下。
在線(xiàn)算法: 在計(jì)算機(jī)科學(xué)中,一個(gè)在線(xiàn)算法是指它可以以序列化的方式一個(gè)個(gè)的處理輸入,也就是說(shuō)在開(kāi)始時(shí)并不需要已經(jīng)知道所有的輸入。
離線(xiàn)算法: 在開(kāi)始時(shí)就需要知道問(wèn)題的所有輸入數(shù)據(jù),而且在解決一個(gè)問(wèn)題后就要立即輸出結(jié)果。例如, 選擇排序 在排序前就需要知道所有待排序元素,然而 插入排序 就不必了。
簡(jiǎn)單的概括一下 在線(xiàn)算法就是說(shuō)程序先把預(yù)處理工作做好,對(duì)于之后的查詢(xún),可以很快給你答復(fù)。離線(xiàn)算法就是你先把需求告訴程序,他一次性給你解決 。
好了,下面來(lái)講解 Sparse_Table 算法
1.求最值數(shù)組
Sparse_Table 算法的預(yù)處理就是一個(gè)動(dòng)態(tài)規(guī)劃的思想。
設(shè)數(shù)組maxn[i][j] 表示給定的數(shù)組從下標(biāo)i開(kāi)始,長(zhǎng)度為2^j的區(qū)間最大值(最小值一樣)也就是arr[i]----arr[i+2^j-1]這個(gè)區(qū)間的最大值。
于是我們可以寫(xiě)出這樣一個(gè)動(dòng)態(tài)轉(zhuǎn)移方程maxn[i][j] = max(maxn[ i ][ j-1 ],maxn[ i+2^(j-1) ][ j-1 ]) 看懂了么?
其實(shí)就是把區(qū)間【i ,i+2^j -1】分成兩段,一段是【i,i+2^(j-1)-1】 和【i+2^(j-1),i+2^j】 (一直記住二維數(shù)組后面一維表示的是區(qū)間的長(zhǎng)度2^j)
那么對(duì)于maxn[i][j]當(dāng)j等于0,也就是區(qū)間長(zhǎng)度為1的最大值顯然就有maxn[i][0] = arr[i];
到此我們就可以寫(xiě)出 Sparse_Table 的預(yù)處理部分了
?
void getbestarr(int n)//n為給定的數(shù)組的長(zhǎng)度 { int tem = (int)floor(log2((double)n));//因?yàn)閰^(qū)間的最長(zhǎng)長(zhǎng)度是2^tem==n嘛 for(int i=1;i<=n;i++) minn[i][0]= maxn[i][0] = arr[i]; for(int j=1;j<=tem;j++) //下標(biāo)從1開(kāi)始 for(int i=1;i+(1<<j)-1<=n;i++) { maxn[i][j] = max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]); //最大值 minn[i][j] = min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]); //最小值 } }
我們看看這個(gè)動(dòng)態(tài)規(guī)劃方程是怎么求解這個(gè)maxn,minn數(shù)組的
?
要求區(qū)間長(zhǎng)度為2的肯定要先求出區(qū)間長(zhǎng)度為1的嘛 ?比如區(qū)間[1,2]只要在區(qū)間[1,1] ? [2,2]中取最值嘛 長(zhǎng)度為4的肯定要先算出長(zhǎng)度為2的嘛 比如求區(qū)間[6,9]的最值只要在區(qū)間[6,7] [8,9]中取最值嘛。。。。。。
所以最外層的循環(huán)就肯定是區(qū)間的長(zhǎng)度2^j次方咯 里面的循環(huán)應(yīng)該都看得懂吧。
2.查詢(xún)
這個(gè)最值區(qū)間的數(shù)組求出來(lái)了,下面就是查詢(xún)了?
比如要查詢(xún)區(qū)間[a,b]的最值 ?怎么求呢?
注意到我們的最值數(shù)組存的都是區(qū)間長(zhǎng)度為2^k(k=0,1,2,3.....)次方的最值
所以對(duì)于區(qū)間[a,b] 我們肯定要?jiǎng)澐譃閮蓚€(gè)區(qū)間長(zhǎng)度是2^x ?2^y的區(qū)間才可以直接利用我們得到的最值數(shù)組來(lái)求最值嘛
這里有兩個(gè)未知數(shù)不好求,我們可以直接取k,對(duì)于k滿(mǎn)足a+2^k-1=b ?k=log2(b-a+1) (注意這里不是a+2^k=b 還是那句話(huà),始終記得2^k是區(qū)間的元素的個(gè)數(shù)) 那么區(qū)間a,b的最大值不就是max(maxn[a][k],maxn[b-2^k+1][k])比如對(duì)于區(qū)間長(zhǎng)度為4的[3,6]求出k==2 于是最大值就是區(qū)間max(【3,6】,【3,6】)當(dāng)然我們不能能保證log2(a-b+1)就一定能得到一個(gè)整數(shù),但是這不要緊,比如對(duì)于區(qū)間長(zhǎng)度為5的【3,7】我們對(duì)log2(7-3+1)取整得到2,于是最大值就在
max(【3,6】,【4,7】),max函數(shù)里面前面那個(gè)maxn[a][k]就保證了我們的求最值的區(qū)間以a開(kāi)始,后面那個(gè)maxn[b-2^k+1][k]就保證了我們必然能夠以b為尾
?
int query(int a,int b,bool getwhat)//getwhat表示你是想取最大還是最小 { int k = log2(b-a+1); if(getwhat) return max(maxn[a][k],maxn[b-(1<<k)+1][k]); else return min(minn[a][k],minn[b-(1<<k)+1][k]); }
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
