《算法设计与分析大作业西安电子科技大学》由会员分享，可在线阅读，更多相关《算法设计与分析大作业西安电子科技大学（6页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析大作业西安电子科技大学 算法设计技术与方法 学院电子工程学院专业电子与通信工程学号 学生姓名 授课教师公茂果 问题一 1 问题描述 分别实现多项式求值的三种运算，针对不同规模的输入值a，各算法的运行时间，问题规模n分别取10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000时绘制三种算法运行时间的比较图。 2 算法分析 1)算法1：P n(x) = P n-1(x) + a n x nP i(x) = P i-1(x) + a i x i 该算法的伪代码表示如下： begin P := a0; for i
2、=1 to n do P = P + a i x i; end end 该算法的时间复杂度为T(n) = O(n2)。 2)算法2：在上一算法中，可以看出xi重复计算了。如果 把上一次计算出的xi-1保存起来，直接乘以x,就可以得到xi，这样就可以避免重复计算。 该算法的伪代码表示如下： begin P := a0; Q := 1; for i=1 to n do Q = Qx; P = P + a i Q; end end 该算法的时间复杂度为T(n) = O(n)。 3)算法3：P n(x) = Pn-1(x)x+a0, Pn-1(x)=a n x n-1+a n-1x n-2+a2x+a
3、1 Pi(x)=Pi-1(x)x+a n-i 该算法的伪代码表示如下： begin P := a n; for i=1 to n do P = xP + a n-i; end end 该算法的时间复杂度为T(n) = O(n)。 3 实验数据 下表为实验中所测得的数据： 4 实验结果图 下图为用所测得的数据画出的运行时间对比图，横轴为多项式的规模n，纵轴为运行时间。为了便于观察，横坐标采用了对数坐标。 从上图可以看出，在多项式的规模n 1000时，可以明显地看出算法2和算法3的优越性。由于算法2和算法3的时间复杂度都为O(n)，所以这两种算法的运行时间差不多。 三种算法的运行时间曲线与前面分析
4、的三种算法的时间复杂度也是相吻和的：算法1的时间复杂度为O(n2)，运行 时间随着n的增长呈平方律增长；算法2和算法3的时间复杂度为O(n),运行时间随着n的增长而线性增长。 5 源代码 3)% polyval1.m - 算法1的实现 function val = polyval1(a, x) % 该函数用来实现算法1 n = length(a); val = a(1); for i = 1:(n-1) val = val + a(i+1)*xi; end; 3)% polyval2.m - 算法2的实现 function val = polyval3(a, x) % 该函数用来实现算法2 n
5、 = length(a); val = a(1); temp = 1; for i = 1:(n-1) temp = temp * x; val = val + a(i+1)*temp; end; 3)% polyval3.m - 算法3的实现 function val = polyval4(a, x) % 该函数用来实现算法3 n = length(a); val = a(n); for i = 1:(n-1) val = val * x + a(n - i); end; 3)% main.m - n取不同值时,分别计算3种算法的运行时间 n = 10 50 100 150 200 300
6、400 500 10000 20000 50000 100000; x = 1.001; % x取1.001以下才能保证结果不溢出 for i = 1:length(n) a = rand(n(i), 1); origin_time = cputime; for j = 1:500 polyval1(a, x); end; time1(i) = (cputime - origin_time)/500; % 计算算法1的运行时间 origin_time = cputime; for j = 1:1000 polyval2(a, x); end; time2(i) = (cputime - ori
7、gin_time)/1000; % 计算算法2 的运行时间 origin_time = cputime; for j = 1:1000 polyval3(a, x); end; time3(i) = (cputime - origin_time)/1000; % 计算算法3的运行时间 end; save data time1 time2 time3 %保存数据 load data %加载数据 % 画图 semilogx(n, time1,-b*, n, time2, :b*, n, time3, -.b*); xlabel(n),ylabel(时间/s); legend(算法1,算法2,算法3
8、); grid on 问题二 1 问题描述 分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为2222， 2323，2424， 2525， 2626， 2727， 2828， 2929时的运行时间与MATLAB 自带的矩阵相乘的运行时间，绘制时间对比图。 2 算法分析 1) 算法1：按照矩阵相乘的定义，直接计算。 1 n k C i j A i k B k j = 若依此定义来计算A 和B 的乘积矩阵C ，则每计算C 的一个元素C i j ，需要做n 次乘法和n-1次加法。因此，算出矩阵C 的每个元素所需的计算时间为O(n 3)。 2) 算法2：采用分治法。 将矩阵A ，B 和C 中每一
9、矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB 重写为： C 11 = A 11B 11 + A 12B 21 C 12 = A 11B 12 + A 12B 22 C 21 = A 21B 11 + A 22B 21 C 22 = A 21B 12 + A 22B 22 再把A 11，A 12，A 21，A 22，B 11，B 12，B 21，B 22分别分成4个大小相等的子矩阵，这样依次下去，直到子矩阵为1 阶矩阵为止。 此时的时间复杂度为O(n 3)，与上面的算法相比，并没有减少时间复杂度。 3) 算法3：利用Strassen 矩阵乘法 111211121112212221 22
10、2122C C A A B B C C A A B B ?= ? ? 1111222211122232122114222111511221122612222122711211112()()()()()()()()()() M A B B M A A B M A A B M A B B M A A B B M A A B B M A A B B =-=+=+=-=+=-+=-+ 11542612122134 225137C M M M M C M M C M M C M M M M =+-+=+=+- 再把A 11，A 12，A 21，A 22，B 11，B 12，B 21，B 22分别分成4个
11、大小相等的子矩阵，这样依次下去，直到子矩阵为1阶矩阵为止。 此算法的时间复杂度为O(n 2.81)，比以上两种算法的时间复杂度都小。 3 实验数据 下表为实验中所测得的数据： 4 实验结果图 下图为实验结果图，横轴为矩阵规模的幂次，纵轴为运行时间。 算法1和MATLAB自带算法运行时间很短，曲线几乎与横轴重合，所以图中看不太清楚。 理论上，算法3要比算法1的运行时间要短一些，但是算法2和算法3采用的是递归调用，递归调用时所消耗的时间占了整个运行时间的很大一部分。所以即使算法3比算法1的时间复杂度小，前者比后者的运行时间还是多了很多。 从算法2和算法3的运行时间图中可以看出，算法3比算法2所用的
12、时间少了很多，这与理论是相吻和的。 5 源代码 1)% multiply1.m - 算法1的实现 function C = multiply1(A, B) % 该函数用来实现算法1 n = size(A, 1); for i = 1 : n for j = 1 : n C(i, j) = A(i, :) * B(:, j); end; end; 2)% multiply2.m - 算法2 的实现 function C = multiply2(A, B) % 该函数用来实现算法2 n = size(A, 1); if(n = 1) C = A * B; % 此时A，B为两个1阶矩阵 else %
13、 矩阵分成4个大小相等的子矩阵 A11 = A(1 : n/2, 1 : n/2); A12 = A(1 : n/2, n/2+1 : n); A21 = A(n/2+1 : n, 1 : n/2); A22 = A(n/2+1 : n, n/2+1 : n); B11 = B(1 : n/2, 1:n/2); B12 = B(1 : n/2, n/2+1 : n); B21 = B(n/2+1 : n, 1 : n/2); B22 = B(n/2+1 : n, n/2+1 : n); % 递归调用 C11 = multiply2(A11, B11) + multiply2(A12, B21); C12 = multiply2(A11, B12) + multiply2(A12, B22); C21 = multiply2(A21, B11) +
