算法设计与分析复习资料

《算法设计与分析复习资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.什么是算法？算法是一系列解决问题的指令，对符合规范的输入，能在有限时间内获得预期的输出。2.算法的特点？有穷性-有限步内完成；确定性-每一步是确定的，不能有二义性；可行性-每一步有意义，每一步能求解；输入-须检查输入值值域合法性；输出-输出问题的解，无输出的算法没有意义。补：排序算法的特点：稳定性，在位性。稳定性：如果一个排序算法保留了等值元素在输入中的相对顺序，他被称为是稳定的。换句话说，如果一个输入列表包含两个相等的元素，他们的位置分别是i和j。i

2、储空间(除了个别存储单元外),我们称它是在位的。3.求最大公约数的伪码？Euclid(m,n)//计算m和n最大公约数的欧式算法//输入：两个不全为0的非负整数m>=n//输出：m和n的最大公约数whilen≠0do{r←mmodnm←nn←r}returnm4.问题求解过程理解问题；了解设备性能选择计算方法，精确或近似接法高效的数据结构算法的设计技术；设计算法；正确性证明；分析算法；编程实现算法。1-2-3-4-5-6.4-3,4-2,5-3,5-2（理解问题；决定：计算方法：精确或近似方法：数据结构：算法设计技术；设计算法；正确性证明；分析算法；根据算法写代码.

3、）5.算法分析主要步骤（框架）算法的运行效率也称为计算复杂性(计算复杂度);计算复杂性：时间复杂性（时间效率）空间复杂性（空间效率）时间效率-算法运行所耗费的时间。空间效率-算法运行所需的存储空间。输入规模事实：几乎所有算法对更大规模的输入都要耗费更长的时间！即算法耗时随输入规模增大而增大；增长函数定义为输入规模的函数，用它来研究算法；输入规模的选择它的选择比较直接容易。6.n元列表查找最大值-数组实现列表MaxElement(A[0..n-1])maxval←0fori←1ton-1doifA[i]>maxvalmaxval←A[i]returnmaxval7.检

4、查数组元素是否唯一UniqueElement(A[0..n-1])fori←0ton-2doforj←i+1ton-1doifA[i]=A[j]returnfalsereturntrue8.计算方阵AB的矩阵乘积MatrixMultiplication(A[0..n-1][0..n-1],B[0..n-1][0..n-1])fori←0ton-1do//行循环forj←0ton-1do//列循环M[i][j]←0.0//积矩阵初始化fork←0ton-1do//用变量k表示变化的脚标M[i][j]←M[i][j]+A[i][k]*B[k][j]returnM9.计算

5、十进制正整数n的二进制位数b算法的时间复杂性分析Binary(n)count←1whilen>1docount++n←「n/2「returncount10.求m,n最大公约数gcd(intm,intn)//求m,n最大公约数的欧式递归版本//输入：两个正整数m≥n//输出：最大公约数{if(n=0)//递归出口，结束递归write(M);//输出结果elsegcd(n,mmodn);}11.选择排序(每次从数组中选取最小的按顺序插入)SelectionSort(A[1..n]){fori←1ton-1domin←iforj←i+1tondoif(A[j]

6、])min←jA[i]↔A[min]}12.冒泡排序(相邻的比较，aA[j+1])A[j]↔A[j+1]}13.顺序查找SequentialSearch(A[n..n],k){A[n]←Ki←0while(A[i]≠k)i←i+1if(i

7、

8、s

9、≤t)thenadhocery(s)else{dividesintosmallersubsets1