算法合集之《一類(lèi)算法復(fù)合的方法》.ppt

《算法合集之《一類(lèi)算法復(fù)合的方法》.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、一類(lèi)算法復(fù)合的方法江蘇省揚(yáng)州中學(xué)張煜承問(wèn)題描述維護(hù)集合S，初始時(shí)為空。有N個(gè)操作需要依次處理BX在S中插入一個(gè)整數(shù)XAY詢(xún)問(wèn)S中被Y除余數(shù)最小的數(shù)，如果有多個(gè)則任取一個(gè)1≤N≤40000，1≤X,Y≤R=500000允許離線算法初步分析算法1：對(duì)詢(xún)問(wèn)中每個(gè)不同的Y，維護(hù)它對(duì)應(yīng)的詢(xún)問(wèn)當(dāng)前的答案時(shí)間復(fù)雜度為O(N2)，不能解決問(wèn)題但當(dāng)詢(xún)問(wèn)中出現(xiàn)的不同Y的個(gè)數(shù)比較少時(shí)會(huì)很快，時(shí)間復(fù)雜度可以寫(xiě)成O(不同Y的個(gè)數(shù)×N)進(jìn)一步分析當(dāng)遇到一個(gè)詢(xún)問(wèn)"AY"時(shí)，要在S中尋找使得xmodY最小的數(shù)x把這里的x寫(xiě)成kY+r，其中0≤r

2、最小的數(shù)kY+r算法2：枚舉k，找[kY,(k+1)Y)中的最小值。最后在這些最小值中取最優(yōu)的一個(gè)例子S={2,3,6,8}Y=5012345678910…最小值為2最小值為62mod5=26mod5=1因此取6現(xiàn)在的問(wèn)題：詢(xún)問(wèn)S中給定區(qū)間[a,b]內(nèi)的最小數(shù)可以看成是詢(xún)問(wèn)≥a的最小數(shù)q(a)012345678910…aq(a)222366688+∞+∞…對(duì)很多連續(xù)的a，q(a)是相等的形成了若干個(gè)區(qū)間假設(shè)X所在的區(qū)間為[s,t]，現(xiàn)在在S中插入X[s,t]被拆分成了區(qū)間[s,X]和[X+1,t]ss+1…X-1XX+1…t-1taq(a)tttttttttss+1

3、…X-1XX+1…t-1tXXXXXtttt只有插入操作，所以一直在拆分區(qū)間，而不合并區(qū)間讓時(shí)間倒流，把所有操作按照從后往前的順序處理，那么區(qū)間就一直都在被合并了并查集把這里每個(gè)區(qū)間看作是一個(gè)集合，并維護(hù)它們對(duì)應(yīng)的q每次操作近似地認(rèn)為是均攤O(1)算法2對(duì)一個(gè)詢(xún)問(wèn)“AY”，需要詢(xún)問(wèn)O(R/Y)個(gè)區(qū)間，最多O(R)個(gè)區(qū)間一次詢(xún)問(wèn)的時(shí)間復(fù)雜度高達(dá)O(R)總時(shí)間復(fù)雜度O(NR)，也不能解決問(wèn)題嘗試著優(yōu)化算法2的瓶頸在于一次詢(xún)問(wèn)需要處理的區(qū)間可能非常多，但只會(huì)發(fā)生在很少當(dāng)Y非常小的時(shí)候一個(gè)例子：當(dāng)Y>R0.5時(shí)，算法2已經(jīng)可以接受了我們可以對(duì)這部分很少的Y的詢(xún)問(wèn)使用另一種算法

4、算法1當(dāng)詢(xún)問(wèn)中的不同的Y很少時(shí)會(huì)很快，所以這里的另一種算法可以選擇算法1算法3設(shè)一個(gè)邊界值K對(duì)Y>K的詢(xún)問(wèn)使用算法2O(NR/K)對(duì)Y≤K的詢(xún)問(wèn)使用算法1O(NK)總時(shí)間復(fù)雜度O(NK+NR/K)將N和R看作常數(shù)，容易得出當(dāng)K=R0.5時(shí)總時(shí)間復(fù)雜度最小，為O(NR0.5)算法3可以完全解決本題我們解決本題的重點(diǎn)是：不使用統(tǒng)一的算法，而是同時(shí)使用這個(gè)問(wèn)題的兩種算法，分別解決問(wèn)題中的兩個(gè)互補(bǔ)的部分我的論文里還有另一個(gè)例子SPOJRECTANGL這個(gè)問(wèn)題同樣可以通過(guò)同時(shí)使用兩種不同的算法得到較好的解決總結(jié)一個(gè)問(wèn)題往往可以被看作是由若干個(gè)相對(duì)并列的部分組成起來(lái)的通常對(duì)這些部

5、分使用統(tǒng)一的算法而有時(shí)這個(gè)問(wèn)題可以使用多種算法解決，并且當(dāng)這些算法應(yīng)用在問(wèn)題中不同特征的部分時(shí)，會(huì)有不同的效果這時(shí)就可以將這些算法復(fù)合，對(duì)問(wèn)題的不同部分，根據(jù)它們的特征分別選擇使用對(duì)這個(gè)部分較優(yōu)的算法總結(jié)兩個(gè)算法合并起來(lái)后，很神奇地得到了一個(gè)更優(yōu)的算法這是因?yàn)檫@兩種算法具有互補(bǔ)的優(yōu)勢(shì)，而我們把問(wèn)題分成了若干部分，對(duì)每一部分根據(jù)其特征使用較優(yōu)的算法，就使得兩種算法的優(yōu)勢(shì)得到了結(jié)合總結(jié)每個(gè)算法都有各自的優(yōu)勢(shì)和劣勢(shì)如果我們?nèi)￠L(zhǎng)補(bǔ)短，充分利用它們的優(yōu)勢(shì)，也許就將會(huì)得出總體更優(yōu)的算法這種取長(zhǎng)補(bǔ)短的思想是非常重要的