衡水网站制作【衡水网站优化】衡水建网站、衡水微信公众号运营、衡水网页设计、衡水微信小程序商城

发表日期： 2021-04-13 09:35:05 浏览次数：168

衡水，河北省地级市，位于河北省东南部，介于东经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.4　习题

1. 绘出下列函数的结构树。

(a) split

(b) MergeSort

2. * 将k 路归并排序函数定义为把一个表分为k 部分，在为每部分排序后合并各部分得到结果。

(a) 用k 和n 的函数表示的k 路归并的运行时间是怎样的？

(b) **什么样的k 值可以带来最快的算法（用n 的函数表示）？这个问题要求大家对运行时间作出足够精确的估算，从而保证自己可以区分一些常数因子。出于我们在本章开头所讨论过的原因，在实践中不可能那样精确，所以大家需要研究一下由习题(a)中得到的运行时间是怎样随着k 变化的，并据此得出近似的最小值。

3.11　为递推关系求解

求解递推关系的技巧有很多。本节将讨论两种方法。第一，就是我们已经看到的，反复将递归规则代换到它们自身中，直到得出T(n)与T(1)的关系，或者T(n)与依据给出的某个T(i )之间的关系（如果1不是依据的话）。第二种方法是猜测一种解，并将其替换到依据和归纳规则中以验证其正确性。

在3.9和3.10两节中，我们已经为T(n)准确求解了。不过，因为T(n)实际上是确切运行时间的大O上界，所以找出T(n)的紧上界就够了。因此，特别是对于“猜测并验证”的方法，只需要求出的解是递推关系真正解的上界就可以了。

3.11.1　通过反复代换为递推关系求解

示例3.24所示的递推关系可能是我们在实践中遇到的最简单的递推关系了。

依据。T(1)=a。

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

如果可以在归纳中将常数b换成某个函数g(n)，就可以将这种形式进一步一般化，于是我们可以将这种形式写成下面这样。

依据。T(1)=a。

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

只要递归函数花了时间g(n)，并接着用比当前函数调用所使用的参数小1的参数调用自身，就出现了这种形式。例子有示例3.24中的阶乘函数、3.10节中的merge函数，以及2.7节中的递归选择排序。在前两个函数中，g(n)是常数，而在第三个函数中，g(n)是n 的线性函数。3.10节中的split函数也基本是这种形式，只不过它递归地调用自身所使用的参数是依次减小2的。我们应该明白，这种差别是不重要的。

接下来通过反复代换来求解该递推关系。正如示例3.24中那样，首先将归纳规则用参数m的函数表示出来，即

T(m)=T(m-1)+g(m)

接着反复替换原归纳规则右边的T。这样做，就可以得到一串表达式：

$\begin{align*}T(n)&=T(n-1)+g(n)\\&=T(n-2)+g(n-1)+g(n)\\&=T(n-3)+g(n-2)+g(n-1)+g(n)\\&\dots\\&=T(n-i)+g(n-i+1)+g(n-i+2)+\dots+g(n-1)+g(n)\end{align*}$

运用示例3.24中介绍的技巧，就可以通过对i的归纳，证明对i=1、2、…、n-1，有

$T(n)=T(n-i)+\sum^{i-1}_{j=0}g(n-j)$

我们希望选择一个i值，让依据情况可以涵盖T(n-i )，因此我们选择i=n-1。因为T(1)=a，所以有 $T(n)=a\sum^{n-2}_{j=0}g(n-j)$ 。换句话说，T(n)就是常数a加上从2到n 的所有g之和，或者说是a+g(2)+g(3)+…+g(n)。除非所有的g(j )都为0，否则在将该表达式转换为大O表达式时，a这项都是无关轻重的，因此一般只需要g(j )的和就行了。

示例 3.25

考虑一下图2-22所示的递归选择排序函数，我们在图3-29中重新展示了该函数的函数体。在需要为含m个元素的数组排序时，也就是当参数i的值为n-m时，如果设SelectionSort函数的运行时间为T(m)，那么就可以得出关于T(m)的如下递推关系。首先，依据是m=1。这时，只有第(1)行执行，花的时间为O(1)。

(1)      if (i < n-1) {(2)              small = i;(3)              for (j = i+1; j < n; j++)(4)                  if (A[j] < A[small])(5)                      small = j;(6)              temp = A[small];(7)              A[small] = A[i];(8)              A[i] = temp;(9)              recSS(A, i+1, n);
             }
     }复制代码

图 3-29　递归的选择排序

对m>1时的归纳，我们会执行第(1)行的测试以及第(2)、(6)、(7)、(8)行的赋值，这些语句的运行时间是O(1)。而第(3)至第(5)行的for循环的运行时间为O(n-i )，或者O(m)，就像我们在示例3.17中讨论过的迭代选择排序程序那样。要知道原因，请注意第(4)行和第(5)行的循环体所花的时间为O(1)，而我们要进行m-1次循环。所以，该for循环的运行时间主导了第(1)至第(8)行的运行时间，这样就可以将整个函数的运行时间T(m)写为T(m-1)+O(m)。第2项O(m)覆盖了第(1)至第(8)行，而T(m-1)这项则是第(9)行的递归调用的时间。如果将隐藏在大O表达式背后的常数因子替换为某个具体的常数，就可以得到以下递推关系。

依据。T(1)=a。

归纳。对m>1，T(m)=T(m-1)+bm。

该递推关系具有我们研究过的形式，其中g(m)=b(m)。也就是说，该递推关系的解为

$\begin{align*}T(m)&=a+\sum^{m-2}_{j=0}b(m-j)\\&=a+2b+3b+\dots+mb\\&=a+b(m-1)(m+2)/2\end{align*}$

因此T(m)是O(m2)。我们感兴趣的是SelectionSort函数处理长度为n的整个数组时的运行时间，也就是说，当用i=1调用函数时，我们需要T(n)的表达式，并得出它是O(n2)。因此，递归的选择排序是二次的，就像迭代的选择排序那样。

递推的另一种常见形式是在3.10节中为MergeSort函数得出的递推关系。

依据。T(1)=a。

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

该递推关系表示的是一个递归算法，它通过将大小为n 的问题细分为两个大小为n/2的子问题来解决问题。这里g(n)是创建子问题以及结合解决方案所花的时间。例如，MergeSort将大小为n的问题分为大小为n/2的两个部分。函数g(n)具有bn 的形式，其中b是某个常数，因为MergeSort除了递归调用自身之外，所花的时间是O(n)，主要就是用在split和merge算法上。

要求解该递推关系，需要替换等式右边的T。这里我们假设对某个k 有n=2k。递推关系可以写为参数为m 的函数：T(m)=2t(m/2)+g(m)。如果用n/2i 替换m，就得到

T(n/2i )=2T(n/2i+1)+g(n/2i )　　　　　　(3.8)

如果由归纳规则开始，接着用i 值逐渐变大的(3.8)替换T，就会发现

$\begin{align*}T(n)&=2T(n/2)+g(n)\\&=2\bigl(2T(n/2^2)+g(n/2)\bigr)+g(n)\\&=2^2T(n/2^2)+2g(n/2)+g(n)\\&=2^2\bigl(2T(n/2^3)+g(n/2^2)\bigr)+2g(n/2)+g(n)\\&=2^3T(n/2^3)+2^2g(n/2^2)+2g(n/2)+g(n)\\&\quad\dots\\&=2^iT(n/2^i)+\sum^{i-1}_{j=0}2^jg(n/2^j)\\\end{align*}$

如果n=2k，我们知道T(n/2k)=T(1)=a。因此，当i=k时，也就是当i=log2n 时，可以得到递推关系的解为

$T(n)=an+\sum^{(\log_2n)-1}_{j=0}2^jg(n/2^j)$ 　　　　　　(3.9)

直观地讲，(3.9)的第一项表示依据值a 带来的时间，也就是以大小为1的参数调用该递归函数n 次的时间。而和项则是递归所花的时间，它表示以大小大于1的参数执行的所有调用的总时间。图3-30展示了MergeSort函数执行期间的时间积累情况。它表示为8个元素排序的时间。

第一行表示最外层的调用，涉及全部8个元素；第二行表示对两组4个元素的两次调用；第三行表示对4组两个元素的4次调用。最后，底部那行表示对长度为1的表调用MergeSort共8次。一般来说，如果原始无序表中有n个元素，那么通过引发其他调用的MergeSort调用完成bn 的工作就需要log2n层调用，因此这些调用累计的时间就是bn log2n。还将有一层的调用不会引起进一步的调用，这些调用所花的总时间是an。请注意，前log2n层调用表示的是(3.9)中的和项，而最下面的那层表示an那项。