算法设计与分析 习题1 学习课件

习题1L求解递归方程Tn=T5n/6+n2•证明或否证明/n+o/n=/n

3.证明设k是任意常数正整数，则4,证明°/3+如=°〃皿/,，,八二十廨、系白和护丁7口=4口/2〕+

15.求解递归力程I，

6.对于平面上的两个点pl=xl,yl和p2=x2,y2,如果xl2且yly2,则p2支配pl,给定平面上的n个点，请设计算法求其中没有被任何其他点支配的点

7.如果一个数组A［1…n］中某个元素的数量超过其元素数量的一半，称其包含主元素，假设比较两个元素大小的时间不是常数但判定两个元素是否相等的时间是常数，要求对于给定数组A,设计算法判定其是否有主元素，如果有，找到该元素1设计时间复杂性为Onlogn的算法完成该任务2设计时间复杂性为0n的算法完成该任务

8.证明在有n个数的序列中找出最大的数至少需要n.l次比较

9.设计一个对7个元素进行排序的方法，保证其平均比较次数最少，要求证明这个结论

10.al,a2,”an是｛1,2,…,n｝的一个随机排列，等可能第位n!中可能排列中的任意一个,当对列表al,a2,an排序时，元素ai从它当前位置到达排序位置必须一定|ai-i|的距离,求元素必须移动的期望总距离上［.；」出一4。