算法合集之《减少冗余与算法优化》.ppt
湖南省长沙市长郡中学 胡伟栋,减少冗余与算法优化,减少冗余与算法优化,要提高算法的效率，必须减少算法中的冗余,算法的目标：,用最少的时间解决问题,最高的效率,冗余：,多余的或重复的操作,高效率,在搜索、递推、动态规划中，都可能出现冗余,例1：整数拆分问题描述,将整数N拆分成若干个整数的和，要求所拆分成的数必须是2的非负整数幂的形式。问有多少种拆分方案？如果两个方案仅有数的顺序不同，则它们算作同一种方案。,当N=5时，可以拆分成下面的形式：5=1+1+1+1+15=1+1+1+25=1+2+25=1+45有4种拆分方案。,例1：整数拆分样例,例1：整数拆分递推的建立,用Fi,j表示 i 拆分成若干个数，其中最大的数不超过2 j的拆分方案数。,递推方程：,递推的表示：,目标：,最大数是,最大数小于,(初始值),例1：整数拆分递推复杂度,复杂度：,时间复杂度：,O(Nlog2N),空间复杂度：,O(Nlog2N),1iN 1j,M=3,N=8,BFi,j-1,AFi,j,例1：整数拆分,当N=2M(M是非负整数)时,实际要计算的点数：,1+2+22+23+24+2M-1=2M-1=N-1,Fi,j,i,j,递推中的冗余,1=20,2=21,4=22,C,当 j=M-k 时，第 j 行要计算的点数为 2k。,例1：整数拆分减少冗余,当N=2M(M是非负整数)时,当 i=x 时，第 i 列要计算的点数与 x 的二进制表示中最末的 0 的个数相等,1 2,10 2,11 2,100 2,101 2,110 2,111 2,1000 2,时间复杂度：,O(N),每列要计算的点是最下方连续的若干个点,需要计算的点,已知点,不必求出的点,例1：整数拆分减少冗余,当N=2M(M是非负整数)时,在所有 Fx,j(j一定,x为变量)中，只要存储 x 最大的一个即可。,空间复杂度：,O(log2N),例1：整数拆分减少冗余,当N2M时，,可转化成N=2M的形式求解,例1：整数拆分减少冗余,设N=2M-r(2M-1N2M),0,0,0,0,0,0,0,r,目标,FN,M-1,FN,M,例1：整数拆分小结,冗余,时空复杂度较高,去除冗余后,时空复杂度相对很低,去除冗余,优化本题的关键,例1：整数拆分最后的思考,更优秀的算法？,Exploring,公式？,.,例2：最大奖品价值问题描述,有N+2级楼梯，分别用0至N+1编号，第1至N级楼梯上每级都放有一个奖品，每个奖品都有一个正的价值。如果某人从第0级开始，向上走M步正好到达第N+1级楼梯，他将得到所走过的楼梯上的所有奖品，否则他将一无所获。问能得到的奖品价值的和最大是多少？当然，一步不可能走太多级楼梯，假设每步最多上K级，即最多从第 i 级走到第 i+K 级。,例2：最大奖品价值数学模型,有一列数 a0,a1,a2,aN,aN+1其中a0=0a1,a2,a3,aN0aN+1=0从中选M+1个数,，使1)0=i0i1i2 iM=N+1；2)i1-i0,i2-i1,i3-i2,iM-iM-1K3)最大,例2：最大奖品价值动态规划,状态表示：,用Fi,j表示走 i 步到达第 j 级楼梯能得到的奖品的价值和的最大值,Fi,j=maxFi-1,x+aj,j-kxj,时间复杂度：,O(NMK),例2：最大奖品价值规划中的冗余,从Fi-1到Fi的转移,f1j表示Fi-1,j,f2j表示Fi,j,f1j-k-1f1j-kf1j-k+1f1j-3f1j-2f1j-1,f2j-1,f2j,max,max,例2：最大奖品价值减少冗余,动态的考虑：,每次要求的 f1 的一段都是变化的,每次会加入一个新元素,每次会删除一个元素,堆,静态的考虑：,每次都是找 f1 中连续的一段,线段树,log2K,log2K,NM,NM,编程复杂度,O(),O(),高,例2：最大奖品价值减少冗余,f1j-k f1j-k+1 f1a f1b f1j-1f1j,a b j,f1af1b,对于任意a f1b时，f1a才有用,f2j,f1a1f1a2f1a3f1ar,max,j-ka1 a2 a3 arj,例2：最大奖品价值减少冗余,数据结构：,删除第一个元素,新增元素到最后一个位置，并维护这个数据结构使它保持递减的性质,线性表*,队列,堆栈,f1a1,f1a2,f1a3,f1a4,f1a5,f1a6,f1a7,f1a8,x,x,例2：最大奖品价值时间复杂度,O(NM),时间复杂度,例2：最大奖品价值小结,O(NMK),O(NMlog2K),O(NMlog2K),O(NM),堆,线段树,去除冗余,线性表*,例2：最大奖品价值小结,去除冗余,数据结构,探索,分析,降低复杂度,选取一个最合适的数据结构,总结,在算法设计和编程过程中，冗余的出现是难以避免的冗余是高效率的天敌，减少冗余，必然会使算法和程序效率提高很多去除冗余没有可套用的定理公式可用，只有认真分析、善于探索，并在做题中积累经验，才能得到去除冗余的好方法,总结,如果在做题时和做题后，思考一下，能否有更好的方法解决此题，此题还有冗余能去吗，必然会得到意想不到的收获。,谢谢,
