




已閱讀5頁(yè),還剩21頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
湖南省長(zhǎng)沙市長(zhǎng)郡中學(xué)胡偉棟 減少冗余與算法優(yōu)化 減少冗余與算法優(yōu)化 要提高算法的效率 必須減少算法中的冗余 算法的目標(biāo) 用最少的時(shí)間解決問題 最高的效率 冗余 多余的或重復(fù)的操作 高效率 在搜索 遞推 動(dòng)態(tài)規(guī)劃 中 都可能出現(xiàn)冗余 例1 整數(shù)拆分 問題描述 將整數(shù)N拆分成若干個(gè)整數(shù)的和 要求所拆分成的數(shù)必須是2的非負(fù)整數(shù)冪的形式 問有多少種拆分方案 如果兩個(gè)方案僅有數(shù)的順序不同 則它們算作同一種方案 當(dāng)N 5時(shí) 可以拆分成下面的形式 5 1 1 1 1 15 1 1 1 25 1 2 25 1 45有4種拆分方案 例1 整數(shù)拆分 樣例 例1 整數(shù)拆分 遞推的建立 用F i j 表示i拆分成若干個(gè)數(shù) 其中最大的數(shù)不超過2j的拆分方案數(shù) 遞推方程 遞推的表示 目標(biāo) 最大數(shù)是 最大數(shù)小于 初始值 例1 整數(shù)拆分 遞推復(fù)雜度 復(fù)雜度 時(shí)間復(fù)雜度 O Nlog2N 空間復(fù)雜度 O Nlog2N 1 i N1 j M 3 N 8 BF i j 1 AF i j 例1 整數(shù)拆分 當(dāng)N 2M M是非負(fù)整數(shù) 時(shí) 實(shí)際要計(jì)算的點(diǎn)數(shù) 1 2 22 23 24 2M 1 2M 1 N 1 F i j i j 遞推中的冗余 1 20 2 21 4 22 C 當(dāng)j M k時(shí) 第j行要計(jì)算的點(diǎn)數(shù)為2k 例1 整數(shù)拆分 減少冗余 當(dāng)N 2M M是非負(fù)整數(shù) 時(shí) 當(dāng)i x時(shí) 第i列要計(jì)算的點(diǎn)數(shù)與x的二進(jìn)制表示中最末的0的個(gè)數(shù)相等 12 102 112 1002 1012 1102 1112 10002 時(shí)間復(fù)雜度 O N 每列要計(jì)算的點(diǎn)是最下方連續(xù)的若干個(gè)點(diǎn) 需要計(jì)算的點(diǎn) 已知點(diǎn) 不必求出的點(diǎn) 例1 整數(shù)拆分 減少冗余 當(dāng)N 2M M是非負(fù)整數(shù) 時(shí) 在所有F x j j一定 x為變量 中 只要存儲(chǔ)x最大的一個(gè)即可 空間復(fù)雜度 O log2N 例1 整數(shù)拆分 減少冗余 當(dāng)N 2M時(shí) 可轉(zhuǎn)化成N 2M的形式求解 例1 整數(shù)拆分 減少冗余 設(shè)N 2M r 2M 1 N 2M 0 0 0 0 0 0 0 r 目標(biāo) F N M 1 F N M 例1 整數(shù)拆分 小結(jié) 冗余 時(shí)空復(fù)雜度較高 去除冗余后 時(shí)空復(fù)雜度相對(duì)很低 去除冗余 優(yōu)化本題的關(guān)鍵 例1 整數(shù)拆分 最后的思考 更優(yōu)秀的算法 Exploring 公式 例2 最大獎(jiǎng)品價(jià)值 問題描述 有N 2級(jí)樓梯 分別用0至N 1編號(hào) 第1至N級(jí)樓梯上每級(jí)都放有一個(gè)獎(jiǎng)品 每個(gè)獎(jiǎng)品都有一個(gè)正的價(jià)值 如果某人從第0級(jí)開始 向上走M(jìn)步正好到達(dá)第N 1級(jí)樓梯 他將得到所走過的樓梯上的所有獎(jiǎng)品 否則他將一無(wú)所獲 問能得到的獎(jiǎng)品價(jià)值的和最大是多少 當(dāng)然 一步不可能走太多級(jí)樓梯 假設(shè)每步最多上K級(jí) 即最多從第i級(jí)走到第i K級(jí) 例2 最大獎(jiǎng)品價(jià)值 數(shù)學(xué)模型 有一列數(shù)a0 a1 a2 aN aN 1其中a0 0a1 a2 a3 aN 0aN 1 0從中選M 1個(gè)數(shù) 使1 0 i0 i1 i2 iM N 1 2 i1 i0 i2 i1 i3 i2 iM iM 1 K3 最大 例2 最大獎(jiǎng)品價(jià)值 動(dòng)態(tài)規(guī)劃 狀態(tài)表示 用F i j 表示走i步到達(dá)第j級(jí)樓梯能得到的獎(jiǎng)品的價(jià)值和的最大值 F i j max F i 1 x aj j k x j 時(shí)間復(fù)雜度 O NMK 例2 最大獎(jiǎng)品價(jià)值 規(guī)劃中的冗余 從F i 1 到F i 的轉(zhuǎn)移 f1 j 表示F i 1 j f2 j 表示F i j f1 j k 1 f1 j k f1 j k 1 f1 j 3 f1 j 2 f1 j 1 f2 j 1 f2 j max max 例2 最大獎(jiǎng)品價(jià)值 減少冗余 動(dòng)態(tài)的考慮 每次要求的f1的一段都是變化的 每次會(huì)加入一個(gè)新元素 每次會(huì)刪除一個(gè)元素 堆 靜態(tài)的考慮 每次都是找f1中連續(xù)的一段 線段樹 log2K log2K NM NM 編程復(fù)雜度 O O 高 例2 最大獎(jiǎng)品價(jià)值 減少冗余 f1 j k f1 j k 1 f1 a f1 b f1 j 1 f1 j a b j f1 a f1 b 對(duì)于任意af1 b 時(shí) f1 a 才有用 f2 j f1 a1 f1 a2 f1 a3 f1 ar max j k a1 a2 a3 ar j 例2 最大獎(jiǎng)品價(jià)值 減少冗余 數(shù)據(jù)結(jié)構(gòu) 刪除第一個(gè)元素 新增元素到最后一個(gè)位置 并維護(hù)這個(gè)數(shù)據(jù)結(jié)構(gòu)使它保持遞減的性質(zhì) 線性表 隊(duì)列 堆棧 f1 a1 f1 a2 f1 a3 f1 a4 f1 a5 f1 a6 f1 a7 f1 a8 x x 例2 最大獎(jiǎng)品價(jià)值 時(shí)間復(fù)雜度 O NM 時(shí)間復(fù)雜度 例2 最大獎(jiǎng)品價(jià)值 小結(jié) O NMK O NMlog2K O NMlog2K O NM 堆 線段樹 去除冗余 線性表 例2 最大獎(jiǎng)品價(jià)值 小結(jié) 去除冗余 數(shù)據(jù)結(jié)構(gòu) 探索 分析 降低復(fù)雜度 選取一個(gè)最合適的數(shù)據(jù)結(jié)構(gòu) 總結(jié) 在算法設(shè)計(jì)和編程過程中 冗余的出現(xiàn)是難以避免的冗余是高效率的天敵 減少冗余 必然會(huì)使算法和程序效率提高很多去除
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 公司游戲線上活動(dòng)方案
- 公司美甲活動(dòng)策劃方案
- 公司文化曬單活動(dòng)方案
- 公司組織員工清雪活動(dòng)方案
- 公司每周團(tuán)體活動(dòng)方案
- 公司百日會(huì)戰(zhàn)活動(dòng)方案
- 公司搬遷慶祝活動(dòng)方案
- 公司日常野餐活動(dòng)方案
- 公司活動(dòng)全案策劃方案
- 公司百年慶典策劃方案
- 軍兵種知識(shí)課件稿
- 體外震波碎石術(shù)的護(hù)理
- EB病毒檢測(cè)技術(shù)進(jìn)展及臨床應(yīng)用
- 去極端化教育宣講
- 大學(xué)語(yǔ)文試題及答案4
- 發(fā)電廠2×150MW循環(huán)流化床空冷機(jī)組工程施工主要技術(shù)方案
- 移動(dòng)寬帶營(yíng)銷培訓(xùn)
- 2025年二級(jí)建造師礦業(yè)工程考試真題及答案
- 2025年上半年湖北恩施州事業(yè)單位統(tǒng)一考試公開招聘278人易考易錯(cuò)模擬試題(共500題)試卷后附參考答案
- 甘肅省蘭州市(2024年-2025年小學(xué)六年級(jí)語(yǔ)文)統(tǒng)編版小升初真題((上下)學(xué)期)試卷及答案
- 臨床常用降壓藥物
評(píng)論
0/150
提交評(píng)論