算法设计与分析期末考试卷及答案a16页.docx

一填空题（每空2分，共30分）1算法的时间复杂性指算法中 的执行次数。2在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。3设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。4分治算法的时间复杂性常常满足如下形式的递归方程： 其中，g(n)表示 。5. 分治算法的基本步骤包括 。6回溯算法的基本思想是 。7动态规划和分治法在分解子问题方面的不同点是 。8贪心算法中每次做出的贪心选择都是 最优选择。9PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小