算法导论 思考题4-1

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法导论 思考题4-1，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2618字，纯文字阅读大概需要4分钟。

内容图文

4-1（递归式例子）对下列每个递归式，给出T(n)的渐进上界和渐进下界。假定 $n\leq2$n≤2时T(n)时常数。给出尽量紧确的界，并验证其正确性。

不会主方法的先看以下这篇博客：
https://blog.csdn.net/qq_40512922/article/details/96932368

a.?$T(n)=2T(n/2)+n^4$T(n)=2T(n/2)+n4

证明：有$a=2,b=2,n^{log_ba}=n$a=2,b=2,nlogb?a=n，$f(n)=f(n^4)=\Omega(n^{\epsilon+1})$f(n)=f(n4)=Ω(n?+1)，其中$\epsilon=3$?=3。下面证明正则条件：$\exists c&lt;1,af(n/b)\leq cf(n)$?c<1,af(n/b)≤cf(n)

$2f(n/2)=\frac{n^4}{8} \leq cn^4$2f(n/2)=8n4?≤cn4

当 $c=1/8$c=1/8时,显然成立。因此$T(n)=\Theta(f(n))=\Theta(n^4)$T(n)=Θ(f(n))=Θ(n4)

---

b.?$T(n)=T(7n/10)+n$T(n)=T(7n/10)+n

证明：有$a=1,b=10/7,n^{log_ba}=1$a=1,b=10/7,nlogb?a=1，$f(n)=n=\Omega(n^{\epsilon+0})$f(n)=n=Ω(n?+0)，其中$\epsilon=1$?=1，下面证明正则条件：$\exists c&lt;1,af(n/b)\leq cf(n)$?c<1,af(n/b)≤cf(n)

$f(7n/10)=7n/10 \leq cn$f(7n/10)=7n/10≤cn

当$c=7/10$c=7/10时，显然成立。因此$T(n)=\Theta(f(n))=\Theta(n)$T(n)=Θ(f(n))=Θ(n)

---

c.?$T(n)=16T(n/4)+n^2$T(n)=16T(n/4)+n2

证明：有$a=16,b=4,n^{log_ba}=n^2$a=16,b=4,nlogb?a=n2，$f(n)=n^2=\Theta(n^2)$f(n)=n2=Θ(n2)。

因此，$T(n)=\Theta(nlgn)$T(n)=Θ(nlgn)。

---

d.?$T(n)=7T(n/3)+n^2$T(n)=7T(n/3)+n2

证明：有$a=7,b=3,n^{log_ba}\approx n^{1.7}$a=7,b=3,nlogb?a≈n1.7，$f(n)=n^2=\Omega(n^{1.7+\epsilon})$f(n)=n2=Ω(n1.7+?)，其中$\epsilon=0.3$?=0.3，下面证明正则条件。

$7f(n/3)=\frac{7n^2}{9} \leq cn^2$7f(n/3)=97n2?≤cn2

当$c=7/9$c=7/9时，显然成立。因此$T(n)=\Theta(f(n))=\Theta(n^2)$T(n)=Θ(f(n))=Θ(n2)

---

e.?$T(n)=7T(n/2)+n^2$T(n)=7T(n/2)+n2

证明：有$a=7,b=2,n^{log_ba}\approx n^{2.8}$a=7,b=2,nlogb?a≈n2.8，$f(n)=n^2=O(n^{2.8-\epsilon})$f(n)=n2=O(n2.8??)，其中$\epsilon=0.8$?=0.8。

因此$T(n)=\Theta(n^{log_ba})=\Theta(n^{log_27})$T(n)=Θ(nlogb?a)=Θ(nlog2?7)

---

f.?$T(n)=2T(n/4)+\sqrt n$T(n)=2T(n/4)+n?

证明：有$a=2,b=4,n^{log_ba}=n^{0.5}$a=2,b=4,nlogb?a=n0.5，$f(n)=n^{0.5}=\Theta(n^0.5)$f(n)=n0.5=Θ(n0.5)。
因此，$T(n)=\Theta(f(n)lgn)=\Theta(\sqrt{n}lgn)$T(n)=Θ(f(n)lgn)=Θ(n?lgn)

---

g.?$T(n)=T(n-2)+n^2$T(n)=T(n?2)+n2

证明：
$T(n)=\sum_{i=0}^{n}{(2i)^2}=\frac{2n(n+1)(2n+1)}{3}+T(0) = \Theta(n^3)$T(n)=i=0∑n?(2i)2=32n(n+1)(2n+1)?+T(0)=Θ(n3)

---

内容总结

以上是互联网集市为您收集整理的算法导论 思考题4-1全部内容，希望文章能够帮你解决算法导论 思考题4-1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---