邢台申请400电话费用【邢台企业全国热线电话办理】邢台开通400电话电信价格、邢台微信公众号代运营外包托管、邢台网店编辑装修美工、邢台网站推广优化大概需要多少钱

邢台申请400电话费用【邢台企业全国热线电话办理】邢台开通400电话电信价格、邢台微信公众号代运营外包托管、邢台网店编辑装修美工、邢台网站推广优化大概需要多少钱

邢台，简称“邢”，古称邢州、顺德府，是河北省地级市，河北省政府批复确定的京津冀城市群节点城市、河北省级历史文化名城、冀中南先进制造业基地和物流枢纽 [1]  。截至2020年，全市下辖4个区、12个县、代管2个县级市。 [2]  总面积12400平方千米，市区建成区面积214.84平方千米，常住人口739.52万人，城镇人口401.04万人，城镇化率54.23%。 [3-5] 

邢台地处中国华北地区、河北南部，境内京广、京九铁路，京广、京九高铁，京港澳、大广、太行山高速纵贯南北；邢和、邢黄铁路，邢衡、邢汾、邢临、青银高速横贯东西，与邢台国际内陆港、邢台机场构成了“东出西联、南承北接”的交通枢纽。 [6] 

邢台拥有3500余年建城史，距今五万至十万年前就有人类栖息繁衍，历史上曾四次建国、五次定都，有“五朝古都、十朝雄郡”之称，是华夏版图上建城历史排名第三的城市 [7]  ，华北历史上第一座城市，中国最早的古都之一，历经三千多年行政建制未曾中断、城址未曾迁移。邢台古城是黄河以北地区建城最早的“第一古城”，被誉为“燕赵第一城”。 [8] 

邢台悠久的历史涌现出郭守敬、李牧、宋璟、刘秉忠等先贤，走出了郭威、柴荣、孟知祥、孟昶等帝王，千古一帝秦始皇东巡途中驾崩于邢台沙丘 [9-10]  。 邢台也是唐朝皇室祖籍地（唐祖陵） [11-14]  ，发生过尧舜禅让、胡服骑射、巨鹿之战、黄巾起义等影响中国历史进程的事件，有破釜沉舟、鹿死谁手、民脂民膏、腹背受敌等近百条成语、典故源自邢台。

3.10　归并排序的分析

我们现在要分析2.8节中介绍过的归并排序算法。首先要证明，merge函数和split函数在处理长度为n的表时，所花的时间都是O(n)；接着使用这些边界来证明MergeSort函数在处理长度为n的表时所花的时间为O(n logn)。

3.10.1　merge函数的分析

首先分析递归函数merge，我们在图3-25中再次展示了它的代码。merge函数参数大小n 的合适概念是表list1和list2的长度之和。因此，设T(n)是当参数表的长度之和为n 时merge函数所花的时间。我们可以拿n=1的情况作为依据情况，因此必须在list1和list2二者中有一个为空而另一个仅含一个元素的假设下对图3-25进行分析。有以下两种情况。

1. 如果第(1)行的测试（也就是list1等于NULL的测试）成功，我们就返回list2，这所花的时间为O(1)。第(2)行至第(7)行就不会执行。因此，整个函数调用所花的时间为测试第(1)行选择的O(1)和执行第(1)行赋值的O(1)，总共是O(1)。

2. 如果第(1)行的测试失败，就说明list1不为空。因为我们假设两个表的长度之和只是1，所以list2一定为空。因此，第(2)行的测试（即list2等于NULL的测试）一定会成功。那么我们就要花O(1)来执行第(1)行的测试，花O(1)执行第(2)行的测试，再花O(1)在第(2)行返回list1。第(3)行至第(7)行不会执行。所花的时间还是O(1)。

这样可以得出在依据情况中merge的运行时间为O(1)。

     LIST merge(LIST list1, LIST list2)
     {(1)      if (list1 == NULL) return list2;(2)      else if (list2 == NULL) return list1;(3)      else if (list1->element <= list2->element) {(4)          list1->next = merge(list1->next, list2);(5)          return list1;
         }
         else { /* list2 的第一个元素更小 */(6)          list2->next = merge(list1, list2->next);(7)          return list2;
         }
     }复制代码

图 3-25　merge函数

现在来考虑归纳情况，也就是表长度之和大于1的情况。当然，即便长度之和为2或者更大，仍然可能有一个表为空。因此，嵌套的选择语句所表示的4种情况都可能发生。图3-25中程序的结构树如图3-26所示。我们可以从结构树的底部开始，向上分析该程序。

图 3-26　merge的结构

最内层的选择是从第(3)行的“if”开始的，我们在那里会测试哪个表的第一个元素更小，并根据测试的结果选择执行第(4)行和第(5)行，或执行第(6)行和第(7)行。第(3)行的条件需要花O(1)的时间来评估，第(5)行要花上O(1)来评估，而第(4)行所花的时间是O(1)加上递归调用merge所花的时间T(n-1)。请注意，n-1是递归调用的参数大小，因为我们已经从一个表中剔除了一个元素，并保持另一个表不变。因此第(4)行和第(5)行的程序块所花的时间为O(1)+T(n-1)。

对第(6)和第(7)行中else部分的分析是完全一样的：第(7)行所花时间为O(1)，而第(6)行所花时间为O(1)+T(n-1)。因此，在选取if部分和else部分运行时间的最大值时，会发现这两者其实是相同的。测试条件所花的时间O(1)可以忽略，因此可以得出结论：最内层选择的运行时间是O(1)+T(n-1)。

现在继续分析从第(2)行开始的选择。我们要在这一行测试list2是否等于NULL。测试条件的时间为O(1)，而if部分的时间（就是第(2)行的返回）也是O(1)。不过，else部分是第(3)行至第(7)行的选择语句，这部分语句的运行时间我们刚才确定过了，是O(1)+T(n-1)。因此，第(2)行至第(7)行的选择所花的时间为

O(1)+max(O(1),O(1)+T(n-1))

最大值中的第二项主导了第一项，也主导了测试条件所花的时间O(1)。因此，从第(2)行开始的if语句的运行时间也是O(1)+T(n-1)。

最后，要对最外层的if语句进行同样的分析。从根本上讲，对时间起主导作用的还是由第(2)行至第(7)行组成的else部分的时间。

递归的共通形式

很多极简单的递归函数（比如fact和merge）都会执行一些所需时间为O(1)的操作，然后对它们自己执行参数大小减小1的递归调用。假设依据情况花的时间为O(1)，可以看到这样的函数总能形成T(n)=O(1)+T(n-1)这样的递推关系。T(n)的解是O(n)，或者是参数大小的线性关系。在3.11节中我们还将看到对这一原则的一些概括。

也就是说，这些含递归调用的情况（比如第(4)行和第(5)行，或第(6)行和第(7)行）下的时间，主导了不含递归调用情况下的时间，还主导了第(1)、(2)和(3)行中所有3次测试的时间。因此，当n>1时，merge函数的运行时间上界就是O(1)+T(n-1)。因此可以得到用于定义T(n)的如下递推关系。

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

归纳。对n>1，T(n)=O(1)+T(n-1)。这些等式与示例3.24中为fact函数得出的那些等式如出一辙。因此，求解过程是相同的，可以得出T(n)是O(n)的结论。该结果从直观上讲是成立的，因为merge函数的工作原理就是花O(1)的时间从其中一个表里删除一个元素，然后对剩余的表递归地调用自身。这种递归调用遵循着递归调用的次数不大于表长度之和的原则。如果不考虑其递归调用所花时间，那么每次调用均耗时O(1)，如此就可以得出merge的运行时间将会是O(n)。

3.10.2　split函数的分析

现在来考虑一下split函数，我们在图3-27中再次展示了该函数。对split函数的分析和对merge函数的分析非常相似。我们令表的长度为参数的大小n，而且这里使用T(n)表示split函数处理长度为n的表所花的时间。

     LIST split(LIST list)
     {
         LIST pSecondCell;(1)      if (list == NULL) return NULL;(2)      else if (list->next == NULL) return NULL;
         else { /* 至少有两个单元 */(3)          pSecondCell = list->next;(4)          list->next = pSecondCell->next;(5)          pSecondCell->next = split(pSecondCell->next);(6)          return pSecondCell;
         }
     }复制代码

图 3-27　split函数

我们选取n=0和n=1作为依据。如果n=0，也就是说表为空，那么第(1)行的测试就会成功，而我们将在第(1)行返回NULL。第(2)行至第(6)行就不会执行。因此所花的时间为O(1)。如果n=1，也就是表只含一个元素，那么第(1)行的测试失败，不过第(2)行的测试成功。因此我们会在第(2)行返回NULL，而且不执行第(3)行至第(6)行。同样，这两条测试语句和一条返回语句只需要O(1)的时间。

接着考虑n>1时的归纳部分，这里存在3条选择分支，类似我们在分析merge函数时遇到的4条分支。简单来说，可以看出，第(1)行和第(2)行的测试不论是执行一个还是两者都执行，所花时间都是O(1)，正如我们最终为merge函数得出的结论那样。而且，如果这两个测试中有一个为真，就会致使我们在第(1)行或第(2)行返回的情况中，多花的时间也是O(1)。占主导的时间是两个测试均失败的情况，也就是表长度至少为2的情况。在这种情况下，第(3)行至第(6)行的语句都要执行。除了第(5)行的递归调用外，其他的内容所花的时间为O(1)。而递归调用的时间是T(n-2)，因为该参数表是list原来的值减去它的前两个元素（想知道原因，可以参考2.8节中的内容，特别是图2-28）。因此，归纳情况下的T(n)是O(1)+T(n-2)。

可以建立如下递推关系。

依据。T(0)=O(1)，且T(1)=O(1)。

归纳。对n>1，T(n)=O(1)+T(n-2)。

如示例3.24所述，接下来必须引入某些常数来表示隐藏在O(1)背后的比例常数。可以分别用常数a 和b 表示依据中T(0)和T(1)的O(1)，并用常数c 表示归纳步骤中的O(1)。因此，可以将上述递归定义重写为

依据。T(0)=a，且T(1)=b。

归纳。对n≥2，T(n)=c+T(n-2)。

我们先来求一下T(n)的前几个值。由依据，显然有T(0)=a和T(1)=b。可以使用归纳步骤得出

对T(n)的计算其实是两部分单独的计算，一部分是n为奇数的情况，一部分是n为偶数的情况。对偶数n，我们有T(n)=a+cn/2。这是可行的，因为对长度为偶数的表，剔除两个元素所花的时间为c，而且在经过n/2次递归调用后，就会得到不再对其进行递归调用而且所花时间为a 的空表。

对奇数长度的表来说，还是要花时间c 来剔除两个元素的。在经过(n-1)/2次调用后，我们得到了一个长度为1的表，而且需要的时间为b。因此，奇数长度的表所需的时间将是b+c(n-1)/2。

对这些观察结果的归纳证明与示例3.24中的证明过程非常近似，就是要证明如下命题。

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

在该命题的证明过程中，我们使用T(n)定义中的归纳规则，用参数m将其重写为

对　　　　　　　　　　　m≥2， T(m)=c+T(m-2)　　　　　　　　　　　(3.4)

接着就可以按照如下方式用归纳法证明S(i )了。

依据。依据是i=1，也就是用n 替代m 后的等式(3.4)。

归纳。因为S(i )是“如果……那么……”的形式，所以若i≥n/2，则S(i+1)恒为真。因此，若i≥n/2，我们就不需要对归纳步骤（即由S(i )可得到S(i+1)）加以证明。

难点是当1≤i≤n/2时。在这种情况下，假定归纳假设S(i)为真，即T(n)=ic+T(n-2i)。用n-2i替换(3.4)中的m，就得到

T(n-2i)=c+T(n-2i-2)

如果替换S(i )中的T(n-2i )，就得到

T(n)=ic+(c+T(n-2i-2))

如果对等式右边的项加以组合，就有

T(n)=(i+1)c+T(n-2(i+1))

这就是命题S(i+1)。因此我们证明了归纳步骤，而且得出T(n)=ic+T(n-2i)。

现在，若n为偶数，则令i=n/2。则S(n/2)就表示T(n)=cn/2+T(0)，也就是a+cn/2。如果n为奇数，就令i=(n-1)/2。S((n-1)/2)就表示T(n)=c(n-1)/2+T(1)，也就等于b+c(n-1)/2，因为有T(1)=b。

最后，必须将特定于编译器和机器的常数a、b和c改写为大O表示。多项式a+cn/2和b+c(n-1)/2都具有与n成比例的高阶项。因此，该问题中不论n是奇数还是偶数其实是没关系的，两种情况下split的运行时间都是O(n)。这又是个很直观的正确解答，因为对长度为n的表来说，split会进行约n/2次递归调用，每次调用的时间都是O(1)。

邢台申请400电话费用【邢台企业全国热线电话办理】邢台开通400电话电信价格、邢台微信公众号代运营外包托管、邢台网店编辑装修美工、邢台网站推广优化大概需要多少钱