算法合集之淺談補(bǔ)集轉(zhuǎn)化思想在統(tǒng)計(jì)問題中的應(yīng)用-資料下載頁
2024-10-16 20:33本頁面
【正文】 交的編號(hào)最小的已擺放矩形。 補(bǔ)集轉(zhuǎn)化 為了做到這一點(diǎn)，我們只需采取如下算法： 依次處理每個(gè)已經(jīng)擺放的矩形，設(shè)當(dāng)前處理的矩形編號(hào)為 i。 在這個(gè)矩形周圍一一枚舉與它相交的擺放方案。 對(duì)于每個(gè)方案，再依次枚舉編號(hào)為 1,2,……(i 1)的矩形，判斷這些矩形能否與當(dāng)前枚舉的方案相交，如果發(fā)現(xiàn)有相交的情況，則此方案不能計(jì)入總數(shù) T，否則就將 T加 1。 補(bǔ)集轉(zhuǎn)化 根據(jù)結(jié)論三，與每個(gè)已擺放的 X行 Y列的矩形相交的擺放方案位于它周圍的一個(gè)矩形框內(nèi)，這個(gè)矩形框最多 2P+X行，最多 2Q+Y列。 再根據(jù)結(jié)論一，在其中擺放 P行 Q列的矩形最多只有 (P+X+1)*(Q+Y+1)種方案 。 由于每個(gè)矩形的大小均在 P*Q這樣的級(jí)別，所以總共需要處理的方案數(shù)規(guī)模為 O(P*Q*L) 。 對(duì)于每個(gè)方案，最多只需要枚舉 L－ 1個(gè)已擺放矩形判斷是否與之相交。 補(bǔ)集轉(zhuǎn)化 總共需要處理的方案數(shù)規(guī)模為 O(P*Q*L) 根據(jù)結(jié)論二，判斷兩個(gè)矩形是否相交的復(fù)雜度為 O(1)。 處理每個(gè)方案的復(fù)雜度為 O(L) 整個(gè)算法的復(fù)雜度僅為 O(P*Q*L2) 補(bǔ)集轉(zhuǎn)化 思維復(fù)雜度、編程復(fù)雜度較低 在時(shí)間復(fù)雜度上，大大領(lǐng)先于離散化的常規(guī)解法 小結(jié) 本題從正面考慮 ， 枚舉量太大 ， 所以常規(guī)的解法是采用離散化技巧來減少枚舉量 。 但是從反面考慮 ， 枚舉量就非常小了 。 補(bǔ)集轉(zhuǎn)化思想在這里起到的作用是 幫助我們選擇了合適的枚舉對(duì)象 ， 從而減少了枚舉量 。 總結(jié) 比較：兩個(gè)例子都是利用補(bǔ)集轉(zhuǎn)化思想解決統(tǒng)計(jì)問題 不同點(diǎn) 作用效果 意義價(jià)值 例一中 指導(dǎo)我們?cè)O(shè)計(jì)出了本質(zhì)不同的新算法 似乎是解決這個(gè)問題的唯一可行方法 例二中 只是通過改變枚舉對(duì)象減少了枚舉量 比常規(guī)方法更自然、更優(yōu)秀的另一種方法 相同點(diǎn) 求解目標(biāo) R較困難 求 R的補(bǔ)集 T以及 R、 T的總和 S相對(duì)較容易 總結(jié) 補(bǔ)集轉(zhuǎn)化思想應(yīng)用于統(tǒng)計(jì)問題的形式是多種多樣的 ， 可能從解決問題的各個(gè)方面幫助我們 。 補(bǔ)集轉(zhuǎn)化思想不僅可以應(yīng)用于一些非常規(guī)的統(tǒng)計(jì)問題 ， 而且對(duì)于一些常規(guī)算法能夠解決的問題 ， 應(yīng)用補(bǔ)集轉(zhuǎn)化思想也許可以做得更好 。 總結(jié) 補(bǔ)集轉(zhuǎn)化思想 ， 體現(xiàn)了 矛盾對(duì)立統(tǒng)一 ， 互相轉(zhuǎn)化 的一種哲學(xué)觀念 。 在統(tǒng)計(jì)問題中靈活地應(yīng)用補(bǔ)集轉(zhuǎn)化思想 ， 往往可以起到 “ 出奇制勝 ” 的效果 ， 而這就要求我們注意培養(yǎng)逆向思維的能力 ， 才能用好 、 用活補(bǔ)集轉(zhuǎn)化思想 。 值得注意的是 ， 利用補(bǔ)集轉(zhuǎn)化思想解決統(tǒng)計(jì)問題作為一種非常規(guī)的統(tǒng)計(jì)方法 ， 和一些常規(guī)的統(tǒng)計(jì)方法 、 技巧之間的關(guān)系是辨證的 。 雖然在本文的例子中 ， 補(bǔ)集轉(zhuǎn)化思想都優(yōu)于常規(guī)方法 ， 但是并不能認(rèn)為常規(guī)方法一定不如非常規(guī)方法 。 大多數(shù)的統(tǒng)計(jì)問題 ， 還是適合使用常規(guī)方法的 。 總結(jié) 只有將常規(guī)方法和非常規(guī)方法都靈活地掌握 ， 并對(duì)于具體問題選擇合適的方法 ， 才能夠游刃有余地解決統(tǒng)計(jì)問題 。 感謝 我的演講到此結(jié)束 ， 謝謝大家 ！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1