邢台微信公众号开发【邢台网络推广】邢台建站、邢台网站维护、邢台网页制作、邢台微信小程序代运营公司

邢台微信公众号开发【邢台网络推广】邢台建站、邢台网站维护、邢台网页制作、邢台微信小程序代运营公司

邢台，简称“邢”，古称邢州、顺德府，是河北省地级市，河北省政府批复确定的京津冀城市群节点城市、河北省级历史文化名城、冀中南先进制造业基地和物流枢纽 [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.4　大 O 运行时间和近似运行时间

假设我们编写了一个C语言程序，并选择了想要它处理的特定输入。程序处理这一输入的运行时间仍取决于以下两个因素。

1. 运行该程序的计算机。一些计算机执行指令的速度比其他计算机更快，最快的超级计算机与最慢的个人计算机之间的性能比远大于1000∶1。

2. 生成计算机可执行程序所使用的特定C语言编译器。在同一计算机上，执行不同程序所用的时间是不一样的，即便这些程序有着相同的功效。

这样一来，我们就不能看着C语言程序及其输入，然后判断说：“这个任务要花上3.21秒。”除非知道用的什么计算机和编译器。此外，就算我们知道程序、输入、机器和编译器，要准确预计将要执行的机器指令数通常也是一项过于复杂的任务。

出于这些原因，我们通常用大O表示法来表示程序的运行时间，该方法让我们可以不去考虑如下常数因子。

1. 特定编译器生成机器指令的平均数。

2. 特定计算机每秒执行机器指令的平均数。

例如，就像在示例3.1中那样，我们研究的SelectionSort程序段处理长度为m的数组将耗时4m-1。不过这里我们不这么说，而是说它耗时O(m)，非正式的含义是“某个常数乘以m”。

“某个常数乘以m”这一表述不仅能让我们忽略那些与编译器和计算机相关的未知常数，还让我们可以作出一些起简化作用的假设。例如，在示例3.1中，假设所有的赋值语句会消耗长短相同的一段时间，而在测试for循环的终止、随着循环进行递增j，以及进行变量初始化等工作时，也都会消耗这样长的一段时间。因为这些假设在实际情况中都是不可能的，所以在运行时间方程T(m)=4m-1中，常数4和-1是对事实的最佳逼近。可以更近似地将T(m)描述为“某个常数乘以m，再加上或减去某个常数”，甚至描述为“最多与m成正比”。O(m)表示法使我们可以在不涉及不可知或无意义常数的情况下作出这些陈述。

另一方面，将程序段的运行时间表示为O(m)，也告诉我们一些非常重要的事情。它表明，执行处理逐步变大的数组的程序，所花的时间是线性增长的，就像3.3节末尾的图3-2和图3-3中假想的程序A那样。因此，该程序段表示的算法，优于运行时间增长更快的算法（比如在上文的讨论中与程序A相对比的假想程序B）。

3.4.1　大O的定义

我们现在要给出某个函数是另一个函数的“大O”的正式定义。设有函数T(n)，这通常是某个程序的运行时间，以输入大小为n的函数来度量。要让函数适用于度量程序的运行时间，我们假设有：

1. 参数n 被限定为非负整数；

2. 值T(n)对所有的参数n 来说都非负。

设f (n)是某个定义在非负整数n之上的函数。如果除了对某些较小的n值之外，T(n)至多是某个常数乘以f (n)，我们就可以说

“T(n)是O(f (n))”。

正式地说，如果存在某个整数n0以及某个大于0的常数c，使得对所有大于n0的整数n，都有T(n)≤cf (n)，那么我们就说T(n)是O(f (n))。

我们把数对n0和c 称为“T(n)是O(f (n))”这一事实的证物（witness）。在接下来的证明中，该证物可以为T(n)和f(n)的大O关系“作证”。

3.4.2　证明大O关系

可以应用“大O”的定义证明对特定的函数T和f，T(n)就是O(f(n))。我们会通过选择特定的证物n0和c，接着证明T(n)≤cf(n)，从而完成这一证明。证明过程必须假设n是非负整数，且不小于我们选择的n0。通常，证明过程涉及一些代数和不等式的变换。

示例 3.2

假设有某个程序，其运行时间为T(0)=1，T(1)=4，T(2)=9，一般表示为T(n)=(n+1)2。我们就可以说T(n)是O(n2)，或者说T(n)是二次幂的，因为可以选择证物n0=1和c=4。然后需要证明(n+1)2≤4n2，其中有n≥1。在证明过程中，我们将表达式(n+1)2展开为n2+2n+1。只要n≥1，我们就知道有n≤n2而且有1≤n2。因此

n2+2n+1≤n2+2n2+n2=4n2

此外，也可以选择证物n0=3和c=2，因为，正如大家可以验证的，对所有的n≥3，都有(n+1)2≤2n2。

不过，不能选择n0=0，因为若n0=0，那么对n=0，我们可以证明(0+1)2≤c 02，也就是有1小于等于c 乘以0。因为不管选择什么c，都有c×0=0，而1≤0是不成立的，所以如果我们选择n0=0就玩完了。不过没关系，因为要证明(n+1)2是O(n2)，所以只要找出一组可行的证物n0和c 就行了。

大O证明的模版

请记住：所有的大O证明基本遵循相同的形式，只有代数变换是各异的。要证明T(n)就是O(f(n))，要做的只有下面两件事。

1. 说明证物n0和c。这些证物必须是特定的常数，比如n0=47和c=12.5。还有，n0必须是非负整数，而c 必须是正实数。

2. 通过适当的代数变换，证明对所选择的特定证物n0和c，如果n≥n0，则有T(n)≤cf(n)。

这可能看起来有些奇怪，虽然(n+1)2大于n2，但是我们还是说(n+1)2是O(n2)。其实，也可以说(n+1)2是任意分之n2的大O，例如O(n2/100)。要看看原因的话，选择证物n0=1和c=400。那么如果n≥1，由与示例3.2中一样的推导可知

(n+1)2≤400(n2/100)=4n2

这些现象背后的基本原则如下。

1. 常数因子不产生影响。对于任意正值常数d 和任意函数T(n)，T(n)是O(dT(n))，不论d 是很大的数，还是很小的分数，只要d>0即可。要知道为什么，可以选择证物n0=0和c=1/d。3那么就有T(n)≤c(dT(n))，因为cd=1。类似地，若已知T(n)是O(f (n))，便也知道对任何的d>0，有T(n)是O(df (n))，即便d 很小。因为我们知道，对某个常数c1和所有的n≥n0，有T(n)≤c1f (n)。如果选择c=c1/d，那么就可以看到，对n≥n0，有T(n)≤c(df(n))。

3请注意，虽然要求选择常数而不是函数作为证物，但选择c=1/d 是没有错的，因为d 本身也是个常数。

2. 低阶项不产生影响。假设T(n)是形如

aknk+ak-1nk-1+…+a2n2+a1n+a0

的多项式，其中开头的系数ak为正数。然后我们可以扔掉除第一项（就是具有最高指数k的那项）之外的所有项，并利用规则(1)，忽略常数ak，直接用1代替它。也就是说，我们可以得出T(n)就是O(nk)。为了证明这一点，设n0=1，并设c是各系数ai中所有正系数的和，其中0≤i≤k。如果系数aj 是0或负数，那么肯定有ajn j≤0。如果aj 为正，那么对所有的j< k，只要n≥1，都有ajn j≤aknk。因此T(n)不大于nk乘以所有正系数之和，或者说是T(n)≤cnk。

关于大O的谬论

对“大O”的定义是很诡异的，在该定义中，在检查完T(n)和f (n)后，我们要一次性选择证物n0和c，接着证明对所有的n≥n0，都有T(n)≤cf (n)。不能为每个n值重新选择c 和（或）n0。例如，大家可能偶尔会看到如下证明n2为O(n)的谬误“证明”。“选择n0=0，并为每个n 选择c=n。然后有n2≤cn。”这种论述是无效的，因为我们要求在不知道n 的情况下一次性选定c。

示例 3.3

作为规则(1)（“常数因子不产生影响”）的例子，我们看到2n3是O(0.001n3)。令n0=0，而且c=2/0.001=2000。那么显然有，对所有的n≥0，2n3≤2000(0.001n3)=2n3。

作为规则(2)（“低阶项不产生影响”）的例子，考虑多项式T(n)=3n5+10n4-4n3+n+1。最高位的项是n5，我们就说T(n)是O(n5)。要验证该说法，令n0=1，c等于所有正系数的和。正系数的项包含指数为5、4、1和0的这些项，其系数分别为3、10、1和1。因此，令c=15。我们可以说，对n≥1，有

3n5+10n4-4n3+n+1≤3n5+10n5+n5+n5=15n5　　　　　　(3.1)

我们可以通过对正系数项的匹配来验证不等式(3.1)，也就是，3n5≤3n5，10n4≤10n5，n≤n5，以及1≤n5。而且，因为-4n3≤0（之前假设n为正数），所以可以忽略不等式(3.1)左边的负系数项。因此，不等式(3.1)的左边，也就是T(n)，要小于等于不等式的右边，也就是15n5，或者说是cn5。由此可以得出T(n)是O(n5)的结论。

其实，低阶项可以删除的原则不仅适用于多项式，而且适用于任何表达式之和。也就是说，如果随着n趋近无穷大，h(n)/g(n)的比值趋近于0，则可以说h(n)比g(n)“增长得慢”，或者说h(n)的“增长率低于”g(n)，这样就可以忽略h(n)。也就是说h(n)+g(n)是O(g(n))。

例如，设T(n)=2n+n3。众所周知，多项式（比如n3）要比指数式（比如2n）增长得慢。因为随着n的增大，n3/2n趋近于0，所以我们可以扔掉低阶项，并得出T(n)是O(2n)的结论。

要正式地证明2n+n3是O(2n)，令n0=10，c=2。必须证明，对n≥10，有

2n+n3≤2×2n

如果从两边都减去2n，就会发现这是要证明对n≥10，有n3≤2n。

对n=10，我们有210=1024。而103=1000，因此对n=10，有n3≤2n。n每增加1，2n就会翻倍，而n3则是会乘以(n+1)3/n3这个量，而当n≥10时，这个量是小于2的。因此，随着n的增大，n3会逐步小于2n。我们可以得出结论：对n≥10，有n3≤2n，因此有2n+n3是O(2n)。

3.4.3　证明大O关系不成立

如果两个函数之间的大O关系成立，就可以通过找出证物来证明这种关系。然而，如果某个函数T(n)不是另一个函数f(n)的大O呢？答案就是，经常可以证明某个特定的函数T(n)不是O(f(n))。证明方法是，假设证物n0和c存在，并推理出矛盾。下面要介绍这种证明的一个例子。

示例 3.4

在前文附注栏“关于大O的谬论”中，我们声称n2不是O(n)。我们可以证明该声明，方法如下。假设n2是O(n)，然后就存在证物n0和c，使得对所有的n≥n0，都有n2≤cn。不过如果我们选择n1等于2c 和n0中较大者，就会有不等式

(n1)2≤cn1　　　　　　(3.2)

一定成立（因为n1≥n0，而且对所有的n≥n0，n2≤cn都是成立的）。

如果将不等式(3.2)两边都除以n1，就有n1≤c。然而，我们还选择了n1至少是2c。因为证物c一定为正数，所以n1不可能既小于c 又大于2c。因此，可以证明“n2是O(n)”的证物n0和c 不存在，由此可以得出结论：n2不是O(n)。

3.4.4　习题

1. 考虑以下4个函数。

f1:n2

f2:n3

对等于1、2、3、4的i 和j，分别确定fi (n)是不是O(fj (n))。要么给出证明大O关系的n0和c 的值，要么假设存在这样的n0和c，并推理出矛盾，证明fi (n)不是O(fj (n))。提示：请记住，除了2之外，所有的质数都是奇数。还要记住，质数有无数个，而合数也有无数个。

2. 有以下一些大O关系。请为每个大O关系给出可用来证明这种关系的证物n0和c。选择最小的一组证物，也就是说n0-1和c不是证物，而如果d< c，那么n0和d 也不是证物。

(a) n2是O(0.001n3)。

(b) 25n4-19n3+13n2-106n+77是O(n4)。

(c) 2n+10是O(2n)。

(d) n10是O(3n)。

(e) * log2n是

3. * 证明：如果对所有的n有f(n)<g(n)，那么f(n)+g(n)是O(g(n))。

4. ** 假设f (n)是O(g(n))，而且g(n)是O(f (n))。那么f (n)和g(n)之间有什么关系？是不是一定有f (n)=g(n)？随着n 趋近无穷大，f (n)/g(n)的极限是否一定存在？

证明大O关系不成立的模板

证明函数T(n)不是O(f (n))的常见证明过程如下。示例3.4就展示了这样的证明过程。

1. 首先假设存在证物n0和c，使得对所有的n≥n0，都有f (n)≤cg(n)。这里，n0和c 是表示未知证物的符号。

2. 定义特定的整数n1，用与n0和c 相关的形式表示（例如，在示例3.4中，我们选择的是n1=max(n0,2c )）。该n1是用来证明T(n1)≤cf (n1)的n 的值。

3. 证明，对于这个选定的n1，有n1≥n0。这一部分是非常简单的，因为我们在第(2)步中选择的n1至少是n0。

4. 声明因为有n1≥n0，所以一定有T(n1)≤cf (n1)。

5. 通过证明对我们选择的这个n1有T(n1)>cf (n1)，从而推导出矛盾。选择与c 有关的n1可以让这个部分变得很简单，就像示例3.4中所做的那样。

邢台微信公众号开发【邢台网络推广】邢台建站、邢台网站维护、邢台网页制作、邢台微信小程序代运营公司