衡水微信公众号开发【衡水网络推广】衡水建站、衡水网站维护、衡水网页制作、衡水微信小程序代运营公司

衡水微信公众号开发【衡水网络推广】衡水建站、衡水网站维护、衡水网页制作、衡水微信小程序代运营公司

衡水，河北省地级市，位于河北省东南部，介于东经115°10′-116°34′，北纬37°03′-38°23′之间，东部与沧州市和山东省德州市毗邻，西部与石家庄市接壤，南部与邢台市相连，北部同保定市和沧州市交界，总面积8815平方公里。 [1-2]  衡水市地处河北冲积平原，地势自西南向东北缓慢倾斜，海拔高度12米～30米。属大陆季风气候区，为温暖半干旱型，是京津重要的农副产品加工供应基地。衡水属于环渤海经济圈和首都经济圈的“1+9+3”计划京南区，为环渤海区域合作市长联席会议成员市，被费孝通称为“黄金十字交叉处”。 [2-5] 

衡水所辖冀州为九州之首。河北省称冀，也缘于此，涌现出了董仲舒、孔颖达、高适、孙犁等知名人物。截至2016年，衡水有国家级非物质文化遗产保护项目6项，省级非遗保护项目33项，市级非遗保护项目55项，境内有衡水湖、武强年画博物馆、冀州城等旅游景点。 [2]  [6-8] 

截至2019年末，衡水市辖2个市辖区，1个县级市，8个县，户籍人口457.8万人，常住人口448.6万人；实现生产总值1504.9亿元，人均生产总值33599元。 2019年10月23日，被确定为“第三批城市黑臭水体治理示范城市”。

3.11.2　通过猜测解为递推关系求解

求解递推关系的另一种实用方法就是猜测一个解f (n)，接着使用递推关系证明T(n)≤f (n)。这可能不会给出T(n)的精确值，不过如果它给出了紧上界，也是能令人满意的。通常我们只会猜测f (n)这样的函数形式，不去指定一些参数。例如，我们可以猜测对某a和b，f (n)=anb。这些参数的值都是确定的，因为我们要为所有n证明T(n)≤f (n)。

虽然可能觉得能准确猜测解是件离奇的事，但我们经常能通过观察一些较小n 值所对应的T(n)来推断出高阶项。然后就可以舍弃某些低阶项，并看看它们的系数是否非0。9

9要知道，与递推关系理论很类似的微分方程理论也依赖于一些常见形式的方程的已知解，并据此通过合理的猜测求解其他方程。

示例 3.27

我们再来研究一下3.10节中介绍过的MergeSort递推关系，将其写为

依据。T(1)=a。

归纳。T(n)=2T(n/2)+g(n)，其中n是2的乘方而且大于1。

我们要猜测T(n)的上界是f(n)=cn log2n+d，其中c 和d 是某些常数。回想一下，这种形式并不完全正确，在之前的示例中，我们得出的解都具有O(n logn)项以及O(n)项，而不带常数项。不过，这个猜测对证明O(n logn)是T(n)的上界来说已经足够好了。

接着要对n进行完全归纳，证明以下命题，其中c 和d 是某些常数。

命题S(n)。如果n是2的乘方而且n≥1，那么T(n)≤f (n)，其中f (n)是函数cn log2n+d。

依据。当n=1时，T(1)≤f (1)表示a≤d，因为当n=1时，f (n)中cn log2n这项的值为0，则f (1)=d，而且之前已经给定了T(1)=a。

归纳。对所有的i< n，假设S(i )为真，并证明对某些n>1，S(n)为真。如果n不是2的乘方，就没什么好证明的，因为这时具有“如果……那么……”形式的命题S(n)的如果部分不为真。因此，考虑困难的情况，也就是n是2的乘方的情况。可以假设S(n/2)为真，也就是假设

T(n/2)≤(cn/2)log2(n/2)+d

因为它是归纳假设的一部分。对归纳步骤来说，需要证明

T(n)≤f(n)=cn log2n+d

当n≥2时，T(n)定义的归纳部分告诉我们

T(n)≤2T(n/2)+bn

将归纳假设应用到T(n/2)的边界，就有

T(n)≤2[c(n/2)log2(n/2)+d]+bn

因为log2(n/2)=log2n-log22=log2n-1，所以可以将这一表达式简化为

T(n)≤cn log2n+(b-c)n+2d　　　　　　(3.10)

现在要证明T(n)≤cn log2n+d，条件是(3.10)右边的式子中，cn log2n+d之外的部分最多为0，也就是说(b-c)n+d≤0。因为n>1，所以当d≥0且b-c≤-d时该不等式成立。

要让f(n)=cn log2n+d成为T(n)的上界，需要满足以下3条约束。

1. 约束a≤d 来自依据部分。

2. d>0来自归纳部分，不过因为已知a>0，所以由(1)便可得到该不等式。

3. b-c≤-d，或者说c≥b+d，也是来自归纳部分。

如果令d=a而且c=a+b，那么这些约束显然可得到满足。我们现在就通过对n 的归纳证明了，对所有大于等于1且为2的乘方的n，有

T(n)≤(a+b)n log2n+a

该参数表明了T(n)是O(n logn)，也就是说T(n)的增长速度不会比n logn 快。不过，我们得到的边界(a+b)n log2n+a要比示例3.26中得到的确切解答bn log2n+an 稍大一些，但至少是成功得到了边界。假使我们选择了更简单的猜测f (n)=cn log2n，可能就失败了，因为不存在可以使f (1)≥a的c值。原因在于，c×1×log21=0，这样就有f (1)=0。如果a>0，就显然不能使f (1)≥a。

不等式的处理

示例3.27中的不等式T(n)≤cn log2n+d，是从另一个不等式T(n)≤cn log2n+(b-c)n+2d 得出的。方法是找出“多余的量”，并要求它至多为0。一般的原则是，假设有不等式A≤B+E，那么如果要证明A≤B，只需要证明E≤0就够了。在示例.27中，A是T(n)，B是cn log2n+d，而那个“多余的量”是(b-c)n+d。

示例 3.28

现在考虑的是在本书后续内容中将要遇到的一个递推关系。

依据。G(1)=3。

归纳。对n>1，G(n)=(2n/2+1)G(n/2)。

该递推关系包含的是实际的数字，而不是像a这样的符号常数。在第13章中，我们将使用这样的递推关系计算电路中门的数量，而且门的数量是可以准确计出的，不需要用大O表示法去隐藏不可知的常数因子。

如果我们考虑一下通过反复代换得到的解，就可能发现，要将G(n)用含G(1)的项表示出来，需要进行log2(n-1)次代换。随着代换的不断进行，就会得到因子

(2n/2+1)(2n/4+1)(2n/8+1)…(21+1)

如果舍去每个因子中的“+1”项，就会近似地得出积2n/22n/42n/8…21，也就是

2n/2++n/4+n/8+…+1

或者如果为指数部分的几何级数求和，就是2n-1，也就是2n的一半，因此可以猜测，2n是解G(n)中的项。不过，如果猜测f(n)=c 2n是G(n)的上界，就可能会求解失败，读者可以自行验证。也就是说，我们得到了两个涉及c的不等式，但它们不是解。

因此我们会猜测下一种最简单的形式，f(n)=c 2n+d，而这样就能成功求解了。也就是说，可以通过对n的完全归纳证明以下命题，其中c 和d 是某些常数。

命题 S(n)。如果n是2的乘方且n≥1，那么G(n)≤c 2n+d。

依据。如果n=1，那么必须证明G(1)≤c 21+d，也就是3≤2c+d。该不等式变成了对c 和d 的约束。

归纳。像示例3.27那样，唯一的难点出现在当n为2的乘方而且要从S(n/2)证明S(n)时。这种情况下等式就成了

G(n/2)≤c 2n/2+d

必须证明S(n)，也就是G(n)≤ c 2n+d。首先从G的归纳定义开始。

G(n)=(2n/2+1)G(n/2)

然后用得到的上界替换G(n/2)，就将上述表达式转换成了

G(n)≤(2n/2+1)(c 2n/2+d)

加以简化，就得到

G(n)≤c 2n+(c+d)2n/2+d

这要给出所需的G(n)的上界c 2n+d，因此就要有右侧多余的部分(c+d)2n/2不大于0，而这只需有c+d≤0就足够了。

我们需要选择c 和d 来满足两个不等式。

1. 源于依据部分的2c+d≥3。

2. 源于归纳部分的c+d≤0。

例如，如果c=3且d=-3，则两个不等式都能满足。那么我们就知道G(n)≤3(2n-1)。因此，G(n)是随着n指数增长的。刚好这个函数就是确切的解，也就是说G(n)=3(2n-1)，读者可以自己通过对n的归纳来证明这一点。

对解的总结

下面的表格中列出了一些最常见的递推关系，其中包括本节未曾介绍的。在每种情况中，假设依据等式为T(1)=a，而且有k>0。

归纳等式	T(n)
T(n)=T(n-1)+bnk	O(nk+1)
T(n)=cT(n-1)+bnk其中c>1	O(cn)
T(n)=cT(n/d)+bnk其中c>dk	O(nlogdc)
T(n)=cT(n/d)+bnk其中c< dk	O(nk)
T(n)=cT(n/d)+bnk其中c=dk	O(nk logn)

若上述等式中的bnk 被替换为任意的k 次多项式，其结论也都是成立的。

衡水微信公众号开发【衡水网络推广】衡水建站、衡水网站维护、衡水网页制作、衡水微信小程序代运营公司