递归分治算法 动态规划法问题 分治策略的实例——归并排序 ●某一类递归问题,如果直接用递归实 现,可能会导致极低的效率 往往是o(2) 回回回回画回回凹 ●上一级问题可以利用那些更小子问题的 结果,例如 分 合 Fibonacci问题 合数问题 二分搜索、BST查找和插入 Hanoi问题不是动态规划问题 sTL里面的 quick sort—快速排序 递归的效率 递归调用树 C=O -1+C >n>0 n=0或m= ●c(m,n) C32) ·两个子问题cm-1,n)和c(m-1,n-1) 回 2)=1C(2 2D)(20) 递归了 回回圆可回 递归法 递推法 int comb(int m, int n)( intc[m];∥假设初值为0矩阵 int comb(int m, int n) if(m=n)‖(n==0) return1;∥处理边界,递归出口 int i,j (m=n)‖(m==0))cm]=1;递归出口 H+)∥递推 return comb(m-1, n)+comb(m-1, n-1) 时间代价O(2m2) ·时间代价o(mn)10 递归分治算法 z分治策略的实例——归并排序 421 24 5143 541 35 97 87 789 二分搜索、BST查找和插入 STL里面的quick_sort——快速排序 z分 z治 z合 动态规划法问题 z 某一类递归问题，如果直接用递归实 现，可能会导致极低的效率 z 往往是Ｏ(2n) z 上一级问题可以利用那些更小子问题的 结果，例如 z Fibonacci问题 z 组合数问题 z Hanoi问题不是动态规划问题 递归的效率 z C(m,n) z 两个子问题C(m-1,n) 和 C(m-1,n-1) 1 1 1, 0 1, 0 nn n mm m n m C C C mn C n mn − − − ⎧ ⎫ ⎪ ⎪ = + >> ⎨ ⎬ ⎪ ⎪ ⎩ ⎭ = == 或 递归 递归调用树 C(5,3) C(4,2) C(2,2) = 1 C(2,1) C(3,2) C(4,3) C(3,3) =1 C(3,1) C(2,2) = 1 C(2,1) C(3,2) C(1,1) = 1 C(1,0) = 1 C(1,1) = 1 C(1,0) = 1 C(2,1) C(2,0) =1 C(1,1) = 1 C(1,0) = 1 递归法 int comb(int m, int n) { if ((m==n) || (n==0)) return 1; //处理边界，递归出口 else return comb(m-1,n)+comb(m-1,n-1); } z时间代价O(2m-2n) 递推法 int c[m][n]; // 假设初值为0矩阵 int comb(int m, int n) { int i,j; if ((m==n) || (n==0)) c[m][n] = 1; //递归出口 else for (i=1; i<=m; i++) // 递推计算 for (j=0; j<=i,j<=n; j++) if ((i==j) || (j==0)) c[i][j] = 1; else [i][j] = c[i-1][j] + c[i-1][j-1]; } z 时间代价O(mn)