算法设计与分析ch2proof.doc

证明： 而，，所以 其余各项可表示为 29． 令 情况1。 ，则有，从而有 ，而 所以 因此， 情况2。 ，则有，从而有 ，而 所以 因此， 情况3。 首先由知f(n)为g(n)中的一项，而每项均非负，所以 对常量c1与所有的n(b，有af(n/b)(cf(n)，则有ajf(n/bj)(cjf(n) 所以 而af(n/b)(cf(n)，所以 因此， 如果是底函数和顶函数，则用下面的方法 n(n；(n/b((n/b+1；((n/b(/b((n/b2+1/b+1；。。。(…(n/b(…/b((n/bi+1/bi-1…+1=n/bi+b/(b-1)；代入计算。 例子：T(n)=9T(n/3)+n；a=9，b=3，f(n)=n，则，而，其中(=1，所以为第一种情况，因此 T(n)=T(2n/3)+1，则为第二种情况， T(n)=3T(n/4)+n lg n，a=3，b=4，f(n)=nlg n，则，而，其中(≈0.2。进一步有，对足够大的n，有af(n/b)=3(n/4)lg(n/4)(3/4f(n)，其中c=3/4，所以属于第三种情况， 而T(n)=2T(n/2)+nlgn则不属于上面三种情况 a=2，b=2，f(n)=nlgn，，看上去象第三种情况，但是f(n)=nlgn渐进大于，并不是多项式大于。对任意的正常数(，比值渐进小于。因此，介于第二和第三种情况之间。