算法合集之淺談補(bǔ)集轉(zhuǎn)化思想在統(tǒng)計(jì)問題中的應(yīng)用(參考版)
2024-10-19 20:33本頁面
【正文】 總結(jié) 只有將常規(guī)方法和非常規(guī)方法都靈活地掌握 ， 并對于具體問題選擇合適的方法 ， 才能夠游刃有余地解決統(tǒng)計(jì)問題 。 雖然在本文的例子中 ， 補(bǔ)集轉(zhuǎn)化思想都優(yōu)于常規(guī)方法 ， 但是并不能認(rèn)為常規(guī)方法一定不如非常規(guī)方法 。 在統(tǒng)計(jì)問題中靈活地應(yīng)用補(bǔ)集轉(zhuǎn)化思想 ， 往往可以起到 “ 出奇制勝 ” 的效果 ， 而這就要求我們注意培養(yǎng)逆向思維的能力 ， 才能用好 、 用活補(bǔ)集轉(zhuǎn)化思想 。 補(bǔ)集轉(zhuǎn)化思想不僅可以應(yīng)用于一些非常規(guī)的統(tǒng)計(jì)問題 ， 而且對于一些常規(guī)算法能夠解決的問題 ， 應(yīng)用補(bǔ)集轉(zhuǎn)化思想也許可以做得更好 。 補(bǔ)集轉(zhuǎn)化思想在這里起到的作用是 幫助我們選擇了合適的枚舉對象 ， 從而減少了枚舉量 。 處理每個(gè)方案的復(fù)雜度為 O(L) 整個(gè)算法的復(fù)雜度僅為 O(P*Q*L2) 補(bǔ)集轉(zhuǎn)化 思維復(fù)雜度、編程復(fù)雜度較低 在時(shí)間復(fù)雜度上，大大領(lǐng)先于離散化的常規(guī)解法 小結(jié) 本題從正面考慮 ， 枚舉量太大 ， 所以常規(guī)的解法是采用離散化技巧來減少枚舉量 。 對于每個(gè)方案，最多只需要枚舉 L－ 1個(gè)已擺放矩形判斷是否與之相交。 再根據(jù)結(jié)論一，在其中擺放 P行 Q列的矩形最多只有 (P+X+1)*(Q+Y+1)種方案 。 對于每個(gè)方案，再依次枚舉編號為 1,2,……(i 1)的矩形，判斷這些矩形能否與當(dāng)前枚舉的方案相交，如果發(fā)現(xiàn)有相交的情況，則此方案不能計(jì)入總數(shù) T，否則就將 T加 1。 補(bǔ)集轉(zhuǎn)化 為了做到這一點(diǎn)，我們只需采取如下算法： 依次處理每個(gè)已經(jīng)擺放的矩形，設(shè)當(dāng)前處理的矩形編號為 i。 補(bǔ)集轉(zhuǎn)化 符合規(guī)則的擺放方案數(shù) R+違反規(guī)則的擺放方案數(shù) T =總共的擺放方案數(shù) S 問題轉(zhuǎn)化為：怎樣高效地求出 T 根據(jù)結(jié)論一， S可以根據(jù)公式計(jì)算出來 T也就是所有與已經(jīng)擺放的軍艦相交的方案數(shù) 符合規(guī)則的擺放方案數(shù) R＝ 總共的擺放方案數(shù) S－違反規(guī)則的擺放方案數(shù) T 補(bǔ)集轉(zhuǎn)化 不能簡單地枚舉每一艘已經(jīng)擺放的軍艦，計(jì)算與它相交的擺放方案數(shù)并累加起來 。 幾個(gè)工具 當(dāng)然，這樣說還不是太嚴(yán)密，因?yàn)檫@個(gè)矩形框有可能超出了棋盤的邊界，此時(shí)它的邊就要調(diào)整到棋盤邊界內(nèi)。這個(gè)矩形框是在矩形 A的上、下各擴(kuò)展 P行，左、右各擴(kuò)展 Q列得到的。 如何判斷 A、 B是否相交 ？ 這個(gè)問題稍稍復(fù)雜一點(diǎn) ， 但是仔細(xì)分析各種情況之后可以得出 結(jié)論二 ： A和 B相交的充要條件是 (AX1=BX2+1) and (AX2=BX11) and (AY1=BY2+1) and (AY2=AY11)。 否則矩形 B的左上角可以位于矩形 A的 1至 XP+1行 ， 1至YQ+1列 ， 也就是總共有 (XP+1)*(YQ+1)種擺放方案 。 幾個(gè)工具 在進(jìn)一步地思考之前，我們先明確幾個(gè)小問題，以作為下面研究的工具 。 離散化的算法時(shí)間復(fù)雜度為 O(min{M,N}*L) 雖然對于原題勉強(qiáng)可以應(yīng)付，但是一旦數(shù)據(jù)規(guī)模再稍稍擴(kuò)大一點(diǎn)，必定超時(shí)。 這是典型的在有障礙點(diǎn)的網(wǎng)格上求擺放方案數(shù)的統(tǒng)計(jì)問題。如果要再擺一個(gè) 2行 2列的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1