邢台网站优化【邢台开通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.5.7　习题

1. 证明如下命题。

(a) 如果a≤b，那么na是O(nb)。

(b) 如果a>b，那么na不是O(nb)。

(c) 如果1< a≤b，那么an是O(bn)。

(d) 如果1< b< a，那么an不是O(bn)。

(e) 对任意a和任意b>1，na是O(bn)。

(f) 对任意b和任意a>1，an是O(nb)。

(g) 对任意a和任意b>0，(logn)a是O(nb)。

(h) 对任意b和任意a>0，na不是O((logn)b)。

2. 证明：f(n)+g(n)是O(max(f(n),g(n)))。

3. 假设T(n)是O(f(n))，且g(n)是某个值不为负的函数。证明：g(n)T(n)是O(g(n)f(n))。

4. 假设S(n)是O(f(n))，且f(n)是O(g(n))，而且这些函数对任意n都不为负值。证明：S(n)T(n)是O(f(n)g(n))。

5. 假设f(n)是O(g(n))。证明：max(f(n),g(n))是O(g(n))。

6. * 证明：如果f1(n)和f2(n)都是某个函数T(n)的紧边界，那么f1(n)和f2(n)互为对方的大O。

7. *证明：对于图3-6所示的函数f(n)，log2n不是O(f(n))。

8. 在图3-7所示的程序中，通过先在矩阵中每个位置放上0，然后在对角线上放上1，我们创建了一个单位矩阵。将第(4)行的测试改为询问是否有i=j，如果是，则在A[i][j]中放上1，如果不是，则放上0，这样修改后似乎能更快地完成这一工作。然后我们还可以删除第(5)行和第(6)行。

(a) 写出这一程序。

(b) * 考虑图3-7中的程序以及自己为问题(a)编写的程序。作出示例3.1中那样的简化假设，计算两个程序分别耗费了多少个时间单位。哪个程序更快？用不同大小的二维数组运行这两个程序，并绘制它们的运行时间曲线。

3.6　分析程序的运行时间

掌握了大O的概念，以及3.4节和3.5节中介绍的那些处理大O表达式的规则之后，我们将要学习如何获得常见程序运行时间的大O上界。只要有可能，我们将只考虑那些不含函数调用（除了诸如printf那样的库函数）的程序，将含有函数调用的问题留待3.8节及以后的内容中介绍。

我们不指望能够分析任意程序，因为有关运行时间的问题可能是非常难的数学问题。另一方面，只要了解一些简单的规则，我们就能够计算出实践中遇到的多数程序的运行时间。

3.6.1　简单语句的运行时间

这里要求读者接受这样一个原则，即某些对数据的简单操作可以在O(1)时间内完成，也就是说，这个时间是和输入大小无关的。C语言中的这些基本操作包括：

1. 算术运算（比如+或%）；

2. 逻辑运算（比如&&）；

3. 比较运算（比如<=）；

4. 结构体存取操作（比如A[i]这样的数组索引，或者跟在指针后的->运算符）；

5. 简单的赋值（比如将某个值复制到某个变量中）；

6. 对库函数（比如scanf、printf）的调用。

对这一原则的验证需要对常见计算机的机器指令（初始步骤）进行详细研究。我们很容易看出，之前描述的每种操作都只需要少量机器指令便可完成，通常只需要1条或2条指令。

因此，在C语言中有好几种语句都能在O(1)时间内执行完，也就是说，可以在与输入无关的某个时间段内执行完。这些简单语句包括：

1. 表达式中不涉及函数调用的赋值语句；

2. 读语句；

3. 不需要调用函数确定参数值的写语句；

4. 跳转语句break、continue、goto和return表达式，其中表达式不含函数调用。

在第(1)到第(3)条中，这些语句都是由有限数量的基本操作构成的，每个操作花的时间都是O(1)。由求和规则可知，整个语句花的时间是O(1)。当然，语句对应的时间常数要比单个操作对应的常数大，不过我们已经知道，无论如何也不能将具体的常数与C语言语句的运行时间关联起来。

示例 3.11

我们在示例3.9中看到，图3-7中第(1)行的读语句，以及第(4)行和第(6)行中的赋值，每一行花费的时间都是O(1)。再看一个例子，即图3-8中展示的选择排序程序段。第(2)、(5)、(6)、(7)和第(8)行，每一行花费的时间都是O(1)。

(1)        for (i = 0; i < n-1; i++) {(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;
           }复制代码

图 3-8　选择排序程序段

我们经常会看到由连续执行的简单语句构成的程序块。如果每条语句的运行时间都是O(1)，那么根据求和规则，整个程序块花费的时间也是O(1)。也就是说，任意固定多个O(1)的和还是O(1)。

示例 3.12

图3-8中的第(6)行到第(8)行形成了一个程序块，因为它们永远是连续执行的。由于每一行花的时间都是O(1)，所以第(6)行到第(8)行的程序块所花的时间也是O(1)。

请注意，不应该把第(5)行算在程序块中，因为它是第(4)行if语句的一部分。也就是说，有时候即便不执行第(5)行，第(6)行至第(8)行也会执行。

3.6.2　简单for循环的运行时间

在C语言中，很多for循环的构成包括初始化指标变量为某个值的语句，以及每进行一次循环就将该标量递增1的语句。当该指标达到某个限制后，for循环就终止了。例如，图3-8中第(1)行的for循环使用了指标变量i。每进行一次循环，它就将i递增1，而当i达到n-1时，迭代就停止了。

在C语言中，还有更复杂的for循环，其行为更类似while语句，这些循环迭代的次数是不可预知的。本节后面将会介绍这种循环。不过在这里，还是将注意力集中在形式简单的for循环上，在这种for循环中，最终值和初始值之间的差，除以指标变量每次递增的量，就可以得出循环了多少次。这种计数是精确的，除非还存在一些通过跳转语句退出循环的方式，否则这在任何情况下都是迭代次数的上界。例如，图3-8中for循环的第1行会迭代((n-1)-0)/1=n-1次，因为0是i 的初始值，n-1是i 达到的最高值（即当i 达到n-1时，循环就会终止，i=n-1时不会发生迭代），而且循环每次迭代i都会增加1。

要为for循环的运行时间找出边界，必须先找到循环体进行一次迭代所花时间的上界。请注意，进行一次迭代的时间包括递增循环指标（比如图3-8第(1)行中的递增语句i++）所花的时间O(1)，以及比较循环指标与上限（比如图3-8第(1)行中的测试语句i<n-1）所花的时间O(1)。除了循环体为空的异常情况，其他所有情况下的这些O(1)都可以根据求和规则舍弃掉。

在最简单的情况，也就是循环体每次迭代所花的时间均相同的情况下，可以用循环体的大O上界乘上循环的次数。严格地说，还必须加上初始化循环指标的时间O(1)，以及第一次比较循环指标和上限的时间O(1)。不过，除非有可能不执行循环，否则初始化循环和测试上限的时间都是根据求和规则可被舍弃的低阶项。

示例 3.13

考虑图3-7第(3)行和第(4)行中的for循环，也就是

(3)        for (j = 0; j < n; j++)(4)            A[i][j] = 0;复制代码

我们知道第(4)行花的时间为O(1)。显然，我们要进行n次循环，这可以由第(3)行找到的上限减去下限再加上1来确定。因为循环体，也就是第(4)行，花费的时间为O(1)，所以可以忽略递增j的时间O(1)以及比较j与n的时间O(1)。因此，第(3)行和第(4)行的运行时间为n与O(1)的积，也就是O(n)。

类似地，可以确定由第(2)行至第(4)行构成的外层循环的运行时间边界，外层循环如下。

(2)        for (i = 0; i < n; i++)(3)            for (j = 0; j < n; j++)(4)                A[i][j] = 0;复制代码

我们已经得到第(3)行和第(4)行的循环所花的时间为O(n)。因此，可以忽略递增i的时间O(1)以及每次迭代时测试是否有i< n所花的时间O(1)，并得出外层循环每次迭代所花的时间为O(n)。外层循环初始化i=0，以及第(n+1)次i< n 的条件测试花的时间都是O(1)，而且都可以忽略。最终，我们看到外层循环要循环n次，而每次迭代的时间都是O(n)，因此总运行时间就是O(n2)。

示例 3.14

现在来考虑图3-8第(3)行到第(5)行中的for循环。在这里，循环体是if语句，是我们接下来将要了解如何进行分析的结构。不难推断出第(4)行花费时间O(1)执行测试，第(5)行如果执行的话也会花费时间O(1)，因为它是不含函数调用的赋值语句。因此，不管第(5)行是否执行，执行for循环循环体所花的时间都为O(1)，循环中的递增和测试增加的时间都是O(1)，所以循环进行一次迭代的总时间也只是O(1)。

现在我们必须计算进行循环的次数。迭代次数是与输入大小n无关的。而公式“最后的值减去初始值除以递增量”告诉我们，(n-(i+1))/1，或者说n-i-1，是循环迭代的次数。严格地说，该公式只有在i<n时才成立。好在我们从图3-8的第(1)行可以看出，除非i≤n-2，否则我们不会进入第(2)至第(8)行的循环体。因此，我们不仅知道了n-i-1是循环迭代的次数，而且知道了这个数值不可能为0。由此可以得出该循环所花的时间为(n-i-1)×O(1)，或者说是O(n-i-1)。5此处不必加上初始化j所花的时间O(1)，因为已知n-i-1不可能为0。如果看不出n-i-1为正的话，就必须将运行时间的上界写为O(max(1,n-i-1))。

5从技术上讲，我们没有讨论过应用到多变量函数上的大O运算符。在这种情况中，可以将O(n-i-1)说成是“最多为某个常数乘以n-i-1”。也就是说，可以将n-i-1视为某个单变量函数的替代物。

邢台网站优化【邢台开通400电话】邢台网站搭建、邢台微信公众号推文外包、邢台开通京东拼多多设计、邢台淘宝装修