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

一、填空题：

1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。

2、多项式10()m m A n a n a n a =+++的上界为O(n m )。

3、算法的基本特征：输入、输出、确定性、有限性。

4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。

5、计算下面算法的时间复杂度记为：O(n 3) 。

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、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。

7、算法设计的基本要求：正确性 和 可读性。

8、计算下面算法的时间复杂度记为：O(n 2) 。

for （i ＝1；i

{ y=y+1;

for （j ＝0；j <=2n ；j++ ）

x ＋＋；

}

9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。

10、算法是指解决问题的。

二、简答题：

1、按照时间复杂度从低到高排列：O( 4n 2)、O( logn)、O( 3n )、O( 20n)、O( 2)、O( n 2/3), O( n!)应该排在哪一位？

答：O( 2)，O( logn)，O( n 2/3)，O( 20n)，O( 4n 2)，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 的时间复杂性满足递归方程

???>+===1n , n )2/n (T 4)n (T 1n , 1)n (T ，算法B 的时间复杂性满足递归方程

?

??>+===1n , n )4/n (aT )n (T 1n , 1)n (T ，若要使得算法A 时间复杂性的阶高于算法B 时间复杂性的阶，a 的最大整数值可取多少？

答：分别记算法A 和算法B 的时间复杂性为)n (T A 和)n (T B ，解相应的递归方程得：

依题意，要求最大的整数a 使得)n (T B 〈)n (T A 。显然，当a<=4时，)n (T B 〈)n (T A ；当a>4时，)n (T B 〈(n)T A ?2a log 4

所以，所求的a 的最大整数值为15。

5、算法分析的目的？

首先,为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间； 其次,是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。

6、算法设计常用的技术？（写５种）

答：

①分治法

②回溯法

③贪心法

④动态规划法

⑤分治限界法

⑥蛮力法

⑦倒推法

三、算法设计题

1、蛮力法：百鸡百钱问题？

见ｐｐｔ

2、倒推法：穿越沙漠问题？

见ｐｐｔ