算法导论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\)。