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

湖南省長沙市長郡中學(xué)胡偉棟 減少冗余與算法優(yōu)化 減少冗余與算法優(yōu)化 要提高算法的效率 必須減少算法中的冗余 算法的目標(biāo) 用最少的時間解決問題 最高的效率 冗余 多余的或重復(fù)的操作 高效率 在搜索 遞推 動態(tài)規(guī)劃 中 都可能出現(xiàn)冗余 例1 整數(shù)拆分 問題描述 將整數(shù)N拆分成若干個整數(shù)的和 要求所拆分成的數(shù)必須是2的非負(fù)整數(shù)冪的形式 問有多少種拆分方案 如果兩個方案僅有數(shù)的順序不同 則它們算作同一種方案 當(dāng)N 5時 可以拆分成下面的形式 5 1 1 1 1 15 1 1 1 25 1 2 25 1 45有4種拆分方案 例1 整數(shù)拆分 樣例 例1 整數(shù)拆分 遞推的建立 用F i j 表示i拆分成若干個數(shù) 其中最大的數(shù)不超過2j的拆分方案數(shù) 遞推方程 遞推的表示 目標(biāo) 最大數(shù)是 最大數(shù)小于 初始值 例1 整數(shù)拆分 遞推復(fù)雜度 復(fù)雜度 時間復(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ù) 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時 第j行要計算的點數(shù)為2k 例1 整數(shù)拆分 減少冗余 當(dāng)N 2M M是非負(fù)整數(shù) 時 當(dāng)i x時 第i列要計算的點數(shù)與x的二進(jìn)制表示中最末的0的個數(shù)相等 12 102 112 1002 1012 1102 1112 10002 時間復(fù)雜度 O N 每列要計算的點是最下方連續(xù)的若干個點 需要計算的點 已知點 不必求出的點 例1 整數(shù)拆分 減少冗余 當(dāng)N 2M M是非負(fù)整數(shù) 時 在所有F x j j一定 x為變量 中 只要存儲x最大的一個即可 空間復(fù)雜度 O log2N 例1 整數(shù)拆分 減少冗余 當(dāng)N 2M時 可轉(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é) 冗余 時空復(fù)雜度較高 去除冗余后 時空復(fù)雜度相對很低 去除冗余 優(yōu)化本題的關(guān)鍵 例1 整數(shù)拆分 最后的思考 更優(yōu)秀的算法 Exploring 公式 例2 最大獎品價值 問題描述 有N 2級樓梯 分別用0至N 1編號 第1至N級樓梯上每級都放有一個獎品 每個獎品都有一個正的價值 如果某人從第0級開始 向上走M(jìn)步正好到達(dá)第N 1級樓梯 他將得到所走過的樓梯上的所有獎品 否則他將一無所獲 問能得到的獎品價值的和最大是多少 當(dāng)然 一步不可能走太多級樓梯 假設(shè)每步最多上K級 即最多從第i級走到第i K級 例2 最大獎品價值 數(shù)學(xué)模型 有一列數(shù)a0 a1 a2 aN aN 1其中a0 0a1 a2 a3 aN 0aN 1 0從中選M 1個數(shù) 使1 0 i0 i1 i2 iM N 1 2 i1 i0 i2 i1 i3 i2 iM iM 1 K3 最大 例2 最大獎品價值 動態(tài)規(guī)劃 狀態(tài)表示 用F i j 表示走i步到達(dá)第j級樓梯能得到的獎品的價值和的最大值 F i j max F i 1 x aj j k x j 時間復(fù)雜度 O NMK 例2 最大獎品價值 規(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 最大獎品價值 減少冗余 動態(tài)的考慮 每次要求的f1的一段都是變化的 每次會加入一個新元素 每次會刪除一個元素 堆 靜態(tài)的考慮 每次都是找f1中連續(xù)的一段 線段樹 log2K log2K NM NM 編程復(fù)雜度 O O 高 例2 最大獎品價值 減少冗余 f1 j k f1 j k 1 f1 a f1 b f1 j 1 f1 j a b j f1 a f1 b 對于任意af1 b 時 f1 a 才有用 f2 j f1 a1 f1 a2 f1 a3 f1 ar max j k a1 a2 a3 ar j 例2 最大獎品價值 減少冗余 數(shù)據(jù)結(jié)構(gòu) 刪除第一個元素 新增元素到最后一個位置 并維護(hù)這個數(shù)據(jù)結(jié)構(gòu)使它保持遞減的性質(zhì) 線性表 隊列 堆棧 f1 a1 f1 a2 f1 a3 f1 a4 f1 a5 f1 a6 f1 a7 f1 a8 x x 例2 最大獎品價值 時間復(fù)雜度 O NM 時間復(fù)雜度 例2 最大獎品價值 小結(jié) O NMK O NMlog2K O NMlog2K O NM 堆 線段樹 去除冗余 線性表 例2 最大獎品價值 小結(jié) 去除冗余 數(shù)據(jù)結(jié)構(gòu) 探索 分析 降低復(fù)雜度 選取一個最合適的數(shù)據(jù)結(jié)構(gòu) 總結(jié) 在算法設(shè)計和編程過程中 冗余的出現(xiàn)是難以避免的冗余是高效率的天敵 減少冗余 必然會使算法和程序效率提高很多去除