请教算法导论中 T(n) = 2T(n/2) + nlgn 为什么不能用主定理【c语言吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：561,123贴子：
请教算法导论中 T(n) = 2T(n/2) + nlgn 为什么不能用主定理收藏
T(n) = 2T(n/2) + nlgna=2, b=2, f(n) = nlgn,
n^(log(b, a)) = n^(log(2, 2))
= n；书上的原话是“问题出在它并不是多项式意义上的大于。对任意常数 e，比值 f(n) / (n^(log(a, b))) = nlgn/n = lgn 都渐进小于 n^e。”根据书里的上下文， e = | f(n) 的次数系数 - log(a, b) |。上面假设 lgn = n^a(a & 1)，那么 nlgn = n^(1 + a)； 则 e = | (1 + a) - log(2, 2) | = a, 那么lgn 应该是等于 n^e 的，为什么书上说是渐进小于 n^e 呢？另外书上和网上对 “多项式小于” 都没有具体描述，这东西到底是什么？注：1、鉴于书写方便 log(a, b) 为以 a 为底 b 的对数。2、主定理公式为 T(n) = aT(n/b) + f(n)
找c语言?来博为峰学C语言开发,C语言开发课程,免费训练营火热开启中!找c语言?来这里学C语言开发,抢!!!C语言开发课程试听名额,总监名师主讲.
lgN 一定是渐进小于 N^e , e & 0 其余的没看懂你在写什么。。。
T(n) = 2T(n/2) + nlogn = O(nlogn*logn)
我想大概知道什么是“多项式小于（大于）”了 但 lgn 为什么会渐近 n^a 呢？
4楼正解这个只能用递归做，展开Tn=n+nlgn+nlgn/2+nlgn/3+.....发现这是一个等差数列lgn/2-lgn=1/2....则Tn=O(nlgn*lgn)我们算法作业有这道题，算了半天才算出来....
可以用主定理，导论有误，参考维基百科 case 2
登录百度帐号推荐应用求解递归式T（n）=4T(n/2)+n?，求会的帮忙解答一下.
12-05-22 &第4章思考题 - 简书
第4章思考题
4-1 （递归式例子）对下列每个递归式，给出T(n)的渐近上界和下界。假定n&=2时T(n)是常数。给出尽量紧确的界，并验证其正确性。
a. T(n) = 2T(n/2) + n^4
b. T(n) = T(7n/10) + n
c. T(n) = 16T(n/4) + n^2
d. T(n) = 7T(n/3) + n^2
e. T(n) = 7T(n/2) + n^2
f. T(n) = 2T(n/4) + sqrt(n)
g. T(n) = T(n-2) + n^2
4-2 （参数传递代价）我们有一个贯穿本书的假设——过程调用的参数传递花费常量时间，即使传递一个N个元素的数组也是如此。在大多数系统中，这个假设是成立的，因为传递的是指向数组的指针，而非数组本身。本题讨论三种参数传递策略：
数组通过指针来传递。时间=THETA(1)。
数组通过元素复制来传递。时间=THETA(N)，其中N是数组的规模。
传递数组时，只复制过程可能访问的子区域。若子数组A[p..q]被传递，则时间=THETA(q-p+1)。
a. 考虑在有序数组中查找元素的递归二分查找算法（参见练习2.3-5）。分别给出上述三种参数传递策略下，二分查找最坏情况运行时间的递归式，并给出递归式解的好的上界。令N为原问题的规模，n为子问题的规模。
b. 对2.3.1节的MERGE-SORT算法重做(a)。
4-3 （更多的递归式例子） 对下列每个递归式，给出T(n)的渐近上界和下界。假定对足够小的n，T(n)是常数。给出尽量紧确的界，并验证其正确性。
a. T(n) = 4T(n/3) + nlgn
b. T(n) = 3T(n/3) + n/lgn
c. T(n) = 4T(n/2) + n^2sqrt(n)
d. T(n) = 3T(n/3-2) + n/2
e. T(n) = 2T(n/2) + n/lgn
f. T(n) = T(n/2) + T(n/4) + T(n/8) + n
g. T(n) = T(n-1) + 1/n
h. T(n) = T(n-1) + lgn
i. T(n) = T(n-2) + 1/lgn
j. T(n) = sqrt(n)T(sqrt(n)) + n
4-4 （斐波那契数） 本题讨论递归式（3.22）定义的斐波那契数的性质。我们将使用生成函数技术来求解斐波那契递归式。生成函数（又称为形式幂级数）
其中Fi为第i个斐波那契数。
//吐槽：步骤都写出来了还让人证明......?
d. 利用(c)的结果证明：对i&0, Fi = theta^I/sqrt(5)，结果舍入到最接近的整数。（提示：观察到
4-5 （芯片检测）Diogenes教授有n片可能完全一样的集成电路芯片，原理上可以用来相互检测。教授的测试夹具同时只能容纳两块芯片。当夹具装载上时，每块芯片都检测另一块，并报告它是好是坏。一块好的芯片总能准确报告另一块芯片的好坏，但教授不能信任坏芯片报告的结果。因此，4种可能的测试结果如下：
a. 证明：如果超过n/2块芯片是坏的，使用任何基于这种逐对检测操作的策略，教授都不能确定哪些芯片是好的。假定坏芯片可以合谋欺骗教授。
若有m&n/2块好芯片，则剩余坏芯片中的m个可以选择表现出和好芯片完全一样的性质，即在另一块芯片同属于这个由m个坏芯片组成的集合时报告对方为好，否则报告坏。
这个m块坏芯片组成的集合和m块好芯片组成的集合的行为将无法区分。
b. 考虑从n块芯片中寻找一块好芯片的问题，假定超过n/2块芯片是好的。证明：进行lowerbound(n/2)次逐对检测足以将问题规模减半。
逐对检测所有芯片lowerbound(n/2)次，若检测双方都报告另一块芯片为好，则保留这对芯片中的一块；对其余三种情况，将两块芯片都丢弃，丢弃的两块芯片中至少有一块是坏的，即丢掉的坏芯片数量必然大于等于丢掉的好芯片的数量。可以推知，保留的芯片中好芯片的数量将大于坏芯片的数量，且保留的芯片数量小于等于n/2，即已成功将问题规模减半。
c. 假定超过n/2块芯片是好的，证明：可以用THETA(n)次逐对检测找出好的芯片。给出描述检测次数的递归式，并求解它。
由上一问的证明知，找到一块好芯片的时间为
T(n) = T(n/2) + n/2
T(n)复杂度?为THETA(n)（主方法）。找到一片好的芯片后，可用THETA(n)时间将之与其余所有芯片比较。
4-6 （Monge阵列） 对一个m*n的实数阵列A，若对所有满足1&=i&k&=m和1&=j&l&=n的i, j, k和l有
则称A是Monge阵列(Monge array)。换句话说，无论何时选出Monge阵列的两行和两列，对于交叉点上的4个元素，左上和右下两个元素之和总是小于等于左下和右上元素之和。例如，下面就是一个Monge阵列：
a. 证明：一个数组是Monge阵列当且仅当对所有i=1, 2, ..., m-1和j=1, 2, ..., n-1，有
（提示：对于“当”的部分，分别对行和列使用归纳法。）
b. 下面数组不是Monge阵列。改变一个元素使其变成Monge阵列。（提示：利用(a)的结果。）
c. 令f(i)表示第i行的最左最小元素的列下标。证明：对任意m*n的Monge阵列，f(1)&=f(2)&=...&=f(m)。
d. 下面是一个计算m*n的Monge阵列A的每一行最左最小元素的分治算法的描述：
提取A的偶数行构造其子矩阵A'。递归地确定A'每行的最左最小元素。然后计算A的奇数行的最左最小元素。
解释如何在O(m+n)时间内计算A的奇数行的最左最小元素（在偶数行的最左最小元素已知的情况下）。
e. 给出(d)中描述的算法的运行时间的递归式。证明其解为O(m+nlogm)。
分治作为一种算法设计技术至少可以追溯到1962年Karatsuba和Ofman的一篇文章。但是在这之前，分治技术已经有很好的应用，根据Heideman、Johnson和Burrus的论文，卡尔·弗雷德里希·高斯在1805年设计了第一个快速傅立叶变换算法，而高斯的算法就是将问题分解为更小的子问题，求解完子问题后将它们的解组合起来。
4.1节中讨论的最大子数组问题是Bently研究的问题的一个简单变形。
Strassen算法发表于1969年，它的出现引起了很大的轰动。在此之前，很少人敢设想一个算法能渐近快于平凡算法SQUARE-MATRIX-MULTIPLY。矩阵算法的渐近上界自此被改进了。到目前为止，n*n矩阵相乘的渐近复杂性最优的算法是Coppersmith和Winograd提出的，运行时间为O(n2.376)。已知的最好的下界显然是OMEGA(n2)（这是显然的下界，因为我们必须填写结果矩阵的n^2个元素）。
从实用的角度看，Strassen算法通常并不是解决矩阵乘法的最好选择，原因有4个：
隐藏在Strassen算法运行时间THETA(nlg7)中的常数因子比过程SQUARE-MATRIX-MULTIPLY的THETA(n3)时间的常数因子大。
对于稀疏矩阵，专用算法更快。
Strassen算法的数值稳定性不如SQUARE-MATRIX-MULTIPLY那么好。换句话说，由于计算机计算非整数值时有限的精度，Strassen算法累积的误差比SQUARE-MATRIX-MULTIPLY大。
递归过程中生成的子矩阵消耗存储空间。
后两个原因在1990年左右得到了缓解。Higham显示了数值稳定性上的差异被过分强调了；虽然Strassen算法对某些应用来说数值稳定性太差，但对其他应用来说，它所产生的数值误差还在可接受的范围内。Bailey、Lee和Simon讨论了降低Strassen算法内存需求的技术。
在实际应用中，稠密矩阵的快速乘法程序在矩阵规模超过一个“交叉点”时使用Strassen算法，一旦子问题规模降低到交叉点之下，就切换到一个更简单的算法。交叉点的确切值高度依赖于具体系统。有一些分析统计操作次数，但忽略CPU缓存和流水线的影响，得出的交叉点低至n=8(Higham)或n=12(Huss-Lederman等人）。D'Alberto和Nicolau设计了一个自适应方法，在软件包安装完毕后通过基准测试确定交叉点。它们发现，在不同的系统上，交叉点的值从n=400到n=2150变化，而在几个系统中无法找到交叉点。
递归式的研究最早可追溯到1202年李奥纳多·斐波那契的工作，斐波那契数就是以他命名的。A.De Moivre提出了用生成函数（参见思考题4-4）求解递归式的方法。主方法改自Bentley、Haken和Saxe的方法，这篇文章提供了一种扩展方法，在练习4.6-2中已经得到验证。Knuth和Liu展示了如何使用生成函数的方法求解线性递归式。Purdom和Brown的论文及Graham、Knuth和Patashnik的论文包含了递归式求解的进一步讨论。
相对于主方法可求解的分治算法递归式，多名研究者，包括Akra和Bazzi、Roura、Verma及Yap，都给出过更一般的递归式的求解方法。我们介绍一下Akra和Bazzi的结果，这里给出的是Leighton修改后的版本。Akra-Bazzi方法求解如下形式的递归式：
x&=1是一个实数，
x0是一个常数，满足对i=1, 2, ... , k, x0&=1/bi且x0&=1/(1-bi)，
对i=1, 2, ..., k, ai是一个正常数，
对i=1, 2, ..., k, bi是一个常数，范围在0&bi&1，
k&=1是一个整数常数，且
f(x)是一个非负函数，满足多项式增长条件：存在正常数c1和c2，使得对所有x&=1, i=1, 2, ... , k以及所有满足bix&=u&=x的u，有c1f(x)&=f(u)&=c2f(x)。（若|f'(x)|的上界是x的某个多项式，则f(x)满足多项式增长条件。例如，对任意实常数alpha和beta, f(n) = xalpha*(lgx)beta满足此条件。）
虽然主定理不能应用于T(n) = T(lowerbound(n/3)) + T(lowerbound(2n/3)) + O(n)这样的递归式，但Akra-Bazzi方法可以。为了求解递归式（4.30），我们首先寻找满足sum(i=1,k)aibi^p = 1 的实数p（这样的p总是存在的）。那么递归式的解为
Akra-Bazzi方法可能有点儿难用，但它可以求解那些子问题划分不均衡的算法的递归式。主方法很容易使用，但只能用于子问题规模相等的情况。
在2.3.1节中，我们介绍了归并排序，它利用了分治策略。回忆一下，在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：分解（Divide）步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。解决（Conquer）步骤递归地求解出子问题。如果子...
如果你以前曾经接触过矩阵，可能了解如何进行矩阵乘法（否则，请阅读D.1节）。若A= (aij) 和B=(bij)是n*n的方阵，则对i, j=1, 2, ... , n, 定义乘积C=A*B中的元素cij为： 我们需要计算n^2个矩阵元素，每个元素是n个值的和。下面过程接收...
主方法为如下形式的递归式提供了一种“菜谱”式的求解方法 若对某个常数epsilon&0有f(n)=O(n^logb(a-epsilon))，则T(n) = THETA(n^logba)。 若f(n) = THETA(n^logba)，则T(n) = THETA(n^logb...
算法和数据结构 [TOC] 算法 函数的增长 渐近记号 用来描述算法渐近运行时间的记号，根据定义域为自然数集$N={0, 1, 2, \cdots}$的函数来定义。这样的记号对描述最坏情况运行时间函数$T(n)$是方便的，因为该函数通常只定义在整数输入规模上。 $\Thet...
我们已经看到如何用递归式刻画分治算法的运行时间，下面将学习如何求解递归式。我们从“代入”法开始。代入法求解递归式分为两步： 猜测解的形式。 用数学归纳法求出解中的常数，并证明解是正确的。 当将归纳假设应用于较小的值时，我们将猜测的解代入函数，因此得名“代入法”。这种方法很强...
为了看这风景、我要忍受我生平最讨厌的声音因为我是一个喜欢安静的人 我为了看这夜晚星星灯河、为了看雨后天边的云彩、为了看清晨山间的薄雾、为了城市之中窗前的这一片空旷、也为了我的左心房、我要忍受不定时的火车轰鸣、要忍受水果小贩的叫卖、广场舞的民乐、甚至马路上车流声 小区中间的房...
第四轮打卡：第58天 觉察日记 事实：我调了两天休，请了一天假在家里休养身体，因为昨天的情绪不好，晚上又睡得很迟，到了昨天下午我是等孩子的父亲给我打电话，是不是要烧三个人的饭，他一直没有电话。等到晩上6:00多钟孩子回来，我问她爸爸回不回来？她说应该不回来，...
作者：区块链研习比特币源码研读班 菜菜子 一、源码下载 本文比特币源码下载地址为：/bitcoin/bitcoin，下载的版本为github中的最新版本，即0.14版。其源码目录结构如下。 图中红色矩形框选中的src文件夹为比特币源码所在...
关于军训结束后班里女生哭得稀里哗啦这件事，我一直难以理解。这样的事竟然在高中和大学重复发生，有的女生在军训结束后还跟教官保持联系，甚至因为对方回复了信息而激动不已。 天呐，一个禁锢你的自由，限制你的着装打扮（我曾经因为不愿意剪指甲而挨骂），让你机械地踢正步，甚至处罚你取乐的...相关文章推荐
根据渐近确界的定义知：T(n)max=cnlog(1/a,n)
T(n)min=cnlog(1/(1-a),n)>=d2...
http://acm./vjudge/contest/123676#problem/B
http://acm./vjudge/contest/123676#problem/P
using n...
http://acm./vjudge/contest/123676#problem/N
编写函数:solve,给定浮点数a,b,c,d,e,f,求解方程组ax+by=c,dx+ey=f
任务1：使用assert宏，让解不唯一时退出
任务2：解不唯一时仍然正常返回，但调用者有办...
第三章有两道题卡在那里了···“循环小数”和“浮点数”
今天做循环小数卡了···自己的模拟能力真的特别烂特别特别烂···
最终还是上网看了别人的代码 有的真简洁！真的是开了眼界了 由衷的佩服
http://acm./vjudge/contest/123676#problem/D
int main...
int x,i,j,temp=0,flag=0,y,A[100][100]={};
void DR(char cmd[3])
if(strc...
tuple maxCrossSubarray(vector &vec,int low,int...
他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
第4章_递归式_算法分析与设计_杭电_褚一平.ppt 41页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：250 &&
第4章_递归式_算法分析与设计_杭电_褚一平
你可能关注的文档：
··········
··········
* * 第4章 递归式 ?2T (n / 2) ? ?(n) 递归式 ?
?(1) T(n) ? ? 如果n ? 1 如果n ? 1 其解为：T(n)= Θ(nlgn) 注意问题： 1. 假设自变量为整数 2. 忽略边界条件 3. 忽略上取整、下取整的影响；先忽略，等得到结果后
再确定他们是否重要。 本章简介 介绍三种递归式的解法 代换法（substitution method） 先猜测有某个界存在，然后利用数学归纳法 证明该猜测的正确性！ 递归树方法（recursion-tree-method） 将递归式转换成树形结构，树中的节点代表 在不同递归层次付出的代价，最后利用对和 式限界的技术来解出递归式。 主方法(master metjod) 给出递归形式T(n)=aT(n/b)+f(n)的界，其中 a≥1，b&1，f(n)是给定的函数。 4.1代换法 用代换法解递归式需要两个步骤： 猜测解的形式 用数学归纳法找出使解真正有效的常数 代换法很有效，只能用于解的形式很容易猜的 情形
步骤 确定其界，以Θ记号为例，定义为： Θ(g(n)) = {f(n):存在正常数c1,c2,和n0使对所有的n ≥ n0，有 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) } 对边界条件成立： n0是正常数，n = n0，0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) 常常是n=1的时候不成立这个需要注意。！ 4.1代换法 [例] T(n)=2T(?n/2?)+n 猜其解为T (n) = O(n lg n) 即存在常数c使得T (n) ≤ cn lg n 于是 T(n)≤ 2(c ?n/2?lg(?n/2?)) + n ≤ cn lg(n/2) + n =cn lg n - cn lg 2 + n
=cn lg n - cn + n ≤ cn lg n 最后一步只需c ≥ 1就可以成立 (续上页) 边界条件： 由定义，只需要找出常数n0 ，使得当 n & n0 时， T(n)≤ cn lg n即可
取n0 =2，可证边界条件成立 如果假设T(1)=1，则取n0 =1时有问题，因 为此时的cn lg n=0，不为1。 4.1代换法 不存在通用的方法，需要经验 试探法
递归树 类似的先例 T(n)=2T(?n/2?+17)+n 猜T(n)=O(nlgn) 先证明递归式上下界，不断缩小不确定 性区间 对合并排序：下界T(n)=Ω(n),上界 T(n)=O(n2) [经验]减掉一个低阶项 [例] T (n) = T (?n/2?) + T (?n/2?) + 1 试猜解T (n) = O(n),代入T (n) ≤ cn 可发现 T (n)≤ c ?n/2? + c ?n/2? + 1 =cn + 1 与所猜解并不一致 减掉一个低阶项：T (n) ≤ cn – b T (n)≤ (c ?n/2? - b) + (c ?n/2? - b) + 1 =cn - 2b + 1 ≤ cn – b 只要b ≥ 1即可成立 4.1代换法 [经验]避免陷阱 [例] T(n)=2T(?n/2?)+n 猜解T (n) = O(n)，取T (n) ≤ cn T (n)≤ 2(c ?n/2?) + n ≤ cn + n =O(n) , 错误！c是常数！ [例]
? [经验]改变变量 取m = lg n，则n =2m , T (2m) = 2T (2m/2) + m 取S(m) = T(2m)，则S(m) = 2S(m/2) + m
于是S(m) = O(m lg m) T (n) = T (2m) = S(m) = O(m lg m) = O(lg n lg lg n) n 4.2递归树方法 递归树是一种得到好猜测的直接方法
通常可以容忍小量的不良性 [例]T (n) = 3T (?n/4?) + Θ(n2) 忽略顶和底函数，建立递归式T (n) = 3T(n/4) + cn2的递归树，常系数c & 0 假设n是4的幂 cn2
? ?(nlog 4.2递归树方法
正在加载中，请稍后...