(完整版)算法设计与分析期末考试卷及答案a.doc

一填空题每空 2 分共 30 分 1算法的时间复杂性指算法中 的执行次数 2在忽略常数因子的情况下 O 和 三个符号中 提供了算法运行时间 的一个上界 3设 Dn 表示大小为 n 的输入集合 t(I) 表示输入为 I 时算法的运算时间 , p(I) 表示输入 I 出现的概率则算法的平均情况下时间复杂性A(n)= 4分治算法的时间复杂性常常满足如下形式的递归方程 f (n) d , n n 0 f