计算机算法设计与分析

《计算机算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法设计与分析（书要整体看看再结合老师画的重点）第一章1.算法：是在有限步骤内求解某一问题所使用的一组定义明确的规则。程序：是算法用某种程序设计语言的具体实现。1.算法评定标准：时空的观点标准1算法在计算机上的执行的时间最短。标准2算法所需要的存储空间最小。发展的观点标准3算法的适应性强。设计的观点标准4算法的设计时间少。交流的观点标准5算法容易理解。2.时间复杂性论：原因：所有关于时间复杂性增长的阶的定义和渐近界的讨论都可移植到空间复杂性的讨论中。算法的空间复杂性相对简单，它不可能超过运行时间的复杂性，因为写入每一个内存单元都至少需要一定的时间。对于一个相同的输入I，S(N)

2、=O(T(N))。空间复杂性降低到一定程度时会大幅度增加时间复杂性，而时间复杂性的降低一般对空间复杂性不会有太大影响。例：求两个n阶矩阵的乘积C=AB的算法及其时间复杂性。定义矩阵A[][n]，B[][n]，C[][n]fori←0ton　　　　　　　　　　　←频度：n+1　forj←0ton　　　　　　　　　　　←频度：n（n+1）C[i][j]=0;　　　　　　　　　　←频度：n2　　fork←0ton　　　　　　　　　←频度：n2(n+1)　　　C[i][j]=C[i][j]+A[i][k]*B[k][j];←频度：n3endforendforEndfor时间复杂性T(n)=n

3、+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1上界的阶越低则评估越有价值。下界的阶越高，则评估精度越高，也就越有价值。T(n)大概有三种计算方法：计算迭代次数（循环结构的执行次数）计算基本运算的频度使用递归方程（多用于递归算法）第二章1.并非所有递归函数都能找到其非递归的定义。2.分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。原理：递归地解这些子问题，然后将各子问题的解合并得到原问题的解。分治法的适用条件：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；利用该问题分

4、解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（而动态规划法适合各子问题不独立时，在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算）3.棋盘覆盖法：算法描述：chessBoard(tr,tc,dr,dc,size)//tr:棋盘左上角方格的行号；tc:棋盘左上角方格的列号；dr:特殊方格所在行号；dc:特殊方格所在列号；size:棋盘规格；tile是全局变量，初值为0。过程chessBoard(tr,tc,dr,dc,size)if(size==1)retu

5、rn;t←tile++;//L型骨牌号s←size/2;//分割棋盘//覆盖左上角子棋盘if(dr=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else//此棋盘中无特殊方格board[tr+s-1][tc+s]

6、=t;//用t号L型骨牌覆盖左下角chessBoard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格endif（接下页）//覆盖左下角子棋盘if(dr>=tr+s&&dc=tr+s&&dc>=tc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s)

7、elseboard[tr+s][tc+s]=t//用t号L型骨牌覆盖左上角chessBoard(tr+s,tc+s,tr+s,tc+s,s)//覆盖其余方格endif复杂度分析： T(n)=O(4k)渐进意义下的最优算法了解下合并排序和快速排序：合并排序：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。复杂度分析 T(n)=O(nlogn)渐进意义下的最优算法快速排序：