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

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

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

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

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

示例 3.15

正如我们在示例3.12中看到的，图3-8中第(4)行和第(5)行是选择语句，其中第(5)行是if部分，所花时间为O(1)，而不存在else部分（也就是所花时间为0）。因此，f (n)是1且g(n)是0。由于g(n)是O(f (n))，可以得出O(1)是第(4)行和第(5)行运行时间的上界。请注意，在第(4)行执行测试A[j]<A[small]的时间O(1)可以忽略。

示例 3.16

图3-9所示的代码段是个更为复杂的例子，它执行的（相对无意义的）任务是将矩阵A置为0，或是将矩阵的对角线置为1。一如我们在示例3.13中所了解的，第(2)行至第(4)行的运行时间是O(n2)，而第(5)行和第(6)行的运行时间是O(n)。因此这里的f (n)是n2，g(n)是n。因为n是O(n2)所以可以忽略else部分的时间，并将O(n2)作为图3-9中整个程序段运行时间的边界。也就是说，我们不知道第(1)行的条件是否将为真或者什么时候将为真，不过唯一安全的上界是从最坏的假设中得出的，即条件为真而且if部分执行了。

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

图 3-9　if-else选择语句的示例

3.6.4　程序块的运行时间

前文已经提到，一系列赋值、读、写操作，每一次操作的时间都是O(1)，总时间也是O(1)。一般的情况是，必须能将一系列语句（其中有一些是复合语句，也就是选择语句或循环）组合起来。这样一系列简单的复合语句就是程序块（block）。要计算程序块的运行时间，需要对程序块中每条（可能是复合的）语句的大O上界求和。好在可以使用求和规则消除和中的一些项。

示例 3.17

在图3-8的选择排序程序段中，可以将外层循环的循环体（也就是第(2)行至第(8)行）视为一个程序块。该程序块由5条语句组成。

1. 第(2)行的赋值语句。

2. 第(3)行、第(4)行和第(5)行的循环。

3. 第(6)行的赋值语句。

4. 第(7)行的赋值语句。

5. 第(8)行的赋值语句。

请注意，第(4)和第(5)行的选择语句以及第(5)行的赋值在程序块这一级是不可见的，它们已经隐藏在更大的语句，也就是第(3)行至第(5)行的循环中了。

我们知道，4条赋值语句每条所花的时间都是O(1)。在示例3.14中，已经了解到该程序块中第2条语句（也就是第(3)行至第(5)行）的运行时间是O(n-i-1)。因此，该程序块的运行时间是：

O(1)+O(n-i-1)+O(1)+O(1)+O(1)

因为1是O(n-i-1)（回想一下，我们还推导出i从不会大于n-2），所以可以通过求和规则消除所有的O(1)项。因此，整个程序块的运行时间就是O(n-i-1)。

再看一个例子，考虑一下图3-7中的程序段。它可被视为由3条语句组成的单一程序块。

1. 第(1)行的读语句。

2. 第(2)行至第(4)行的循环。

3. 第(5)行和第(6)行的循环。

我们知道，第(1)行花的时间为O(1)。从示例3.13可知，第(2)行至第(4)行花的时间是O(n2)，第(5)行和第(6)行花的时间是O(n)。所以整个程序块的运行时间就是：

O(1)+O(n2)+O(n)

根据求和规则，由O(n2)可以消去O(1)和O(n)。因此可以得出图3-7中程序段的运行时间为O(n2)。

3.6.5　复杂循环的运行时间

在C语言中，有一些while循环、do-while循环和for循环并未提供显式的计数变量。对于这些循环，一部分分析工作就是要找到为循环迭代次数提供上界的参数。这些证明过程通常都遵循我们在2.5节中了解的模式。也就是说，通过对循环次数的归纳证明某个命题，而该命题表明在迭代次数达到某个限制后，循环条件一定会变为假。

我们还必须建立执行一次循环迭代所花时间的边界。因此，可以对循环体加以研究，并获得其执行的边界。为了实现这个目标，必须在循环体执行后加上测试条件的时间O(1)，不过除非循环体不存在，否则我们都会忽略该O(1)项。通过用迭代次数的上界乘以一次迭代所花时间的上界，可以得到循环运行时间的边界。从技术上讲，如果该循环是for循环或while循环，而不是do-while循环，就必须将进入循环体之前第一次测试条件所需的时间包含在内。不过，这个O(1)经常是可以忽略掉的。

示例 3.18

考虑如图3-10所示的程序段。该程序会搜索数组A[0..n-1]，找出该数组中的元素x。

(1)        i = 0;(2)        while(x != A[i])(3)            i++;复制代码

图 3-10　线性查找的程序段

图3-10中第(1)行和第(3)行的两条赋值语句的运行时间均为O(1)。第(2)和第(3)行的while循环可能会执行n次，但不会超过n次，因为我们假设x确实是数组元素之一。因为第(3)行的循环体所需时间为O(1)，所以该while循环的运行时间就是O(n)。根据求和规则，整个程序段的运行时间为O(n)，因为这是第(1)行的赋值语句以及整个while循环所花的最大时间。在第6章中，我们还将看到这种O(n)程序是如何被使用二叉查找的O(logn)程序所代替的。

3.6.6　习题

1. 对开头为for (i = a; i <= b; i++)的for循环，用a 和b 的函数表示其循环次数。对开头为for (i = a; i <= b; i--)的for循环又是怎样表示的呢？对开头为for(i = a; i <= b; i = i+c)的for循环呢？

2. 给出某个普通的选择语句if(C) {} 运行时间的大O上界，其中C 是不涉及任何函数调用的条件。

3. 给出某个普通的while循环while(C ) {}运行时间的大O上界，其中C 是不涉及任何函数调用的条件。

4. * 给出C语言switch语句运行时间的规则。

5. 给出我们能确定哪条分支被执行的选择语句运行时间的规则，比如

if (1==2)
　　something O(f (n));
else
　　something O(g(n));

6. 给出循环开始前条件已知为假的退化while循环（degenerate while-loop）运行时间的规则，比如

while (1 != 1)
　　something O(f (n))

3.7　边界运行时间的递归规则

在3.6节中，我们简略地描述了一些规则，它们用程序结构各部分的运行时间来定义整个程序结构的运行时间。例如，我们说过for循环的运行时间大致等于循环体所花的时间乘以迭代的次数。隐藏在这些规则背后的概念是，程序是使用归纳规则构成的，复合语句（循环、选择和其他由子语句组成的语句）通过这些规则由诸如赋值、读、写和跳转语句这样的简单语句组成。这些归纳规则涵盖循环的形成、选择语句及程序块等一系列复合语句。

我们要将一些构建C语言语句的句法规则表述为递归定义。这些规则符合经常出现在C语言教材中的那些定义C语言的语法规则。我们在第11章中还将看到，语法可以用作简洁递归表示法，来指明编程语言句法（syntax）。

更具防御性的程序设计

如果大家只是因为相信示例3.18中的数组A总会存在元素x，就认为它总会存在，那就太天真了。请注意，如果数组中不存在x，图3-10中的循环将最终会出错，因为它要试着访问一个超过数组上限的数组元素。

好在有一种简单的方法可以避免这一错误，而且不会给循环的每次迭代增加很多时间。我们允许数组末尾有第n+1个单元，而在开始循环前，将x 放在该单元中。那么确实能确定x 会出现在数组中的某个位置。当循环结束后，我们会测试是否有i=n。如果是，那么x 并非真正在数组中，我们会穿过数组到达作为哨兵（sentinel）的x 的副本。如果i<n，那么i 就表示x 出现的位置。带有这种保护功能的程序如下所示。

A[n] = x;i = 0;while (x != A[i])
   i++;if (i == n) /* do something appropriate to the case
                      that x is not in the array */else /* do something appropriate to the case
                      that x is found at position i */复制代码

依据。

C语言中的简单语句如下。

1. 表达式。包括赋值语句以及读和写语句，后者是对printf和scanf等函数的调用；

2. 跳转语句。包含goto、break、continue和return；

3. 空语句。

请注意，在C语言中，简单语句都是以分号结尾的，我们要将分号视为这些语句的一部分。

归纳。

以下规则让我们可以用较小的语句来构建语句。

1. while语句。如果S是语句，而C 是条件（带有算术值的表达式），那么

while (C )S

是语句。只要C 为真（具有非0的值），循环体S 就会执行。

2. do-while语句。如果S 是语句，而C 是条件，那么

do S while(C )

是语句。do-while循环和while循环类似，只不过do-while循环的循环体S至少会执行一次。

3. for语句。如果S 是语句，而E1、E2和E3是表达式，那么

for (E1; E2; E3) S

是语句。第一个表达式E1会进行一次评估，并指定循环体S 的初始化。第二个表达式E2是对循环终止的测试，会在每次迭代前进行评估。如果它的值不为0，那么循环体就会执行，否则该for循环就将终止。第三个表达式E3会在每次迭代后进行评估，并为循环的下一次迭代指定重初始化（递增）。例如，如下常见的for循环

for (i = 0; i < n; i++) S

其中S会迭代n 次，对应i 的值分别为1、2、3、…、n-1。在这里，i = 0是初始化，i < n 是终止测试，i++是重初始化。

4. 选择语句。如果S1和S2是语句，而C 是条件，那么

if ( C ) S1 else S2

是语句，而且

if ( C ) S1

也是语句。在第一种情况中，如果C为真（非0），就执行S1，否则就执行S2。在第二种情况中，只有当C 为真，才执行S1。

5. 程序块。如果S1、S1、…、Sn都是语句，那么

{S1 S2…Sn}

也是语句。

我们在上面没有列出开关语句，它形式复杂，但在分析运行时间时可以被当作嵌套的选择语句。

利用上述对语句的递归定义，就可以通过分辨程序的组成部分来解析程序。也就是说，首先有简单的语句，再进一步将这些简单的语句组成更大的复合语句。

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