动机
分治算法会在当前输入上花费一部分工作量,再求解规模更小的子问题,并合并它们的答案。递归树按深度把总工作量分开计算。根据子问题个数与子问题规模缩小速度之间的比较,根、叶或各层合在一起都可能主导总代价。
这里的结果是一个刻意加以限制的主定理:各子问题的规模恰好相等,附加代价是正常数乘以某个幂,且输入规模是除数的幂。向下取整与向上取整的影响、规模不等的子问题以及带对数的附加代价,都需要另行论证。这些限制使计算精确,并揭示了三种情形为何出现。
定义
固定整数 a ≥ 1 a\ge1 a ≥ 1 与 b ≥ 2 b\ge2 b ≥ 2 ,实数 d ≥ 0 d\ge0 d ≥ 0 ,以及常数 c , t 0 > 0 c,t_0>0 c , t 0 > 0 。对 n = b k n=b^k n = b k (k k k 为非负整数),令
T ( 1 ) = t 0 , T ( n ) = a T ( n / b ) + c n d ( n > 1 ) . T(1)=t_0,\qquad T(n)=aT(n/b)+cn^d\quad(n>1). T ( 1 ) = t 0 , T ( n ) = a T ( n / b ) + c n d ( n > 1 ) . 项 c n d cn^d c n d 是规模为 n n n 的节点上的非递归工作量,t 0 t_0 t 0 是叶的代价。记 p = log b a p=\log_b a p = log b a ,即 a = b p a=b^p a = b p 。渐近陈述指的是在参数固定的情况下,n n n 沿着 b b b 的幂趋于无穷。
定理
对每个 k ≥ 0 k\ge0 k ≥ 0 及 n = b k n=b^k n = b k ,
T ( n ) = t 0 a k + c n d ∑ i = 0 k − 1 ( a / b d ) i . T(n)=t_0a^k+cn^d\sum_{i=0}^{k-1}(a/b^d)^i. T ( n ) = t 0 a k + c n d i = 0 ∑ k − 1 ( a / b d ) i . 当 k = 0 k=0 k = 0 时和式为空,该恒等式即 T ( 1 ) = t 0 T(1)=t_0 T ( 1 ) = t 0 。
在上述假设下,
T ( n ) = { Θ ( n d ) , a < b d , Θ ( n d log n ) , a = b d , Θ ( n p ) , a > b d . T(n)=\begin{cases}
\Theta(n^d),&a<b^d,\\
\Theta(n^d\log n),&a=b^d,\\
\Theta(n^p),&a>b^d.
\end{cases} T ( n ) = ⎩ ⎨ ⎧ Θ ( n d ) , Θ ( n d log n ) , Θ ( n p ) , a < b d , a = b d , a > b d . 在渐近记号中,对数的底数无关紧要。
证明思路
在深度 i < k i<k i < k 处有 a i a^i a i 个节点,每个节点的规模为 n / b i n/b^i n / b i 。它们的附加代价之和为 a i c ( n / b i ) d = c n d ( a / b d ) i a^ic(n/b^i)^d=cn^d(a/b^d)^i a i c ( n / b i ) d = c n d ( a / b d ) i 。递归在深度 k k k 处到达规模 1 1 1 ,共有 a k a^k a k 个叶,每个叶的代价为 t 0 t_0 t 0 。把各部分相加即得该恒等式。等价地,也可对 k k k 作归纳:代入递推式并平移和式的下标即可。
令 r = a / b d r=a/b^d r = a / b d 。若 r < 1 r<1 r < 1 ,则当 k ≥ 1 k\ge1 k ≥ 1 时,内部各层的和至少为 1 1 1 ,至多为 1 / ( 1 − r ) 1/(1-r) 1/ ( 1 − r ) ,因此它贡献 Θ ( n d ) \Theta(n^d) Θ ( n d ) 。由于 p < d p<d p < d ,叶的代价 t 0 n p = O ( n d ) t_0n^p=O(n^d) t 0 n p = O ( n d ) 。若 r = 1 r=1 r = 1 ,每个内部层的代价都是 c n d cn^d c n d ,这样的层共有 k = log b n k=\log_b n k = log b n 个。叶贡献 t 0 n d t_0n^d t 0 n d ,所以总代价为 Θ ( n d log n ) \Theta(n^d\log n) Θ ( n d log n ) 。
若 r > 1 r>1 r > 1 ,几何和为 ( r k − 1 ) / ( r − 1 ) = Θ ( r k ) (r^k-1)/(r-1)=\Theta(r^k) ( r k − 1 ) / ( r − 1 ) = Θ ( r k ) (r r r 固定)。此外 n d r k = n d ( a / b d ) k = a k = n p n^dr^k=n^d(a/b^d)^k=a^k=n^p n d r k = n d ( a / b d ) k = a k = n p 。内部工作量与叶的代价都是 O ( n p ) O(n^p) O ( n p ) ,而正的叶项本身已经是 Ω ( n p ) \Omega(n^p) Ω ( n p ) 。这就证明了最后一种情形。正的附加代价与正的基础代价排除了相互抵消的可能,并提供了这里用到的下界。
证明透视
比较整层的代价 关键的比值是 a / b d a/b^d a / b d :每深入一层,节点数乘以 a a a ,而每个节点上的工作量则缩小为原来的 1 / b d 1/b^d 1/ b d 。只计入其中一种变化,就会忽略两者之间的竞争。
各项假设在特定的地方使用。固定的 a a a 、b b b 、d d d 使 r = a / b d r=a/b^d r = a / b d 为常数,因此几何和是 Θ ( 1 ) \Theta(1) Θ ( 1 ) 、Θ ( k ) \Theta(k) Θ ( k ) 或 Θ ( r k ) \Theta(r^k) Θ ( r k ) ,其常数不依赖于 n n n 。正的 c c c 与 t 0 t_0 t 0 提供下界,因为没有任何一项能抵消另一项。限制 n = b k n=b^k n = b k 使每一层的规模都是精确的。最后一种情形借恒等式 n d r k = a k = n p n^dr^k=a^k=n^p n d r k = a k = n p 收尾,它把最大的一层代价与叶层等同起来。
例题详解
对于 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T ( n ) = 4 T ( n /2 ) + n (基础代价为正常数),有 a = 4 a=4 a = 4 ,b = 2 b=2 b = 2 ,d = 1 d=1 d = 1 ,p = 2 p=2 p = 2 。因为 4 > 2 4>2 4 > 2 ,总代价为 Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) 。内部各层的代价随深度逐层翻倍,叶贡献 n 2 n^2 n 2 的量级。
对于 T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n ,每个内部层的代价都是 n n n 。这样的层有 log 2 n \log_2 n log 2 n 个,叶有 n n n 个,所以总代价为 Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) ,而不仅仅是 Θ ( n ) \Theta(n) Θ ( n ) 。
对于 T ( n ) = 2 T ( n / 2 ) + n 2 T(n)=2T(n/2)+n^2 T ( n ) = 2 T ( n /2 ) + n 2 ,相邻两层代价之比为 1 / 2 1/2 1/2 。根贡献 n 2 n^2 n 2 ,所有内部层合起来的贡献小于 2 n 2 2n^2 2 n 2 ;叶贡献 n n n 的量级。因此总代价为 Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) 。
常见错误
反例模式
一层的代价不是总代价 在 T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n 中,仅仅观察到一层的代价为 n n n ,并不能证明总代价是线性的。代价相同的层共有对数个,由此产生了额外的因子 log n \log n log n 。
该定理不能直接用于 T ( n ) = T ( n − 1 ) + n T(n)=T(n-1)+n T ( n ) = T ( n − 1 ) + n (其子问题规模不是 n / b n/b n / b ),也不能直接用于 T ( n ) = 2 T ( n / 2 ) + n log n T(n)=2T(n/2)+n\log n T ( n ) = 2 T ( n /2 ) + n log n (其附加代价不是固定常数乘以 n d n^d n d )。这两者都可以用其他求和方法分析;但不加证明地把它们代入这三种情形是无效的。
对 T ( n ) = 2 T ( n / 2 ) + n log 2 n T(n)=2T(n/2)+n\log_2 n T ( n ) = 2 T ( n /2 ) + n log 2 n ,也许会取 d = 1 d=1 d = 1 ,见到 a = b d a=b^d a = b d ,便答 Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) 。但附加代价并不是常数乘以幂。在深度 i i i 处,2 i 2^i 2 i 个节点各付 ( n / 2 i ) ( k − i ) (n/2^i)(k-i) ( n / 2 i ) ( k − i ) ,其中 k = log 2 n k=\log_2 n k = log 2 n ,所以内部代价为 n k ( k + 1 ) / 2 n\,k(k+1)/2 n k ( k + 1 ) /2 ,T ( n ) = Θ ( n log 2 n ) T(n)=\Theta(n\log^2 n) T ( n ) = Θ ( n log 2 n ) ;例如 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 时,T ( 4 ) = 16 = 4 ⋅ 3 + 4 T(4)=16=4\cdot3+4 T ( 4 ) = 16 = 4 ⋅ 3 + 4 。
展开一棵小树
通过写出最初几步代入,可以检验逐层公式。设 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T ( n ) = 4 T ( n /2 ) + n ,T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 。则
T ( n ) = 4 ( 4 T ( n / 4 ) + n / 2 ) + n = 16 T ( n / 4 ) + 2 n + n . T(n)=4\bigl(4T(n/4)+n/2\bigr)+n=16T(n/4)+2n+n. T ( n ) = 4 ( 4 T ( n /4 ) + n /2 ) + n = 16 T ( n /4 ) + 2 n + n .
在最初三个内部层,代价依次为 n , 2 n , 4 n n,2n,4n n , 2 n , 4 n 。重数 4 i 4^i 4 i 与子问题规模 n / 2 i n/2^i n / 2 i 合起来给出每层代价 n 2 i n2^i n 2 i 。这与只沿着一条从根到叶的路径观察不同,因为那样在每一层只看到众多子问题中的一个。
对于 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 与 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T ( n ) = 4 T ( n /2 ) + n ,n = 8 n=8 n = 8 时各层代价为 8 8 8 、16 16 16 和 32 32 32 ,之后是 4 3 = 64 4^3=64 4 3 = 64 个代价为一的叶。因此 T ( 8 ) = 120 T(8)=120 T ( 8 ) = 120 。直接代入的结果一致:T ( 2 ) = 4 ⋅ 1 + 2 = 6 T(2)=4\cdot1+2=6 T ( 2 ) = 4 ⋅ 1 + 2 = 6 ,T ( 4 ) = 4 ⋅ 6 + 4 = 28 T(4)=4\cdot6+4=28 T ( 4 ) = 4 ⋅ 6 + 4 = 28 ,T ( 8 ) = 4 ⋅ 28 + 8 = 120 T(8)=4\cdot28+8=120 T ( 8 ) = 4 ⋅ 28 + 8 = 120 。叶的代价必须与基础情形保持一致地计入。
叶的个数是 a k = n log b a a^k=n^{\log_b a} a k = n l o g b a ,一般并不等于 n n n 。在常见的 a = b a=b a = b 情形下它等于 n n n ,但当 a = 4 , b = 2 a=4,b=2 a = 4 , b = 2 时它是 n 2 n^2 n 2 。所有节点的总数是另一个几何和,当 a > 1 a>1 a > 1 时为 1 + a + ⋯ + a k 1+a+\cdots+a^k 1 + a + ⋯ + a k ;由于节点的代价取决于其规模,仅凭它并不能确定运行时间。当 a = 1 a=1 a = 1 时,递归树是一条含 k + 1 k+1 k + 1 个节点的单一路径。
概念视角 代数
把层和看成一阶线性递推式 令 S ( k ) = T ( b k ) S(k)=T(b^k) S ( k ) = T ( b k ) 、β = b d \beta=b^d β = b d ,递推式变成 S ( k ) = a S ( k − 1 ) + c β k S(k)=aS(k-1)+c\beta^k S ( k ) = a S ( k − 1 ) + c β k :齐次解为 a k a^k a k ,强迫项为 β k \beta^k β k 。若 β ≠ a \beta\ne a β = a ,则 S ( k ) = ( t 0 − B ) a k + B β k S(k)=(t_0-B)a^k+B\beta^k S ( k ) = ( t 0 − B ) a k + B β k ,其中 B = c β / ( β − a ) B=c\beta/(\beta-a) B = c β / ( β − a ) ,a a a 与 β \beta β 中较大者胜出:a > β a\gt\beta a > β 时由叶主导,a < β a\lt\beta a < β 时由根主导。若 β = a \beta=a β = a ,强迫项与齐次解共振,S ( k ) = a k ( t 0 + c k ) S(k)=a^k(t_0+ck) S ( k ) = a k ( t 0 + c k ) ,因子 k = log b n k=\log_b n k = log b n 就是多出来的对数。对 a = 4 , b = 2 , d = 1 a=4,b=2,d=1 a = 4 , b = 2 , d = 1 ,得 S ( k ) = 2 ⋅ 4 k − 2 k S(k)=2\cdot4^k-2^k S ( k ) = 2 ⋅ 4 k − 2 k ,S ( 3 ) = 120 S(3)=120 S ( 3 ) = 120 。
代入法证明及其局限
递归树给出一个猜测的界,归纳法则可以验证所提出的界。例如,在 2 2 2 的幂上令 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 ,T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n 。精确公式为 T ( n ) = n log 2 n + n T(n)=n\log_2 n+n T ( n ) = n log 2 n + n 。它在 n = 1 n=1 n = 1 时成立。若它在 n / 2 n/2 n /2 处成立,则
2 ( ( n / 2 ) log 2 ( n / 2 ) + n / 2 ) + n = n log 2 n + n . 2\left((n/2)\log_2(n/2)+n/2\right)+n
=n\log_2 n+n. 2 ( ( n /2 ) log 2 ( n /2 ) + n /2 ) + n = n log 2 n + n .
因此该表达式在每个 2 2 2 的幂处都成立。这一证明同时检验了基础情形与归纳步骤;它不断言任何关于递推式所声明定义域之外的取值。
对于较宽松的渐近上界,归纳假设有时需要加上一个低阶修正项才能闭合。盲目地在每个规模上假设 T ( n ) ≤ C n log n T(n)\le Cn\log n T ( n ) ≤ C n log n ,可能在基础情形 n = 1 n=1 n = 1 处失败,因为 log 1 = 0 \log1=0 log 1 = 0 而 T ( 1 ) > 0 T(1)>0 T ( 1 ) > 0 。此时可以改用足够大的阈值,或加上一个线性项,或使用 log ( 2 n ) \log(2n) log ( 2 n ) ;每一种选择都必须加以验证。成功的归纳是对所述范围和常数的证明,而不仅仅是由树形图提示的猜测。
精确恒等式也澄清了下界。根贡献 c n d cn^d c n d ,叶贡献 t 0 n p t_0n^p t 0 n p ,因此当各代价非负时,两者各自都是下界。在各层相等的情形中,两者单独都不能给出额外的对数因子;把全部 k k k 个非负的层代价相加才可以。如果模型允许负的附加代价或相互抵消,这些下界论证就需要不同的假设。
一个单独的取整例子
考虑对每个正整数定义的递推式:U ( 1 ) = t 0 > 0 U(1)=t_0>0 U ( 1 ) = t 0 > 0 ,且
U ( n ) = U ( ⌊ n / 2 ⌋ ) + U ( ⌈ n / 2 ⌉ ) + c n ( n ≥ 2 ) , U(n)=U(\lfloor n/2\rfloor)+U(\lceil n/2\rceil)+cn\qquad(n\ge2), U ( n ) = U (⌊ n /2 ⌋) + U (⌈ n /2 ⌉) + c n ( n ≥ 2 ) ,
其中 c > 0 c>0 c > 0 。对任意 n n n ,该递推式并不直接被精确的等规模定理所涵盖,但它的树可以独立地加以估计。每个内部节点把其规模分成两个正整数,其和等于父节点的规模。恰有 n n n 个规模为一的叶。深度 i < ⌊ log 2 n ⌋ i<\lfloor\log_2 n\rfloor i < ⌊ log 2 n ⌋ 处的所有节点规模至少为二,所以它们的规模之和为 n n n ,该层代价为 c n cn c n 。从根到叶的任何路径所含的内部层都不超过 ⌈ log 2 n ⌉ \lceil\log_2 n\rceil ⌈ log 2 n ⌉ 个,且任一层上各节点的规模之和至多为 n n n 。因此
c n ⌊ log 2 n ⌋ + t 0 n ≤ U ( n ) ≤ c n ⌈ log 2 n ⌉ + t 0 n , cn\lfloor\log_2 n\rfloor+t_0n
\le U(n)\le cn\lceil\log_2 n\rceil+t_0n, c n ⌊ log 2 n ⌋ + t 0 n ≤ U ( n ) ≤ c n ⌈ log 2 n ⌉ + t 0 n ,
这就证明了当 n ≥ 2 n\ge2 n ≥ 2 时 U ( n ) = Θ ( n log n ) U(n)=\Theta(n\log n) U ( n ) = Θ ( n log n ) 。
为了证明关于深度的陈述:经过 i i i 次均衡划分后,每个现存子问题的规模要么是 ⌊ n / 2 i ⌋ \lfloor n/2^i\rfloor ⌊ n / 2 i ⌋ ,要么是 ⌈ n / 2 i ⌉ \lceil n/2^i\rceil ⌈ n / 2 i ⌉ 。这可由对“把每个规模划分为其下取整一半与上取整一半”作归纳而得。在 i = ⌊ log 2 n ⌋ i=\lfloor\log_2 n\rfloor i = ⌊ log 2 n ⌋ 之前,较小的规模至少为二;到 i = ⌈ log 2 n ⌉ i=\lceil\log_2 n\rceil i = ⌈ log 2 n ⌉ 时,所有剩余的规模都是一。这个论证处理了不均匀的最后一层,而不是假装每个分支的深度都相同。
对于 n = 5 n=5 n = 5 ,第一次划分得到规模 2 2 2 与 3 3 3 。下一次划分,规模为二的节点产生规模 1 , 1 1,1 1 , 1 ,规模为三的节点产生规模 1 , 2 1,2 1 , 2 。其中一个规模为二的节点还需要再划分一次。共有五个叶,而各内部层的规模之和依次为 5 5 5 、5 5 5 、2 2 2 。附加代价总计 12 c 12c 12 c ,叶的代价为 5 t 0 5t_0 5 t 0 ;取整的界包含了这个值。
从递推式到算法结论
递推式必须与所分析的算法相符。要数清楚进行了多少次递归调用、它们接收的规模是多少,以及这些调用之外还剩下多少工作。二分搜索只对大约一半的输入进行一次递归调用,而不是两次;合并排序进行两次调用,并带有线性的合并工作。如果某些输入使调用提前停止,则精确的递推式可能只是最坏情形的界。只有在建立了递推式与实现之间的联系之后,递推式的数学解才是有用的。
附加代价是在选定模型下的代价。计数比较次数、算术运算次数、内存分配或位运算,可能得到不同的递推式。对于位长随输入增长的整数,常数时间算术的假设可能并不恰当。类似地,描述总工作量的递推式并不自动描述内存峰值或并行运行时间:这些量合并递归调用的方式不同。
检查边界情形
当 a = 1 a=1 a = 1 且 d = 0 d=0 d = 0 时,树是一条链,每个内部节点的附加代价为常数。它的长度是 log b n \log_b n log b n ,等层公式给出 Θ ( log n ) \Theta(\log n) Θ ( log n ) 。当 a = 1 a=1 a = 1 且 d > 0 d>0 d > 0 时,沿该链的附加代价按几何级数递减,由根主导。当 n = 1 n=1 n = 1 时,精确的和式没有内部项,返回基础代价。渐近表达式 n d log n n^d\log n n d log n 在 n = 1 n=1 n = 1 时不必为正;Θ \Theta Θ 描述的是足够大的输入,而不是每个规模下的精确公式。
如果所声称的递推式中的常数依赖于 n n n ,则几何比较可能改变。该定理把 a , b , c , d , t 0 a,b,c,d,t_0 a , b , c , d , t 0 固定,而输入规模增长。例如,把像 log n \log n log n 这样缓慢增长的因子当作常数,会改变附加代价,并可能丢掉整整一个对数因子。在应用有名称的定理之前先写下假设,往往是发现这类错误的最快方法。
定理之外的对数型附加代价
同样的逐层方法可以求解一些不在三情形陈述之内的递推式,但必须重新计算层和。设 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 ,并在 2 2 2 的幂上令 T ( n ) = 2 T ( n / 2 ) + n log 2 n T(n)=2T(n/2)+n\log_2 n T ( n ) = 2 T ( n /2 ) + n log 2 n 。在深度 i < k = log 2 n i<k=\log_2 n i < k = log 2 n 处,2 i 2^i 2 i 个子问题的规模均为 n / 2 i n/2^i n / 2 i ,其对数为 k − i k-i k − i 。因此它们的附加代价之和为 n ( k − i ) n(k-i) n ( k − i ) 。内部代价为
n ∑ i = 0 k − 1 ( k − i ) = n k ( k + 1 ) 2 , n\sum_{i=0}^{k-1}(k-i)=n\frac{k(k+1)}2, n i = 0 ∑ k − 1 ( k − i ) = n 2 k ( k + 1 ) ,
n n n 个叶再加上 n n n 。故对足够大的 2 2 2 的幂,T ( n ) = Θ ( n ( log n ) 2 ) T(n)=\Theta(n(\log n)^2) T ( n ) = Θ ( n ( log n ) 2 ) 。若把附加代价中的对数当作常数,就会错误地得到 Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) 。
这一推导是一次新的计算,而不是对所述幂型附加代价定理的应用。它说明了一种一般策略:写出深度 i i i 处一个节点的工作量,乘以该深度的节点数,确定精确的终止深度,然后求和。如果这些量依赖于路径,或输入的规模不等,则可能不再存在单一的统一层公式。仍然可以像取整例子那样对树加以估计,但必须针对该递推式证明所得的界。
即使实现在递归调用之间重用内存,递归树的图景描述的仍然是代价的算术总和。它并不意味着所有节点同时存在于内存中。反之,并行实现可能同时计算相互独立的调用,因此其耗时取决于关键路径与调度,而不是简单地取决于总工作量。在解释递推式的解之前,应先说明该递推式代表的是哪种资源。
最后的算术检验
对于由根主导的例子 T ( n ) = 2 T ( n / 2 ) + n 2 T(n)=2T(n/2)+n^2 T ( n ) = 2 T ( n /2 ) + n 2 (T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 ),精确的和式给出
T ( n ) = n + n 2 ∑ i = 0 k − 1 2 − i = n + 2 n 2 ( 1 − 2 − k ) = 2 n 2 − n . T(n)=n+n^2\sum_{i=0}^{k-1}2^{-i}=n+2n^2(1-2^{-k})=2n^2-n. T ( n ) = n + n 2 i = 0 ∑ k − 1 2 − i = n + 2 n 2 ( 1 − 2 − k ) = 2 n 2 − n .
该公式在 n = 1 n=1 n = 1 时成立,并且把它代入递推式能在更大的 2 2 2 的幂处重现它。特别地,它的首项为正且是二次的。在少数几个小的输入上做精确计算,可以发现放错的叶项或错误的层比值,尽管有限次检验不能证明对所有输入成立的渐近界。
总结
层比值 a / b d a/b^d a / b d 比较了节点数的增长与每个节点工作量的下降。递减的几何级数由根主导,各层代价相等则累积出一个对数因子,递增的级数则由叶主导。在所述假设下,精确的逐层恒等式证明了这些结论。
练习
快速检查
(对 2 2 2 的幂上的 T ( n ) = 8 T ( n / 2 ) + n 2 T(n)=8T(n/2)+n^2 T ( n ) = 8 T ( n /2 ) + n 2 (基础代价为正常数)进行分类。)
解答 · 答案 这里 a = 8 > b d = 4 a=8>b^d=4 a = 8 > b d = 4 ,且 p = 3 p=3 p = 3 ,所以 T ( n ) = Θ ( n 3 ) T(n)=\Theta(n^3) T ( n ) = Θ ( n 3 ) 。
快速检查
(对 2 2 2 的幂上的 T ( n ) = T ( n / 2 ) + 1 T(n)=T(n/2)+1 T ( n ) = T ( n /2 ) + 1 进行分类。)
解答 · 答案 这里 a = b d = 1 a=b^d=1 a = b d = 1 ,d = 0 d=0 d = 0 ,所以对足够大的 2 2 2 的幂,T ( n ) = Θ ( log n ) T(n)=\Theta(\log n) T ( n ) = Θ ( log n ) 。
快速检查
(对 3 3 3 的幂上的 T ( n ) = 3 T ( n / 3 ) + n 2 T(n)=3T(n/3)+n^2 T ( n ) = 3 T ( n /3 ) + n 2 进行分类。)
解答 · 答案 这里 a = 3 < 9 = b d a=3<9=b^d a = 3 < 9 = b d ,所以 T ( n ) = Θ ( n 2 ) T(n)=\Theta(n^2) T ( n ) = Θ ( n 2 ) 。
快速检查
(当 n = 8 n=8 n = 8 时,T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n 的递归树有多少个叶?)
解答 · 答案 树的深度为 log 2 8 = 3 \log_2 8=3 log 2 8 = 3 ,叶的个数为 2 3 = 8 2^3=8 2 3 = 8 。