算法设计期中试卷、平时作业参考解答14页.docx

算法分析与设计2012-2013-2学期期中测试（信息安全专业DQ教学班）姓名： 学号： 得分： 1. 证明。（10分）证明：对于任意f1(n) O(f(n)，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1f(n)成立。类似，对于任意g1(n) O(g(n)，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n)成立。令c3 = maxc1, c2，n3 = maxn1, n2，则对所有的n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n) = c3(f(n) + g(n)即成立。2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分）解：(1) 是对数函数的幂，是幂函数，因此;(2) ，因此;(3) ，因此;(4) 对和取对数，有，因为，所以;