l杭电算法分析与设计复习提纲.docVIP

杭电算法设计与分析复习提纲 杭电算法设计与分析复习提纲 1 学弟学妹求送点财富 1 填空题 5 快速排序的随机化版本 5 计数排序 6 学弟学妹求送点财富 这份答案是在2014年上半年总结，红色部分为考到的题目，老师没有对题目做无任何修改 选择判断蒙一下就可以了40分。 简答题 5*8=40分 5.2-3 求骰子期望值 略 7.1-4 应如何修改QUICKSORT，才能使其按非增序进行排序？ 在划分子树组时，将大于主元的元素放左边，小于主元的元素放右边 7.2-2 当数组A的所有元素都具有相同值时，QUICKSORT的运行时间是什么？ 7.2-4 银行经常按照交易时间，来记录有关某一账户的交易情况，但是，很多人喜欢按照票据号来收到其银行对账单。因此，如何将按交易时间排序转换成按支票编号来排序，就成为一个对几乎排好序的输入进行排序的问题。证明在这个问题上，过程INSERT_SORT的性能往往优于过程QUIKSORT。 （引用自网络)对于QUIKSORT来说，输入一个已排序的数组属于最坏的情况，则每次区间划分都是最大程度的不对称。其算法运行的递归时间为T(n) = T(n-1) + Θ(n)， 算法时间复杂度为Θ(n^2)； 而对INSERT-SORT来说，输入一个已排序的数组却属于最佳的情况，算法时间复杂度为O(n)。也就是说当输入一个几乎排好序的数组，快速排序趋于最坏的情况，而插入排序却趋于最佳的情况随机快速排序中，只要区间包含元素数目大于1，则需调用RANDOMIZED-PARTITION，选取主元（pivot）进行区间划分， 而主元的选取需调用Random。主元（pivot）一旦被选出来后，就不会在加入到后续的排序了。直白来说就是，有多少次主元（pivot）选取就有多少次随机数生成。另一方面从算法的递归二叉树树上来看，递归树二叉树的非叶子节点可表示一个主元（pivot）；而叶子节点分为两种，一种节点是包含0个元素，另一种节点是包含1个元素，而且该元素不是主元（pivot）。非叶子节点和包含1个元素的叶子节点的数目之和就是输入序列的大小n。即递归树的非叶子节点的数目就是调用RANDOM的次数。调用RANDOM次数T(RANDOM)≤n，即T(RANDOM)=O(n)。 　　又根据二叉树的性质，对于任意一棵二叉树，如果其叶结点数为a，而度数为2的结点（非叶子节点）总数为b，则a=b+1；对于快速排序的递归二叉树中，非叶子节点度数均为2。假设含有0个元素的叶子节点数目a0（≥0），含有1个元素的叶子节点数目为a1，所以 b =a-1 ≥ a1 - 1；又b+a1 = n，可得 b ≥ n/2 - 1，即T(RANDOM)=Ω(n)。 8.2-4 请给出一个算法，使之对给定的介于0到k之间的n个整数进行预处理，并能在O(1)时间内回答出输入的整数中有多少个落在[a...b]区间内。你给出的算法的预处理时间为Θ(n+k)。 略.... 8.3-4 说明如何在O(n)时间内，对0~n^2 -1之间的n个数进行排序。 把整数转换为n进制再排序，每个数有两位，每位的取值范围是[0..n-1]，再进行基数排序 当分布不均匀时，全部元素都分到一个桶中，则O(n^2)，当然[算法导论8.4-2]也可以将插入排序换成堆排序、快速排序等，这样最坏情况就是O(nlgn)。对所有元素，两个一组比较大小，小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。 9.2-1 证明: 在RANDOMIZED-SELECT中,对于长度为0的数组,不会进行递归调用. 从RANDOMIZED-SELECT函数知，长度为0的数组 p=r，那么直接返回A[p].不做下面的随机划分和递归调用。以RANDOMIZED-SELECT作为选择中值的算法step1：求出数组的中位数的值O(n) step2：计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n) step3：求出数组B中第k小的数ret O(n) step4：计算数组S中与ret差的绝对值小于ret的数并输出O(n) 其中，step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数 在一棵红黑树中，从某结点x到其后代叶结点的所有简单路径中，最长的一条是最短一条的至多两倍。 反证法：假设存在一条最长路径长度是最短路径长度的2倍多1，即L1=k，L2=2k+1。为保证从根节点到L1和L2的黑高度相同，最小黑高为k，否则L2上必然出现两个红色是父子关系。那么L2中有k个黑色，k+1个红色，由于根节点必须是黑色，那么lL2中必定存在红色的子节点不是黑色的情况，因此与假设矛盾，命题得证。 14.1-4