算法导论4.5 Exercises 答案

4.5-1

a

$a=2,b=4,f(n)=1,\log _b a=\dfrac{1}{2}$

因此根据第一个条件，$T(n)=\Theta(n^{\frac{1}{2}})=\Theta(\sqrt{n})$

b

$a=2,b=4,f(n)=\sqrt{n},\log _b a=\dfrac{1}{2}$

因此根据第二个条件，得到$k=0$，最终$T(n)=\Theta(n^{\frac{1}{2}}\lg ^1 n)=\Theta(\sqrt{n}\cdot \lg n)$

c

$a=2,b=4,f(n)=\sqrt{n}\lg^2 n,\log _b a=\dfrac{1}{2}$

因此根据第二个条件，得到$k=2$，最终$T(n)=\Theta(n^{\frac{1}{2}}\lg ^3 n)=\Theta(\sqrt{n}\cdot \lg^3 n)$

d

$a=2,b=4,f(n)=n,\log _b a=\dfrac{1}{2}$

因此根据第三个条件，可以构造出$c=\dfrac{1}{2}$，最终$T(n)=\Theta(n)$

e

$a=2,b=4,f(n)=n^2,\log _b a=\dfrac{1}{2}$

因此根据第三个条件，可以构造出$c=\dfrac{1}{8}$，最终$T(n)=\Theta(n^2)$

4.5-2

新设计的算法的运行时间递推式为$T(n)=aT(n/4)+\Theta(n^2)$。

假设运用主定理的第一个条件，那么其时间复杂度为$\Theta(n^{\log_4 a})$。那么如果要比Strassen算法快，那么就有$\log _4 a<\lg 7$，最终得到$a<49$，即$a=48$。

4.5-3

$a=1,b=2,f(n)=\Theta(1),\log _b a=0$

因此根据第二个条件，得到$k=0$，最终$T(n)=\Theta(n^{0}\lg ^1 n)=\Theta(\lg n)$

4.5-4

化简后，问题变成证明$\forall c<1,\exists n_0>0,\forall n\ge n_0,\lg (n/2)\le c\lg n$都不成立。

即证明$\forall c<1,\exists n_0>0,\forall n\ge n_0,(1-c)\lg n-1>0$均成立。

令$f(n)=(1-c)\lg n-1$。那么$f’(n)=\dfrac{1}{(1-c)\cdot\ln 2\cdot n}$。由于$1-c>0$，因此$f’(n)>0$，故$f(n)$是单调递增的。

那么构造出$n_0=\left\lceil2^{1/(1-c)}\right\rceil+1$，对于$\forall n\ge n_0,f(n)\ge 0$均成立。原结论得证。

为了方便证明，假设$a\ge 1$（因为子问题的个数不能是$0\sim 1$直接的小数。）由于$\epsilon > 0$，因此$\lg n=o(n^{\log _b a+\epsilon})$，故不满足题目中的条件。

4.5-5

可以发现，$0\le\lceil x\rceil - x<1$总成立，因此函数$f(n)=2^{\lceil\lg n\rceil}$总满足$n\le f(n) < 2n$，不难发现有$f(n)="\Theta(n)$。也就是说，存在$a\ge" 1,b>1,\epsilon>0$使得$f(n)=\Omega(n^{\log _b a+\epsilon})$成立，即只需要满足$\log_b a+\epsilon \le 1$即可。由于要求$\epsilon>0$，因此只需要构造出来的$a< b$即可。

为证明$a=2,b=3$时不满足正则条件，那么只需要证明存在无数个充分大的$n,2\cdot 2^{\lceil \lg n/3\rceil}>2^{\lceil \lg n\rceil}$成立即可。

经过代数转换后，最终也就是证明$\lceil \lg n-\lg (2/3) \rceil-\lceil\lg n\rceil>0$即可。

可以发现，对于所有正整数$m$，如果正整数$n\in\left[\dfrac{2^{m+1}}{3},2^m\right)$，那么上面的不等式便成立。这样的$n$有无穷多个，并且充分大。

只要$c$取的足够小（逼近但大于$1$），那么存在无数个充分大的$n,2\cdot 2^{\lceil \lg n/3\rceil}>c\cdot2^{\lceil \lg n\rceil}$成立。

因此，当$a=2,b=3$时，不存在$c<1$使得对于所有充分大的$n,af(n/b)\le cf(n)$都成立。此时不满足该正则条件。而$\epsilon$仅需要满足$\log_b a+\epsilon \le 1$。那么可以取$\epsilon=1-\log_3 2$。