上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。

衡水网站建设【衡水网络公司】衡水做网站、衡水微信公众号开发、衡水网站设计、衡水小程序制作

衡水，河北省地级市，位于河北省东南部，介于东经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.10.3　MergeSort函数

最后要介绍一下MergeSort函数，我们在图3-28中再次展示了该函数。对参数大小的合适量度n还是待排序表的长度。在这里，我们要使用T(n)表示MergeSort处理长度为n的表的运行时间。

我们选取n=1的情况作为依据情况，而n>1（发生递归调用）的情况则作为归纳情况。如果对MergeSort加以研究，就会发现，除非从另一个函数中调用参数为空表的MergeSort，不然是没办法在参数为空表的情况下进行调用的。原因在于，只有当表中至少具有两个元素时也就是分拆后得到的两个表中都至少有一个元素时，才会执行第(4)行。因此可以忽略n=0的情况，并直接从n=1开始进行归纳证明。

     LIST MergeSort(LIST list)

     {

         LIST SecondList;

(1)      if (list == NULL) return NULL;

(2)      else if (list->next == NULL) return list;

         else {

             /* 表中至少有两个元素 */

(3)          SecondList = split(list);

(4)          return merge(MergeSort(list), MergeSort(SecondList));

         }

     }

复制代码

图 3-28　归并排序算法

依据。如果list由一个元素构成，就会执行第(1)行和第(2)行，而不执行其他代码。因此，在依据情况中，T(1)是O(1)。

归纳。在归纳情况中，第(1)行和第(2)行的测试都是失败的，因此可以执行第(3)行和第(4)行的程序块。为了简化问题，可以假设n是2的乘方。作出这种假设的好处在于，当n为偶数时，刚好会将表分割成长度为n/2的两等分。此外，如果n是2的乘方，那么n/2也是2的乘方，每次递归结束二分出来的都是等分的表，直到每个表中只含一个元素为止。当n>1时，MergeSort所花的时间为下列各项之和。

1. 两次测试所花的O(1)。

2. 第(3)行的赋值和对split的调用所花的O(1)??O(n)。

3. 第(4)行对MergeSort第1次递归调用所花的T(n/2)。

4. 第(4)行对MergeSort第2次递归调用所花的T(n/2)。

5. 第(4)行调用merge所花的O(n)。

6. 第(4)行的返回语句所花的O(1)。

跳过某些值的归纳法

读者不应该为MergeSort函数的分析中涉及的新型归纳法感到担心，尽管在证明过程中我们跳过了除2的乘方之外的所有数值。一般情况下，如果i1、i2、…是一列与我们想证明的命题S有关的整数，就可以证明S(i1)作为依据，并对所有的j证明，S(i1)可推出S(ij+1)。这就是一般情况下我们所认为的对j 进行归纳的归纳证明。更精确地说，由S' (j )=S(ij )定义命题S'。然后通过对j 的归纳证明S' (j )。这样的话，就可以是i1=1、i2=2、i3=4，而一般形式就是ij=2j-1。

顺便提一句，请注意，MergeSort的运行时间T(n)不会随着n的增加而减少。因此，证明了对等于2的乘方的n有T(n)是O(n logn)，也就证明了对所有的n都有T(n)是O(n logn)。

如果将这些项加起来，然后依据调用split和merge的O(n)更大而舍弃O(1)，就可以得出在归纳情况中，MergeSort的运行时间边界是2T(n/2)+O(n)。因此得到以下递推关系。

依据。T(1)=O(1)。

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

下一步是要用含具体常数的函数代替大O表达式。我们在依据中用常数a代替O(1)，并在归纳步骤中用bn代替O(n)，因此递推关系就变形为

依据。T(1)=a。

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

这一递推关系要比我们之前了解的更难，不过我们还是可以利用相同的技巧。首先，可以为一些较小的n值直接写出O(n)的值。依据说明了T(1)=a，而归纳步骤则告诉我们

T(2)　　= 2T(1) + 2b　　　　　　　　　　　　　= 2a + 2b

T(4)　　= 2T(2) + 4b　　= 2(2a + 2b) + 4b　　= 4a + 8b

T(8)　　= 2T(4) + 8b　　= 2(4a + 8b) + 8b　　= 8a + 24b

T(16) 　= 2T(8) + 16b　 = 2(8a + 24b) + 16b　= 16a + 64b

想直接看出接下来的情况可不容易。显然，a 的系数与n 的值是同步的，也就是说T(n)是n 乘上a，再加上某个数量的b。不过b 的系数要比n 增长得更快。b 的系数与n 之间的关系可以归纳为如下：

n 的值 2 4 8 16

b 的系数 2 8 24 64

比率 1 2 3 4

比率是用系数b 除以n 的值得到的。因此，看起来b 的系数是n 乘上n 每次翻倍便会增长1的另一个因子。具体来讲，我们可以看出这个比率是log2n，因为log22=1，log24=2，log28=3，且log216=4。因此推测递推关系的解为T(n)=an+bn log2n是合理的，至少对表示2的乘方的n来说如此。我们将看到该公式是正确的。

要为该递推关系求解，先遵从前面的示例中使用过的策略。我们将归纳规则写成参数m的函数，形如

对m为2的乘方且m>1，　　　　　　　　T(m)=2T(m/2)+bm　　　　　　　　(3.5)

接着可以从T(n)开始，利用(3.5)，用具有较小参数的表达式来代替T(n)，在这种情况下，要替换的表达式是关于T(n/2)的。也就是，首先有

T(n)=2T(n/2)+bn　　　　　　(3.6)

接下来，利用(3.5)，将m替换为n/2，从而得到替换(3.6)中T(n/2)的表达式。也就是，(3.5)说明有T(n/2)=2T(n/4)+bn/2，而我们可以将(3.6)替换为

T(n)=2(2T(n/4)+bn/2)+bn=4T(n/4)+2bn

然后，可以用n/4代替(3.5)中的m，从而将T(n/4)替换为2T(n/8)+bn/4，从而得到

T(n)=4(2T(n/8)+bn/4)+2bn=8T(n/8)+3bn

我们要通过对i的归纳证明的命题就是

命题S(i )。如果1≤n≤log2n，那么T(n)=2iT(n/2i )+ibn。

依据。对i=1，命题S(1)就是说T(n)=2T(n/2)+bn。这个等式是对归并排序运行时间T(n)的定义中的归纳规则，因此可知依据是成立的。

归纳。就像那些归纳假设是“如果……那么……”形式的归纳证明一样，如果i 在假设范围之外，那么归纳步骤必定成立，这里，i≥log2n 时就是这种简单的情况，这时S(i+1)显然成立。

再来看看困难的情况，假设i<log2n。还要假定归纳假设S(i )成立，就是T(n)=2iT(n/2i )+ibn。用n/2i 替换(3.5)中的m，就得到

T(n/2i )=2T(n/2i+1)+bn/2i　　　　　　(3.7)

用(3.7)的右边替换S(i )中的T(n/2i )，就得到

egin{align*}T(n)&=2^iigl(2T(n/2^{i+1})+bn/2^iigr)+ibn&=2^{i+1}T(n/2^{i+1})+bn+ibn&=2^{i+1}T(n/2^{i+1})+(i+1)bnend{align*}

最终的等式就是命题S(i+1)，这样就证明了归纳步骤。

于是可以得出S(i )，也就是T(n)=2iT(n/2i )+ibn对在1和log2n之间的任意i 都是成立的。现在要考虑公式S(log2n)，也就是

T(n)=2log2nT(n/2log2n)+(log2n)bn

我们知道2log2n=n（请回想一下，log2n 的定义就是，使2变为n，要对2乘方的次数）。还有n/2log2n=1。因此S(log2n)可以写为

T(n)=nT(1)=bn log2n

由T 的定义中的依据，还知道T(1)=a。因此，

T(n)=an+bn log2n

在经过这段分析后，必须将常数a 和b 替换为大O表达式，即T(n)是O(n)+O(n logn)。8因为n 比n logn增长得更慢，所以可以忽略O(n)这项，直接说T(n)是O(n logn)。也就是说，归并排序算法的时间量级是O(n logn)。请记住，我们已经证明了选择排序的运行时间是O(n2)。虽然严格地讲，这里的O(n2)只是个上界，但是它其实是选择排序的最紧简单边界。因此，可以确定，随着n不断变大，归并排序要一直比选择排序运行得更快。从实践上讲，对值大于几十的n来说，归并排序要比选择排序更快。

8请记住，在大O表达式中，我们不必为对数指定底数，因为这里的对数是在常数因子中，所以所有底数的对数都是一样的。

衡水网站建设【衡水网络公司】衡水做网站、衡水微信公众号开发、衡水网站设计、衡水小程序制作

上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。

服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）