邢台400电话申请开通【邢台企业网站建设】邢台微信公众号小程序开发运营价格、邢台微信公众号APP软件客户端设计运营、邢台网页页面设计公司费用、邢台公司网站制作方案流程改版维护大概需要多少钱

邢台400电话申请开通【邢台企业网站建设】邢台微信公众号小程序开发运营价格、邢台微信公众号APP软件客户端设计运营、邢台网页页面设计公司费用、邢台公司网站制作方案流程改版维护大概需要多少钱

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

确定递归调用自身的函数的运行时间，需要比分析那些非递归函数耗费更多的精力。递归函数的分析需要我们将程序中的每个函数F 与某个未知的运行时间TF (n)关联起来。这一未知的函数将F 的运行时间表示为F 函数参数的大小n 的函数。然后构建一套归纳定义，称为TF (n)的递推关系，将TF (n)与同一程序中其他函数G 及其相应的参数大小k 表示的TG(k)形式关联起来。如果F 是直接递归的，那么G 中至少有一个将与F 是相同的。

TF (n)的值通常是通过对参数大小n 的归纳取得的。因此，需要选择合适的参数大小，保证随着递归的进行，函数在被调用时所使用的参数在逐渐减小。这一要求与我们在2.9节中试图证明有关递归程序的命题时遇到的要求别无二致。这应该没什么可奇怪的，因为有关程序运行时间的命题正是我们可能试着证明的与程序相关的某种内容。

一旦找到了合适的参数大小，就可以考虑以下两种情况了。

1. 参数大小足够小，使F 不进行递归调用。这种情况对应TF (n)归纳定义中的依据。

2. 对于较大的参数大小，将至少会发生一次递归调用。请注意，无论F进行怎样的递归调用，不管是对其自身还是对某个其他函数G 进行递归调用，都只可能使用更小的参数。这种情况对应TF (n)归纳定义中的归纳步骤。

通过对函数F 的代码的研究，并完成如下操作，可以得出TF (n)递推关系的定义。

(a) 对函数G 的每次调用或表达式中函数G 的每次使用（请注意，G 可能就是F），用TG (k)表示该次调用的运行时间，其中k 是对该次调用中参数大小的合理度量。

(b) 运用前面几节中介绍的技巧评估函数F 的函数体的运行时间，不过要将TG (k)这样的项留作未知函数，而不是诸如n2这样的具体函数。一般不能用求和规则这样的简化技巧把这些项与具体函数结合起来。我们必须对F 进行两次分析，一次假设F 的参数大小n 足够小，使得函数未进行递归调用，而另一次假设n 不是那么小。因此，我们得到了两个表示F 函数运行时间的表达式。其一（依据表达式）是TF (n)递推关系的依据，另一个（归纳表达式）则是TF (n)递推关系的归纳部分。

(c) 在得出的有关函数F 运行时间的依据表达式和归纳表达式中，用特定常数乘上有关函数（例如cf (n)）的形式来代替像O(f (n))这样的大O项。

(d) 如果输入大小的依据值为a，令TF (a)是在假设不存在递归调用的情况下，由步骤(c)得出的依据表达式。还有，令TF (n)是从步骤(c)得到的n 值不为依据值a 的情况下的归纳表达式。

           int fact(int n)
           {(1)            if (n <= 1)(2)                return 1; /* 依据*/
               else(3)                return n*fact(n-1); /* 归纳 */
           }复制代码

图 3-23　计算n!的程序

通过求解这个递推关系，就可以确定整个函数的运行时间。在3.11节中，我们将介绍一些一般性的技巧，用来在对普通递归函数的分析中求解这种递推关系。而现在，我们要通过特别 手段来求解这些递推关系。

示例 3.24

我们来重新考虑一下2.7节中计算阶乘函数的递归程序。因为只涉及fact这一个函数，所以使用T(n)表示该函数未知的运行时间。我们将使用参数的值n作为参数的大小。显然，当参数为n 时进行的fact函数的递归调用，要使用更小的参数，准确地说是n-1。

我们选择n=1作为T(n)归纳定义的依据，因为当fact函数的参数为1时，它不执行任何递归调用。当n=1时，第(1)行的条件为真，因此对fact的调用会执行第(1)行和第(2)行。每一行花的时间都是O(1)，所以依据情况中fact的运行时间为O(1)。也就是说T(1)是O(1)。

现在考虑当n>1时会发生什么。第(1)行的条件为假，因此只执行第(1)行和第(3)行。第(1)行花的时间是O(1)，而第(3)行会在乘法和赋值上用掉O(1)，并在对fact的递归调用上花费T(n-1)。也就是说，当n>1时，fact的运行时间是O(1)+T(n-1)。因此可以用以下递推关系定义T(n)。

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

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

现在要引入一些常数符号来表示隐藏在各大O表达式中的常数，就像之前在规则(c)中表述的那样。在这种情况下，可以用某个常数a代替依据中的O(1)，并用某个常数b替代归纳中的O(1)。这些变化给了我们如下的递推关系。

依据。 T(1)=a。

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

现在必须求解T(n)的这一递推关系。我们很容易计算出靠前的一些值，由递推依据T(1)=a，

以及归纳规则，我们得到

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

继续使用归纳规则，就得到

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

然后是

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

至此，不难猜测，对所有的n≥1，有T(n)=a+(n-1)b。其实，计算一些样本值，接着猜测解决方案，并最终通过归纳法证明猜测正确，这就是我们常用来处理递推关系的方法。

不过，在这个例子中，我们可以使用反复代换（repeated substitution）的方法直接得出解决方案。首先，在递归等式中进行如下变量代换，用m替换n，就得到

对m>1，T(m)=b+T(m-1)　　　　　　　　　　　　（3.3）

现在，可以用n、n-1、n-2、…、2替换等式(3.3)中的m，得到一系列的等式

　　(1) T(n)　=b+T(n-1)
　　(2) T(n-1)=b+T(n-2)
　　(3) T(n-2)=b+T(n-3)
　　　　　　　…
　 n-1) T(2)　=b+T(1)

接下来，可以利用上述系列等式中的第(2)行，来替换第(1)行中的T(n-1)，从而得到等式

T(n)=b+(b+T(n-2))=2b+T(n-2)

现在用第(3)行替换上式中的T(n-2)，就得到

T(n)=2b+(b+T(n-3))=3b+T(n-3)

按这种方式继续下去，每一次都将T(n)-i 替换为b+T(n-i-1)，直到向下达到T(1)。至此，就得到了等式

T(n)=(n-1)b+T(1)

接着可以利用依据，用a 替换T(1)，就可以得到T(n)=a+(n-1)b。

如果想让该分析过程更正式，就需要通过归纳法，对我们在反复对T(n-i )进行替换时的直观观察结果加以证明。因此，我们要通过对i 的归纳证明如下命题。

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

依据。依据为i=1，S(1)是说T(n)=b+T(n-1)。这是对T(n)的定义中的归纳部分，因此已知为真。

归纳。如果i≥n-1，就没什么要证明的，因为命题S(i+1)的开头是“如果1≤i+1≤n”，而当if语句的条件为假时，不管“那么”后面是如何表述的，该命题都为真。在这种情况下，若i≥n-1，则条件i+1<n一定为假。所以S(i+1)一定为真。

难点就在于，当i≤n-2的时候。在这种情况下，S(i )就是T(n)=ib+T(n-i )。因为i≤n-2，所以T(n-i )的参数至少为2。因此可以将该归纳规则应用到T上，也就是用n-i 替换等式(3.3)中的m，从而得出等式T(n-i )=b+T(n-i-1)。当我们用b+T(n-i-1)替换掉等式T(n)=ib+T(n-i )中的T(n-i )时，就得到T(n)=ib+(b+T(n-i-1))，重组这些项就得到

T(n)=(i+1)b+T(n-(i+1))

这个等式就是命题S(i+1)，而且我们现在已经证明了归纳步骤。

现在已经证明了T(n)=a+(n-1)b。不过，a和b都是未知的常数。因此，这样表示解决方案是不行的。不过，可以将T(n)表示为n的多项式，即bn+(a-b)，接着再用大O表达式来替代这些项，就得到了O(n)+O(1)。利用求和规则，还可以消掉O(1)，从而得出T(n)是O(n)。这就有意义了，它表示：要想计算n!，就要利用对fact的n次（实际调用次数刚好为n）调用的顺序，其中每次调用所需时间为O(1)，不计入花在执行对fact的递归调用上的时间。

习题

1. 为2.9节习题2中提到的sum函数（它是作为程序输入的表的长度的函数）的运行时间建立递推关系。请用（未知的）常数替换大O项，并试着求解这种递推关系。sum的运行时间是多少？

2. 对2.9节习题3中提到的find0函数重复习题1中的练习。合适的大小量度是什么？

3. * 对2.7节中图2-22所示的选择排序程序重复习题1中的练习。合适的大小量度是什么？

4. ** 对图3-24中的函数重复习题1中的练习，该函数是计算斐波那契数的（最开始的两个数是1，之后的每个数都是其前两个相邻数字之和。前7个斐波那契数分别是1、1、2、3、5、8、13）。请注意，n 的值是合适的参数大小，而且大家需要使用1和2作为依据情况。

int fibonacci(int n){
    if (n <= 2)
        return 1;
    else
        return fibonacci(n-1) + fibonacci(n-2);}复制代码

图 3-24　计算斐波那契数的C语言函数

5. * 编写递归程序计算gcd(i,j)，就是两个整数i和j的最大公约数，如2.7节习题(8)中概述的那样。证明该程序的运行时间是O(logi)。提示：在我们调用gcd(m,n)两次后证明这一点（其中m≤i/2）。

邢台400电话申请开通【邢台企业网站建设】邢台微信公众号小程序开发运营价格、邢台微信公众号APP软件客户端设计运营、邢台网页页面设计公司费用、邢台公司网站制作方案流程改版维护大概需要多少钱