计算机算法设计与分析

计算机算法设计与分析

（书要整体看看再结合老师画的重点）

第一章

1.算法：是在有限步骤内求解某一问题所使用的一组定义明确的规则。 程序：是算法用某种程序设计语言的具体实现。 1.算法评定标准：

时空的观点

标准1 算法在计算机上的执行的时间最短。 标准2 算法所需要的存储空间最小。 发展的观点

标准3 算法的适应性强。 设计的观点

标准4 算法的设计时间少。 交流的观点

标准5 算法容易理解。 2.时间复杂性论：

原因：

所有关于时间复杂性增长的阶的定义和渐近界的讨论都可移植到空间复杂性的讨论中。 算法的空间复杂性相对简单，它不可能超过运行时间的复杂性，因为写入每一个内存单元都至少需要一定的时间。对于一个相同的输入I，S(N)=O(T(N))。

空间复杂性降低到一定程度时会大幅度增加时间复杂性，而时间复杂性的降低一般对空间复杂性不会有太大影响。

例： 求两个n阶矩阵的乘积C=AB的算法及其时间复杂性。 定义矩阵A[ ][n]，B[ ][n]，C[ ][n]

for i ← 0 to n ←频度：n+1 for j ← 0 to n ←频度：n（n+1） C[i][j] = 0; ←频度：n2 for k ← 0 to n ←频度：n2(n+1) C[i][j] = C[i][j] + A[i][k] * B[k][j]; ←频度：n3 end for end for End for

时间复杂性T(n) = n+1+n (n+1) + n2 + n2(n+1) + n3 = 2n3+3n2+2n+1 上界的阶越低则评估越有价值。

下界的阶越高，则评估精度越高，也就越有价值。 T(n)大概有三种计算方法：

计算迭代次数（循环结构的执行次数） 计算基本运算的频度

使用递归方程（多用于递归算法）

第二章

1.并非所有递归函数都能找到其非递归的定义。

2.分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。原理：递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

分治法的适用条件：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（而动态规划法适合各子问题不独立时，在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算 ） 3.棋盘覆盖法： 算法描述：

chessBoard(tr, tc, dr, dc, size)

//tr:棋盘左上角方格的行号；tc:棋盘左上角方格的列号；dr:特殊方格所在行号；dc:特殊方格所在列号；size:棋盘规格；tile是全局变量，初值为0。 过程 chessBoard(tr, tc, dr, dc, size) if (size == 1) return;

t ← tile++ ; // L型骨牌号

s ← size/2; // 分割棋盘 // 覆盖左上角子棋盘

if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s);

else // 此棋盘中无特殊方格

board[tr + s - 1][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s); // 覆盖其余方格 end if

if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s);

else // 此棋盘中无特殊方格

board[tr + s - 1][tc + s] = t; // 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s); // 覆盖其余方格 end if （接下页） // 覆盖左下角子棋盘

if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s) else

board[tr + s][tc + s - 1] = t // 用 t 号L型骨牌覆盖右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s) // 覆盖其余方格 end if

// 覆盖右下角子棋盘

if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s) else board[tr + s][tc + s] = t // 用 t 号L型骨牌覆盖左上角 复杂度分析： chessBoard(tr+s, tc+s, tr+s, tc+s, s) // 覆盖其余方格 end if T(n)=O(4k) 渐进意义下的最优算法

了解下合并排序和快速排序： 合并排序：

基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 复杂度分析 T(n)=O(nlogn) 渐进意义下的最优算法 O(1)k?0?T(k)???4T(k?1)?O(1)k?0 O(1)n?1?T(n)???2T(n/2)?O(n)n?1

快速排序：

过程Split(A[left: right],w)

1. i left; x A[left] 2. for j left+1 to right 3. if A[j]≤x then 4. i i+1

5. if i≠j then 互换A[i]和A[j] 6. end if 7. end for

8. 互换A[left]和A[i] 9. w i

10.return A和w

注意：

1.扩展汉诺塔问题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。

2.熟悉采用分治法求解大整数乘法基本过程。 3.通过棋盘覆盖问题理解算法的递归调用过程。

4.编写程序实现合并排序算法MergeSort和快速排序算法qSort。