2-递归和分治策略.ppt

棋盘覆盖 public 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) 渐进意义下的最优算法 * * 合并排序 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 public static void mergeSort(Comparable a[], int left, int right) { if (leftright) {//至少有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 } } 复杂度分析 T(n)=O(nlogn) 渐进意义下的最优算法 * * 合并排序 算法mergeSort的递归过程可以消去。 初始序列 [49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] 第一步 第二步 [38 49 65 97] [13 27 76] 第三步 [13 27 38 49 65 76 97] * * 合并排序 最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n) 稳定性：稳定 * * 快速排序 在快速排序中，记录的比较和交换是从两端向中间 进行的，关键字较大的记录一次就能交换到后面单 元，