先队列及其应用.ppt

分析(2) f(i)=min{f(j)+|A(j+1)-(i-j-1)|} 其中1=jI 我们将决策分成两类，即： 第一类决策：A(j+1)-(i-j-1)0?iA(j+1)+j+1 第二类决策：A(j+1)-(i-j-1)=0?iA(j+1)+j+1 如果分开计算f(i)： 对于第一类：f(i)=min{f(j)+A(j+1)+j+1}-i 对于第二类：f(i)=min{f(j)-A(j+1)-j-1}-i * 分析(3) 我们将两类决策分开计算。 随着i的增加，会有一些决策从第一类转到第二类。 我们用两个二叉堆维护两类决策，用对于第一类决策用f(j)+A(j+1)+j+1作为关键字，第二类决策用f(j)-A(j+1)-j-1作为关键字。 二叉堆可以进行的操作有：插入元素、删除元素、取最值。 * 分析(4) 两个特殊处理： 预处理：计算每个决策在什么时候从第一类转到第二类 记录每个决策在堆中的位置，这样查找的时间复杂度就是O(1) 优化后的时间复杂度为O(nlogn) 思考：还有没有更好的算法？ * 合并操作例 13放入结果队列 * 两个B1合并为B2 * 最终结果 三个B2，两个合并变为B3，一个保留 O(logN) * 插入操作 最坏情况O(logN) 精确：最低位起，第一个0在第i位，则运行时间正比于i+1 每位为0的概率为1/2?平均情况O(1) * 例：将1至7插入空二项队列 * DeleteMin 先找到具有最小根的二项树Bk，O(logN) 将Bk从二项队列中去掉，得到新的二项队列H’ 将Bk的根去掉，其子树构成二项队列H’’ 将H’和H’’合并即可，O(logN) * DeleteMin例 显然应该删除B3的根12 * DeleteMin例（续） H’和H’’为 * DeleteMin例（续） H’和H’’合并后结果为 * 二项队列的实现 二叉树表示树 较大的子树更靠前（左） * 摊还分析 amortization analysis 一般的复杂性分析——算法运行一次所需要的时间 算法如果运行不只一次呢？ 如果每次运行之间相互无关——同样OK 但如果多次运行之间是相关的呢？ 考虑多次运行的总时间，再除以运行次数，得到一个“平均时间”——注意区分平均情况时间复杂性 很多算法，单独考虑一次运行，最坏情况很差，但摊还分析表明其连续运行性能很好 * 二项队列的创建 对空二项队列中进行N次插入操作 每次操作：一个二进制数***…*** + 1 倒数第一个0在倒数第c位?花费时间c 二进制数的变化：0, 1, …, N-1, N 第0, 2, 4, 6…次操作，花费1 第1, 5, …次操作，花费2 … 时间复杂性O(N) * 创建操作的摊还分析 倒数第一个0在倒数第c位?花费时间c，效果是去掉了c-1棵树，增加一棵树，二项树的数目变化为2-c 令Ci为第i次插入代价，Ti为第i次插入后树的数目，则T0=0，可得到公式 Ci+(Ti – Ti-1)=2 因此 C1+(T1 – T0)=2 C2+(T2 – T1)=2 … CN+(TN – TN-1)=2 消去得由于对任何N，TN都是非负的，显然时间复杂性为O(N) * 摊还分析 位势（potential）：某一时刻的状态 Tactual + DPotential = Tamortized 类似分期付款 平均每月应还X元 前N个月应还N*X元，但不必每月均还X元，有钱就多还点，没钱就少还点，保证总值即可 上例的位势为二项树的棵数 平均2个操作完成一次插入 很多情况下1个操作即可，省下来的1个操作被“存入”位势，后面需多个操作时从位势“支取” 位势的选取 初始值为0，始终非负 位势的变化应与算法代价相联系 * 应用1 机器调度 问题描述 一个机械厂，有m台相同的机器 现有n个作业需要处理，作业i的处理时间ti ——作业放入机器直到从机器上取下的时间 调度（schedule）：按作业在机器上的运行时间对作业进行分配，使得 一台机器在同一时间内只能处理一个作业 一个作业不能同时在两台机器上处理 作业i一旦运行，则需要ti个时间单位 0时刻所有机器均可用 完成时间：完成所有作业的时间 非抢先调度 * 作业调度例 七个作业所需时间(2, 14, 4, 16, 6, 5, 3） 求完成时间最短的调度方案：NP-完全问题 近似算法：近似最优解 * 最长处理时间优先调度策略 longest processing time first, LPT 接近最优的完成时间，最优解的4/3-1/3m 算法 所有作业按处理时间递减排序 每个作业分配给最先空闲的机器 * LPT调度实例 上例 排序：(4-16, 2-14, 5-6, 6-5, 3-4, 7-