算法合集之《減少冗余與算法優(yōu)化》.ppt

湖南省長(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ì)使算法和程序效率提高很多去除