算法分析习题参考答案第一章.doc

习题一 复杂性分析初步1. 试确定下述程序的执行步数，该函数实现一个mn矩阵与一个np矩阵之间的乘法： 矩阵乘法运算 template void Mult(T *a, T *b, int m, int n, int p) /mn矩阵a与np矩阵b相成得到mp矩阵c for(int i=0; im; i+) for(int j=0; jp; j+) T sum=0; for(int k=0; kn; k+) Sum+=aik*bkj; Cij=sum; 语 句 s/e 频率 总步数template void Mult(T *a, T *b, int m, int n, int p) 0 0 0for(int i=0; im; i+) 1 m+1 m+1for(int j=0; jp; j+) 1 m*(p+1) m*p+m T sum=0; 1 m*p m*p for(int k=0; kn; k+) 1 m*p*(n+1) m*p*n+m*p Sum+=aik*bkj; 1 m*p*n m*p*n Cij=sum; 1 m*p m*p 总 计 2*m*p*n+4*m*p+2*m+1其中 s/e 表示每次执行该语句所要执行的程序步数。频率是指该语句总的执行次数。2 函数MinMax用来查找数组a0:n-1中的最大元素和最小元素，以下给出两个程序。令n为实例特征。试问：在各个程序中，a中元素之间的比较次数在最坏情况下各是多少？ 找最大最小元素 方法一templatebool MinMax(T a, int n, int& Min, int& Max)/寻找a0:n-1中的最小元素与最大元素 /如果数组中的元素数目小于1，则还回false if(n1) return false; Min=Max=0; /初始化 for(int i=1; iai) Min=i; if(aMaxai) Max=i; return true;最好，最坏，平均比较次数都是 2*（n-1） 找最大最小元素 方法二templatebool MinMax(T a, int n, int& Min, int& Max)/寻找a0:n-1中的最小元素与最大元素 /如果数组中的元素数目小于1，则还回false if(n1) rreturn false; Min=Max=0; /初始化 for(int i=1; iai) Min=i; else if(aMaxai) Max=i; return true;最坏2*（n-1）， 最好 n-1, 平均3.证明以下不等式不成立：1). 2).； 4证明：当且仅当时，。 5.下面那些规则是正确的？为什么？ 1).；错 2).；错 3).；错 4).；错 5).。错 6). 对 6. 按照渐进阶从低到高的顺序排列以下表达式: 顺序：7. 1) 假设某算法在输入规模是时为. 在某台计算机上实现并完成该算法的时间是秒.现有另一台计算机,其运行速度为第一台的64倍, 那么,在这台计算机上用同一算法在秒内能解决规模为多大的问题?规模时间复杂度运行速度（时间/每步）总时间解：关系式为 ，在新机器上由于运行速度提高为，设在新机器上能解决的规模为m，则解得2) 若上述算法改进后的新算法的计算为, 则在新机器上用秒时间能解决输入规模为多大的问题？设在新机器上用秒时间能解决的输入规模为m，则，解得3）若进一步改进算法，最新的算法的时间复杂度为 ，其余条件不变，在新机器上运行，在秒内能够解决输入规模为多大的问题？可解决的最大时间复杂度为因为为常数不随输入规模n变化，所以任意规模的n都可在t秒内解决。8. Fibonacci数有递推关系： 试求出的表达式。解：方