算法合集之《减少冗余与算法优化》.ppt

《算法合集之《减少冗余与算法优化》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖南省长沙市长郡中学胡伟栋减少冗余与算法优化减少冗余与算法优化要提高算法的效率，必须减少算法中的冗余算法的目标：用最少的时间解决问题最高的效率冗余：多余的或重复的操作高效率在搜索、递推、动态规划……中，都可能出现冗余例1：整数拆分——问题描述将整数N拆分成若干个整数的和，要求所拆分成的数必须是2的非负整数幂的形式。问有多少种拆分方案？如果两个方案仅有数的顺序不同，则它们算作同一种方案。当N=5时，可以拆分成下面的形式：5=1+1+1+1+15=1+1+1+25=1+2+25=1+45有4种拆分方案。例1：整数拆分——样例例1：整数拆分——递推的建立用F[i,j]表示i拆分成若干个数，其中最大

2、的数不超过2j的拆分方案数。递推方程：递推的表示：目标：最大数是最大数小于(初始值)例1：整数拆分——递推复杂度复杂度：时间复杂度：O(Nlog2N)空间复杂度：O(Nlog2N)1≤i≤N1≤j≤≤JI123012345678M=3,N=8BF[i,j-1]AF[i,j]例1：整数拆分当N=2M(M是非负整数)时实际要计算的点数：1+2+22+23+24+……+2M-1=2M-1=N-1F[i,j]ij——递推中的冗余1=202=214=22C当j=M-k时，第j行要计算的点数为2k。例1：整数拆分——减少冗余当N=2M(M是非负整数)时当i=x时，第i列要计算的点数与x的二进制表示中最末

3、的0的个数相等12102112100210121102111210002时间复杂度：O(N)JI123012345678每列要计算的点是最下方连续的若干个点需要计算的点已知点不必求出的点JI123012345678例1：整数拆分——减少冗余当N=2M(M是非负整数)时在所有F[x,j](j一定,x为变量)中，只要存储x最大的一个即可。未知点处理中的点已知点不必求出的点空间复杂度：O(log2N)例1：整数拆分——减少冗余JI123012345678当N≠2M时，可转化成N=2M的形式求解例1：整数拆分——减少冗余设N=2M-r(2M-1

4、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其中a

5、0=0a1,a2,a3,…,aN>0aN+1=0从中选M+1个数…,，使1)0=i0

6、j-1]f2[j]maxmax例2：最大奖品价值——减少冗余动态的考虑：每次要求的f1的一段都是变化的每次会加入一个新元素每次会删除一个元素堆静态的考虑：每次都是找f1中连续的一段线段树log2Klog2KNMNM编程复杂度O()O()高例2：最大奖品价值——减少冗余f1[j-k]f1[j-k+1]…f1[a]…f1[b]…f1[j-1]f1[j]af1[b]时，f1[a]才有用f2[j]f1[a1]f1[a2]f1[a3]……f1[ar]>>>>maxj-k≤a1

7、构：删除第一个元素新增元素到最后一个位置，并维护这个数据结构使它保持递减的性质线性表*队列堆栈f1[a1]f1[a2]f1[a3]f1[a4]f1[a5]f1[a6]f1[a7]f1[a8]xx例2：最大奖品价值——时间复杂度O(NM)时间复杂度例2：最大奖品价值——小结O(NMK)O(NMlog2K)O(NMlog2K)O(NM)堆线段树去除冗余线性表*例2：最大奖品价值——小结去除冗余数据结构探索分析降低