算法设计与分析 作业1

第一周作业

1. $T(n) = T\left(\frac34n\right) + n$

$${large} \large \begin{align*} &\text{推测递归式的解为 }T(n) = O\left(n\right), 假设解的形式是T(n) = a'n + n = an\\ &代入递归式得\ an = \frac34an + n\quad\Rightarrow a=4\\ \therefore\ &T(n) = 4n\\ \end{align*}$$

2. $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n$

$$\large \begin{align*} T(n) &= \sqrt{n} \cdot T(\sqrt{n}) + n\\ &=n^{\frac12}\cdot n^{\left(\frac12\right)^2}\cdot T\left(n^{\left(\frac12\right)^2}\right)+ \left(n+n^{\frac12}\cdot n^{\frac12} \right)\\ &=n^{\frac12}\cdot n^{\left(\frac12\right)^2}\cdot n^{\left(\frac12\right)^3} \cdot T\left(n^{\left(\frac12\right)^3}\right)+ \left(n + n^{\frac12}\cdot n^{\frac12} + n^{\frac12}\cdot n^{\left(\frac12\right)^2}\cdot n^{\left(\frac12\right)^2} \right)\\ &= \cdots\\ &= n^{\Large\sum_{i=1}^{L}{\left(\frac12\right)^i} }\cdot T(1) + \sum\limits_{i=1}^{L}{n^{\Large\left(\sum_{j=1}^{i}{\left(\frac12\right)^j}\right)+\left(\frac12\right)^i} }, L=\log_2{n}\\ &= n^{1-2^{-L} }\cdot T(1) + \sum\limits_{i=1}^{L}{n^{1-2^{-i}+2^{-i} } }, L=\log_2{n}\\ &= n^{1-\frac1n}\cdot T(1) + n\log_2{n} \end{align*}$$

3. $T(n) = \frac14 T\left(\frac14 n\right) + \frac34 T\left(\frac34 n\right) + 1$

$$\begin{align*} &\frac14 T\left(\frac14 n\right) + \frac34 T\left(\frac14 n\right) + 1 \leq T(n) \leq \frac14 T\left(\frac34 n\right) + \frac34 T\left(\frac34 n\right) + 1\\ \large{即}\normalsize&T\left(\frac14 n\right) + 1 \leq T(n) \leq T\left(\frac34 n\right) + 1\\ &T(n) \geq T\left(\frac14 n\right) + 1 = T(1) + \log_4{n} = \Omega\left(\log{n}\right)\\ &T(n) \leq T\left(\frac34 n\right) + 1 = T(1) + \log_{\frac43}{n} = O\left(\log{n}\right)\\ \therefore\ & T(n) = \Theta\left(\log{n}\right) \end{align*}$$

4. $T(n) = T(\frac12n)+T(\frac13n)+T(\frac16n)+n\log{n}$

$$\begin{align*} &\frac{1}{2^\rho}+\frac{1}{3^\rho}+\frac{1}{6^\rho}=1\Rightarrow \rho=1\\ &\int_1^n{\frac{f\left(u\right)}{u^{\rho+1} } }\dd{u}=\int_1^n{\frac{\log{u} }{u} }\dd{u}=\frac{1}{\ln{2} }\int_1^n{\ln{u} }\dd{\left(\ln u\right)}=\frac{\ln^2{n} }{2\ln{2} }\\ \therefore\ &T(n)=\Theta\left(n^\rho\left(1+\int_1^n{\frac{f\left(u\right)}{u^{\rho+1} } }\dd{u}\right)\right)=\Theta\left(n+\frac{n\ln^2{n} }{2\ln2}\right)=\Theta(n\ln^2{n})\\ \end{align*}$$

5. $T(n)=3T(\frac13n)+3T(\frac23n)+n^2$

$$\begin{align*} &3\cdot\left(\frac{1}{3}\right)^\rho+3\cdot\left(\frac{2}{3}\right)^\rho=1 \Rightarrow \rho=3\\ &\int_1^n{\frac{f\left(u\right)}{u^{\rho+1} } }\dd{u}=\int_1^n{\frac{1}{u^2} }\dd{u}=1-\frac{1}{n}\\ \therefore\ &T(n)=\Theta\left(n^\rho\left(1+\int_1^n{\frac{f\left(u\right)}{u^{\rho+1} } }\dd{u}\right)\right)=\Theta\left(2n^3-n^2\right)=\Theta(n^3)\\ \end{align*}$$

6.

$$\begin{align*} \large苹果:&\quad (1+x)\cdot(1+x)=(1+x)^2\\ \large香蕉:&\quad 1+x+x^2+x^3\\ \large无花果:&\quad 1+x^6+x^{12}+x^{18}+\cdots=\frac{1}{1-x^6}\\ \large芒果:&\quad 1+x^2+x^4\\ \large桃子:&\quad1+x^4+x^8+x^{12}+\cdots=\frac{1}{1-x^4}\\ G(x)=&(1+x)^2\cdot(1+x+x^2+x^3)\cdot\frac{1}{1-x^6}\cdot(1+x^2+x^4)\cdot\frac{1}{1-x^4}\\ =&(1+x)^2\cdot \frac{1-x^4}{1-x}\cdot \frac{1}{1-x^6}\cdot \frac{1-x^6}{1-x^2}\cdot \frac{1}{1-x^4}\\ =&\frac{1+x}{\left(1-x\right)^2}\\ =&(1+x)\cdot\left(1-x\right)^{-2}\\ =&(1+x)\cdot \sum\limits_{n=0}^{+\infty}{-2\choose n}(-x)^n\\ =&(1+x)\cdot \sum\limits_{n=0}^{+\infty}{\frac{(-2)\cdot(-2-1)\cdots\left(-2-\left(n-1\right)\right)}{n!} }(-x)^n\\ =&(1+x)\cdot \sum\limits_{n=0}^{+\infty}{\frac{(n+1)\cdot n\cdots2\cdot1}{n!} }\left(-1\right)^n (-x)^n\\ =&(1+x)\cdot \sum\limits_{n=0}^{+\infty}(n+1) x^n\\ =& 1+\sum\limits_{n=1}^{+\infty}(n+1) x^n+\sum\limits_{n=1}^{+\infty}n x^n\\ =& 1+\sum\limits_{n=1}^{+\infty}(2n+1) x^n\\ =& \sum\limits_{n=0}^{+\infty}(2n+1) x^n\\ \therefore\ \ &x^n\large项的系数为\normalsize 2n+1 \end{align*}$$