2、二分搜索技术
给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。
分析：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题;
分解出的子问题的解可以合并为原问题的解；
分解出的各个子问题是相互独立的。
分析：很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。
据此容易设计出二分搜索算法：
template<class Type> int BinarySearch(Type a[], const Type& x, int l, int r) { while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; }
算法复杂度分析：
每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。
3、大整数的乘法
请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
小学的方法：O(n2) ×效率太低
分治法:
XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd
XY = ac 2n + ((a+b)(c+d)-ac-bd) 2n/2 + bd
细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+b,c+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。
小学的方法：O(n2) ×效率太低
分治法: O(n1.59) √较大的改进
如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。
最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。
4、Strassen矩阵乘法
传统方法：O(n3)
若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3)
使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：
由此可得：
传统方法：O(n3)
分治法:
为了降低时间复杂度，必须减少乘法的次数。
传统方法：O(n3)
分治法: O(n2.81)
更快的方法??
Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。
在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)
是否能找到O(n2)的算法？
5、棋盘覆盖
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。
void chessBoard(int tr, int tc, int dr, int dc, int size){ if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else {// 用 t 号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; // 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} }
T(n)=O(4k) 渐进意义下的最优算法
6、合并排序
基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
T(n)=O(nlogn) 渐进意义下的最优算法
void MergeSort(Type a[], int left, int right) { if (left<right) {//至少有2个元素 int i=(left+right)/2; //取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } }
算法mergeSort的递归过程可以消去。
最坏时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
辅助空间：O(n)
