(算法分析的设计）第1章递推关系.pptVIP

递推关系 递推方程 递推方程（recurrence equation）是自然数上一个函数T(n)，它使用一个或多个小于n时的值的等式或不等式来描述。递推方程也称为递推关系或递推式。 递推方程必须有一个初始条件（也称边界条件）。 程序的时间分析 设n = d1d2?dk是k位数，当k = 1时，只执行cout语句和if判定语句；当n至少是2位数（k＞1）时，除了执行这两个操作外，还需执行递归函数调用PrintDigit(n/10)，?n/10?是k ? 1位数 。 T(k) = 2k + 2 = ?(k) void PrintDigit(unsigned int n) { coutn%10; //输出最后一位数dk if(n=10) PrintDigit(n/10); //以逆序输出前k-1位数 } 汉诺塔问题 enum tower { A=X, B=Y, C=Z}; void Move(int n,tower x,tower y) { //将第n个圆盘从塔座x移到塔座y的顶部 cout The disk n is moved from char(x) to top of tower char(y) endl; } void Hanoi(int n, tower x, tower y, tower z) {//将x上部的n个圆盘移到y上，顺序不变。 if (n) { Hanoi(n-1, x, z, y); Move(n,x,y); Hanoi(n-1, z, y, x); } } 时间复杂度分析 替换方法 替换方法要求首先猜测递推式的解，然后用归纳法证明。 可以先对以下这些小的示例进行计算： T(3) = 7 = 23 ? 1；T(4) = 15 = 24 ? 1； T(5) = 31 = 25 ? 1；T(6) = 63 = 26 ? 1 看起来，似乎T(n) = 2n ? 1，n≥1。 证明：（归纳法证明） 当n = 1时，T(1) = 1，结论成立。归纳法假设：当k＜n时，有T(k) = 2k ? 1，那么，当k = n时，T(n) = 2T(n ? 1) + 1 = 2(2n?1 ? 1) + 1 = 2n ? 1。因此，对所有n≥1，T(n) = 2n ? 1 = ?(2n)。 使用递归树（recursion tree）可以形象地看到递推式的迭代过程。 例 T(n) = 2T(n/2) + n的递归树 T(n) = T(n/3) + T(2n/3) + n的递归树 主方法 主方法 在递归算法分析中，常需要求解如下形式的递推式： T(n) = aT(n/b) + f(n) 式中，a≥1和b＞1是常数，求解这类递推式的方法称为主方法。 a:子问题的数量； n/b指?n/b? 或 ?n/b? ：子问题的数据规模； f(n)是一个渐近正函数，把问题分解为子问题和把子问题归并起来的工作量。 主方法 根据这两项对结果的影响不同，分成三种情况讨论 两项同阶 前一项比后一项的阶高，对结果的影响大，忽略后一项 后一项比前一项的阶高，对结果的影响大，忽略前一项 渐近分析的记号 算法渐近复杂性分析中常用函数 （1）单调函数 单调递增：m ? n ? f(m) ? f(n) ; 单调递减：m ? n ? f(m) ? f(n); 严格单调递增：m n ? f(m) f(n); 严格单调递减：m n ? f(m) f(n). （2）取整函数 ? x ? ：不大于x的最大整数； ? x ? ：不小于x的最小整数。 取整函数的若干性质 x-1 ? x ? ? x ? ? x ? x+1； ? n/2 ? + ? n/2 ? = n; 对于n ? 0，a0, b0，有： ? ? n/a ? /b ? = ? n/ab ? ; ? ? n/a ? /b ? = ? n/ab ? ; ? a/b ? ? (a+(b-1))/b; ? a/b ? ? (a-(b-1))/b; f(x)= ? x ? , g(x)= ? x ? 为单调递增函数。 （3）多项式函数 p(n)= a0+a1n+a2n2+…+amnm；am0; f(n) = O(nk) ? f(n)多项式有界； f(n) = O(1) ? f(n) ? c; k ? m ? p(n) = O(nk) ; k ? m ? p(n) = ?(nk) ; k m ? p(n) = o(nk) . 算法渐近复杂性分析