邢台网站制作要多少钱【域名企业邮箱服务器注册申请办理】邢台网络优化公司哪家好、邢台软件开发外包价格、邢台高端企业网站页面制作设计专业公司、邢台微信公众号小程序购物支付搭建制作公司

邢台网站制作要多少钱【域名企业邮箱服务器注册申请办理】邢台网络优化公司哪家好、邢台软件开发外包价格、邢台高端企业网站页面制作设计专业公司、邢台微信公众号小程序购物支付搭建制作公司

邢台，简称“邢”，古称邢州、顺德府，是河北省地级市，河北省政府批复确定的京津冀城市群节点城市、河北省级历史文化名城、冀中南先进制造业基地和物流枢纽 [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.8　含函数调用的程序的分析

现在要展示的是如何分析包含函数调用的程序或程序段的运行时间。首先，如果所有的函数都是非递归的，可以从那些不调用其他函数的函数开始，每次确定一个组成该程序的函数的运行时间，然后为那些“只调用已确定运行时间的函数”的函数评估运行时间。我们以这种方式继续评估，直到评估完所有函数的运行时间。

不同函数可能有不同的输入大小的自然量度，这一事实带来了一些复杂性。在一般情况下，函数的输入就是该函数的参数列表。如果函数F调用了函数G，就必须将函数G 中参数的大小量度与函数F所使用的大小量度联系起来。这里很难给出实用的通则，不过本节和下一节中的一些示例将有助于我们了解简单情况下为函数确定运行时间边界的过程是怎样的。

假设已经确定，函数F 运行时间的良好上界是O(h(n))，其中n是函数F 参数大小的度量。那么在某条简单语句（比如一条赋值语句）中对F进行调用时，就要将O(h(n))的开销加到那条语句的运行时间中。

当上界为O(h(n))的函数出现在while语句、do-while语句或if语句的条件中，或出现在for语句的初始化、测试或重初始化中时，该函数调用的时间是按如下方法计算的。

1. 如果函数调用是在while循环或do-while循环的条件中，或在for循环的条件或重初始化中，那么就要在每次迭代的时间边界上加上h(n)，然后按照3.7节中获取循环运行时间的方式继续下去。

2. 如果函数调用是在for循环的初始化中，就在循环的时间开销上加上O(h(n))。

3. 如果函数调用是在if语句的条件中，就在该语句的时间开销上加上h(n)。

简述程序分析

大家应该从3.7节和3.8节中了解到的主要观点如下。

• 一系列语句的运行时间就是每一条语句运行时间的和。通常，如果某一语句的运行时间至少与其他语句一样大，那么它就可以主导其他语句。根据求和规则，主导语句的运行时间就是这一系列语句的大O运行时间。

• 要计算循环的运行时间，先要将循环体的时间与各控制步骤（比如重初始化for循环的循环指标并将其与上限相比较）的运行时间相加。用这个时间去乘以循环迭代次数的上界。接着，将那些一次性完成的步骤（比如初始化或第一次终止测试）的时间加上，以防循环迭代0次的情况出现。

• 选择语句（例如if-else语句）的运行时间是决定执行哪个分支所花的时间与各分支运行时间中较大的那个相加而得到的之和。

示例 3.23

让我们分析一下图3-21中的（无意义的）程序。首先，你会注意到这不是一个递归程序。main函数会调用foo函数和bar函数，而且foo函数会调用bar函数，不过这就是全部的调用关系了。图3-22所示的图称为调用图，表示函数调用其他函数的方式。因为图中不含循环，所以程序中没有递归调用，而且可以首先从“第0组”（就是不调用其他函数的函数，在本例中就是bar函数）开始分析这些函数，接着处理“第1组”（就是只调用第0组中函数的函数，在本例中就是foo函数），再处理“第2组”（就是只调用第0组和第1组中函数的函数，在本例中就是main函数）。至此，工作就完成了，因为所有的函数都已经被分组了。在一般情况下，可能要考虑分更多的组，不过只要其中不含循环，最终就能将每个函数都放在一个组别中。

     #include <stdio.h>
     int bar(int x, int n);
     int foo(int x, int n);

     main()
     {
         int a, n;(1)      scanf("%d", &n);(2)      a = foo(0,n);(3)      printf("%d\n", bar(a,n));
     }

     int bar(int x, int n)
     {
         int i;(4)      for (i = 1; i <= n; i++)(5)          x += i;(6)      return x;
     }

     int foo(int x, int n)
     {
         int i;(7)      for (i = 1; i <= n; i++)(8)          x += bar(i,n);(9)      return x;
     }复制代码

图 3-21　展示非递归函数调用的程序

图 3-22　图3-21所示程序的调用图

我们分析函数运行时间的顺序，也就是为了理解该程序的行为而对其进行研究的顺序。因此，首先考虑一下bar函数是做什么的。第(4)行和第(5)行的for循环会将从1到n 的这n 个整数都加到x 上，结果就是bar(x,n)等于。这里的和式又是个为算术级数求和的例子，只要将第一项与最后一项相加，乘以项数，然后再除以2即可。也就是。因此，bar(x,n)=x+(1+n)n/2。

现在，考虑一下foo函数，它会给它的参数x加上和式

根据我们对bar函数的了解可知，bar(i,n)=i+n(n+1)/2。因此，foo函数就是给x加上了这个量。这样就要为另一个算术级数求和了，而这个算术级数需要更多的代数变换。不过，读者可以验证一下，foo函数加到x上的这个量就是(n3+2n2+n)/2。

最后看看main函数。我们在第(1)行读入n，在第(2)行将foo应用到0和n上。根据我们对foo函数的理解，第(2)行foo(0,n)的值就是0加上(n3+2n2+n)/2。在第(3)行，要将bar(foo(0,n),n)的值打印出来，根据我们对bar函数的理解，这就是n(n+1)/2与foo(a,n)当前值的和。因此，要打印的值就是(n3+2n2+n)/2。

现在来分析图3-21所示程序的运行时间，从bar函数开始，到foo函数，再到main函数，一如我们在示例3.23中所做的那样。在这种情况下，我们要确定值n是所有三个函数的输入的大小。也就是说，即便我们通常想考虑函数所有参数的“大小”，但在本例中函数的运行时间只取决于n。

要分析bar函数，先要注意到第(5)行所花的时间为O(1)。第(4)行和第(5)行的for循环要迭代n次，所以第(4)行和第(5)行的运行时间是O(n)。第(6)行花的时间也是O(1)，所以第(4)行至第(6)行的程序块的运行时间是O(n)。

接着分析foo函数。第(8)行的赋值语句花的时间是O(1)加上调用bar(i,n)所用的时间。而我们已经知道，该调用花的时间为O(n)，所以第(8)行的运行时间就是O(n)。第(7)行和第(8)行的for循环要迭代n次，所以可以用循环体的运行时间O(n)乘上循环迭代的次数n，得到调用foo函数的运行时间是O(n2)。

最后来分析main函数。第(1)行所花的时间为O(1)，第(2)行对foo函数的调用所花的时间为O(n2)，第(3)行的打印语句所花的时间为O(1)加上调用bar函数所花的时间。而后者所花时间为O(n)，所以整个第(3)行所花的时间为O(1)+O(n)。因此从第(1)行到第(3)行的整个程序块的运行时间为O(1)+O(n2)+O(1)+O(n)。根据求和规则，可以消除第二项之外的所有项，得出该函数的运行时间为O(n2)。也就是说，第(2)行对foo函数的调用决定了整个时间开销。

证明和对程序的理解

读者可能注意到，在对图3-21所示程序的研究中，我们能理解程序在做什么，却不能像在第2章中那样正式地证明点什么。不过，在这表面之下却潜藏着诸多简单的归纳证明。例如，需要对第(4)行和第(5)行循环迭代的次数进行归纳，证明在我们用值为i 的i开始迭代之前，x的值是x的初始值加上。请注意，如果i=1，这个和式不含任何项，则其值会为0。

习题

1. 证明示例3.23中的结论：

2. 假设prime(n)是运行时间为的函数调用。考虑一下函数体如下的函数：

if ( prime(n) )
　　A;
else
　　B;

分别假设：

(a) A所花的时间为O(n)，B所花的时间为O(1)；

(b) A和B所花的时间都为O(1)。

用n的函数表示出这两种情况下该函数运行时间的简单大O上界和紧大O上界。

3. 考虑函数体如下的函数：

sum = 0;for (i = 1; i <= f(n); i++)
    sum += i;复制代码

其中f(n)是函数调用。分别假设：

(a) f (n)的运行时间是O(n)，而f (n)的值是n!；

(b) f (n)的运行时间是O(n)，而f (n)的值是n；

(c) f (n)的运行时间是O(n2)，而f (n)的值是n；

(d) f (n)的运行时间是O(1)，而f (n)的值是0。

用n 的函数表示出这4种情况下该函数运行时间的简单大O上界和紧大O上界。

4. 绘出2.8节归并排序程序中函数的调用图。那个程序是否为递归程序？

5. * 假设图3-21中foo函数的第(7)行被替换为

for (i = 1; i <= bar(n,n); i++)复制代码

那么main函数的运行时间会是多少？

邢台网站制作要多少钱【域名企业邮箱服务器注册申请办理】邢台网络优化公司哪家好、邢台软件开发外包价格、邢台高端企业网站页面制作设计专业公司、邢台微信公众号小程序购物支付搭建制作公司