算法设计与分析习题集—第1章 算法引论(补：倒推法、蛮力法)

《算法设计与分析习题集—第1章 算法引论(补：倒推法、蛮力法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式的上界为O(nm)。3、算法的基本特征：输入、输出、确定性、有限性。4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为：O(n3)。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、

2、盒图、PAD图。7、算法设计的基本要求：正确性和可读性。8、计算下面算法的时间复杂度记为：O(n2)。for（i＝1；i

3、哪一位？答：O(2)，O(logn)，O(n2/3)，O(20n)，O(4n2)，O(3n)，O(n!)2、什么是算法？算法的特征有哪些？3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for(j=1;j<=n;j++)for(i=1;i<=n;i++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程，算法B的时间复杂性满足递归方程，若要使得算法A时间复杂性的阶高于算法B时

4、间复杂性的阶，a的最大整数值可取多少？答：分别记算法A和算法B的时间复杂性为和，解相应的递归方程得：依题意，要求最大的整数a使得〈。显然，当a<=4时，〈；当a>4时，〈a<=16。所以，所求的a的最大整数值为15。5、算法分析的目的？首先,为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次,是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。6、算法设计常用的技术？（写５种）答：①分治法②回溯法③贪心法④动态规划法⑤分治限界法⑥蛮力法⑦倒推法三、算法设计题　1、蛮力法：百鸡百钱问题？　　　　　　　见ｐｐｔ

5、2、倒推法：穿越沙漠问题？　　　　　　见ｐｐｔ