沧州网站推广【沧州办理400电话】沧州SEO优化、沧州微信公众号APP客户端小程序开发、沧州网站托管、沧州APP开发

沧州网站推广【沧州办理400电话】沧州SEO优化、沧州微信公众号APP客户端小程序开发、沧州网站托管、沧州APP开发

沧州市，河北省地级市，地处河北省东南部、河北平原东部的黑龙港流域，位于北纬37°29′～38°57′，东经115°42′～117°50′之间。东部滨临渤海，北部与天津、廊坊接壤，西部及西南部与保定、衡水毗邻，南隔漳卫新河与山东省的滨州、德州相望。

沧州市因濒临渤海而得名，市中心北距天津市120千米、北京市240千米，西南距省会石家庄220千米。沧州市辖2个市辖区，4个县级市，10个县及沧州渤海新区、沧州经济开发区、沧州高新技术产业开发区，总面积1.4万平方公里。 [1-3] 

2020年10月，入选河北省第一批新型智慧城市建设试点名单。

从图3-2可知，对大小小于50的输入来说，程序B要比程序A快。当输入的大小大于50时，程序A就要更快了，而且从50这个临界点开始，输入越大，程序A相比程序B而言优势就越大。对大小为100的输入，A要比B快上2倍，而对大小为1000的输入，A要快上20倍。

程序运行时间的函数形式最终确定了我们能用该程序解决多大的问题。随着计算机速度的不断变快，与运行时间增长迅速的程序相比，那些运行时间增长缓慢的程序在可处理问题的规模上能取得更大的提高。

再次假设图3-2所示的程序运行时间是以毫秒计的，图3-3中的表格表示了在同一台计算机上，花同样的时间，使用两种程序分别能解决多大的问题。例如，假设可以接受100秒的计算时间。如果计算机的速度加快10倍，那么在100秒内能处理之前需要花1000秒去处理的问题。对算法A来说，我们现在可以解决10倍大小的问题，而对算法B来说，只可以解决3倍大小的问题。因此，随着计算机速度的持续加快，通过使用低增长率的算法和程序可以获得更为显著的优势。

图 3-3　在可用时间段函数可解决问题的大小

别在乎算法的效率，再等上几年就行了

大家可能经常听到这样的说法、不需要缩短算法的运行时间或是选择更高效的算法，因为计算机的速度每隔几年就会翻番，而且不需要多久，任何算法，不管有多低效，所花的时间都会少到没有人在意了。这一论调的出现已经有几十年的时间了，但计算资源需求上限尚未出现，因此，我们一般都不接受硬件改善可以让高效算法的研究变成无用功这种观点。

不过，也存在我们不需要过分考虑效率的情况。例如，某所学校在每学期期末都要将存储在某台计算机中的学生电子成绩表打印成纸质成绩单。该操作所花的时间大概与要报告的成绩数量成线性关系，就像假想算法A那样。如果学校更换了一台速度快上10倍的计算机，完成这项工作所花的时间就会变为原来的十分之一。不过，学校因此要扩招10倍，或是要求每个学生增加10倍的课程，这是很不现实的。计算机的提速不会影响到成绩单程序的输入大小，因为这一大小是受其他因素限制的。

另一方面，还会存在另外一些问题，我们凭借新兴的计算资源有了一些解决的头绪，不过它们的“大小”却超出了现有技术的处理能力。这样的问题包括自然语言的理解、计算机视觉（对数字化图像的理解），以及各种对人机“智能”交互的尝试。不管是通过改善算法还是通过提升机器性能，所获得的加速都将提升我们在接下来几年里处理这些问题的能力。此外，当它们变成“简单”的问题后，我们现在很难想象的新一代挑战又会替代它们摆在计算机面前。

3.3.5　习题

1. 考虑一下图2-13中的阶乘程序段，设输入大小为读取的n的值。每次执行赋值、读和写语句记为一个时间单位，每进行一次while循环条件测试记为一个时间单位，计算该程序的运行时间。

2. 为2.5节习题1以及图2-14中的程序段给出恰当的输入大小。运用上一题中的计数规则，确定这两个程序的运行时间。

3. 假设程序A花费2n/1000个时间单位，程序B花费1000n2个时间单位。对哪些n值来说，程序A花的时间比程序B少？

4. 对上一题中的两个程序，在106个、109个和1012个时间单位内能解决的问题各有多大？

5. 假设程序A花费1000n4个时间单位，程序B花费n10个时间单位，重复习题3和习题4中的练习。

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关系“作证”。

沧州网站推广【沧州办理400电话】沧州SEO优化、沧州微信公众号APP客户端小程序开发、沧州网站托管、沧州APP开发