最新算法导论第三次习题课PPT课件,算法导论第三次习题课,最新算法导论第三次习题课PPT课件,16.1-1 动态规划时间复杂度为 ,贪心算法时间复杂度为,最新算法导论第三次习题课PPT课件,16.1-2 略 16.1-3 用两个链表分别存放空闲教室和繁忙教室,把活动按开始时间递增排序,依次调度教室,就可以获得最少教室数。调度方案是在繁忙教室队列中寻找是否有教室已经空闲,再在空闲教室队列中寻找空闲教室,如果都没有,就再增加一个教室。 说明:本题直接调用书上的算法GREDDY-ACTIVITYSELECTOR( )来求是不对的,如下实例,按GREDDYACTIVITY-SELECTOR( )求得需要3个教室,实际上只要2个教室,最新算法导论第三次习题课PPT课件,16.3-1 略 16.3-2 略 16.3-5 用2n-1位表示树的结构,内部结点用1表示,叶子结点用0表示,以树的遍历为序。用nlog(n)位表示字母序列,每个字母的二进制编码长度为log(n),总共需要nlog(n)位,最新算法导论第三次习题课PPT课件,17.1-1 不能保持,如执行n次MULTIPUSH(s,n) 17.