中科大算法导论第一,二次和第四次作业答案.ppt

第一次作业 2 2 3再次考虑线性查找问题 见练习2 1 3 在平均情况下 需要检查输入序列中的多少个元素 假定待查找的元素是数组中任何一个元素的可能性是相等的 在最坏情况下有怎样呢 用 形式表示的话 线性查找的平均情况和最坏情况运行时间怎样 对你的答案加以说明 线性查找问题输入 一列数A 和一个值v 输出 下标i 使得v A i 或者当v不在A中出现时为NIL 平均情况下需要查找 1 2 n n n 1 2最坏情况下即最后一个元素为待查找元素 需要查找n个 故平均情况和最坏情况的运行时间都为 n 2 3 2改写MERGE过程 使之不使用哨兵元素 而是在一旦数组L或R中的所有元素都被复制回数组A后 就立即停止 再将另一个数组中余下的元素复制回数组A中 MERGE A p q r n1 q p 1n2 r qcreatearraysL 1 n1 andR 1 n2 fori 1ton1doL i A p i 1 forj 1ton2doR j A q j i 1j 1 k pwhile i n1 and j n2 doifL i R j doA k L i i elsedoA k R j j k while i n1 doA k L i while j n2 doA k R j 3 2 3证明等式lg n nlgn 并证明等式n 2n 和n o nn 第二次作业 3 2 4函数 lgn 是否多项式有界 函数 lglgn 呢 4 1 2证明这个递归的解也是 nlgn 得到解为 nlgn 4 1 4证明合并排序算法的 准确 递归式 4 2 的解为 nlgn 7 1 2当数组A p r 中的元素均相同时 PARTITION返回的q值是什么 修改PARTITION 使得当数组A p r 中所有元素的值相同时 q的值是r 一种方法 记一个cnt碰上一样的数的时候cnt 对全部相同这种情况cnt r p 1 进行处理直接返回 p r 2 或者修改PARTITION A p r 增加对A i x时的处理 对于A i x的数据 一半放在x左边 一半放在x右边通过设置一个flag初始为1当flag 0时才进行交换交换flag flag 第四次作业 intPartition intA intp intr intx A r i p 1 intflag 1 for intj p j A i returni 1 7 2 3证明 当数组A包含不同的元素 且按降序排序时 QUICKSORT的运行时间为 n2 证明 数组元素各不相同 且按降序排列时 每次递归调用都会产生一个元素数目为n 1的分块和一个1的分块 故有T n T n 1 n 有T n T n 1 cn d T n 2 cn c n 1 2d T n 3 cn c n 1 c n 2 3d T 1 cn c n 1 c n 2 c 1 nd T 1 cn n 1 2 nd n2 7 4 3证明 在q 0 1 n 1区间上 当q 0或q n 1时 q2 n q 1 2取得最大值 求导 取极值 或者进行变换 8 2 4在O 1 的时间内 回答出输入的整数中有多少个落在区间 a b 内 给出的算法的预处理时间为O n k 利用计数排序 由于在计数排序中有一个存储数值个数的临时存储区C 0 k 利用这个数组即可 a b 区间整数个数为C b C a 1 题目已经提示运用桶排序 主要是正确设置桶点均匀分布 则每个桶的尺寸应相等 即每个桶在圆中所占据的面积相等 把圆分为n个部分 第一个部分是以原点为圆心的圆 其他部分是以原点为圆心的圆环 单位圆的面积是 1 2 那么我们选择一系列的距离d0 d1 d2 dn满足d0 0 d1 2 n d2 2 2 n d3 2 3 n dn 2 得到 d0 d1 d2 dn 0 sqrt 1 n sqrt 2 n 1 这样相当于每个di到di 1所占的面积都是相同的 也即每个左边点会均匀的落入这些区间中 所n个桶为 d0 d1 d1 d2 dn 1 dn 9 1 1证明 在最坏情况下 利用n ceil lgn 2次比较 即可得到n个元素中的第2小元素 提示 同时找最小元素 先两两比较 较小的组成新的数组再两两比较 不断如此 从而形成一个倒立的树 终于找出最小的元素 由于最上一层是n 2次比较 这又能够看做一个满二叉树 所以总的比较次数为n 2 n 2 1 n 1 找出一个最小的元