实验题

题目1 比较算法复杂性描述函数的增长

一、问题描述

常用到的描述算法复杂度的函数有n，logn，n ² ，n ³ ，nlogn，n！，2 ⁿ 。比较随n的增大，这些函数的增长情况。

二、要求

1.分别求出n取值为1、5、10、15、20、25、30时七种函数的值，并按照增长速度排序。

2.若在每秒执行10亿次指令的计算机上运行，分别计算出n取值为1、5、10、15、20、25、30时七种函数的运行时间。

题目2 矩阵连乘算法的时间和空间复杂性

一、问题描述

已知有三个整数矩阵A _100×1000 、B _1000×50 和C _50×500 ，分别按照方案（AB）C和方案A（BC），求这三个矩阵的连乘积。

二、要求

1.通过采用对核心运算执行频度和对占用数据空间的统计的方式，比较两种方案的时间复杂度和空间复杂度。

2.编写程序记录根据这两种方案所编写的程序的执行时间，输出结果。

题目3 全排列的递归实现

一、问题描述

全排列是指一个数列的不同顺序的所有组合方式。

用1、2、3来举例，123的全排列有123、132、213、231、312、321这六种。

首先考虑213和321这两个数是如何得出的。显然这两个都是123中的1与后面两数交换得到的。然后，可以将123的第二个数和第三个数交换得到132。同理，可以根据213和321来得231和312。因此可以知道，全排列就是从第一个数字起每个数分别与它后面的数字交换。

二、提示与分析

N个互不相同的元素的全排列一共有N！种。实现N个互不相同的元素的全排列可以用递归的方法来实现。

用递归实现全排列的思路：每次将当前元素与后面的元素进行一次交换，可以生成新的排列，当然，交换完的排列全部生成完后要恢复原样。每个元素第一次交换都是跟自己，然后与它后面的交换。

三、选作内容

1.去掉重复的全排列的递归实现。

2.全排列的非递归实现。

题目4 皇后问题

一、问题描述

在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不冲突，即在每一横列、竖列和斜列只有一个皇后。

二、提示与分析

数据表示：用一个8位的八进制数表示棋盘上皇后的位置。

例如45615353表示：

三、选作内容

对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，能产生良好的效果。

题目5 比较递归和非递归算法的时空效率

一、问题描述

给定正整数N，分别采用循环和递归两种方法实现输出1，2，…，N的N个整数。

二、要求

1.分别取N值为100、1000、10000和100000，比较循环方法和递归方法的时间复杂度。

2.分别取N值为100、1000、10000和100000，比较循环方法和递归方法的空间复杂度。

3.分析时间复杂度和空间复杂度产生差别的原因。 +6RncQ387XyN7MQ/mkjJR0MU3dLx24td1GZtIbjspEH6h6+kbIMvd0IISs3oPNY1