发表日期: 2021-04-10 16:43:35 浏览次数:98
沧州网站制作要多少钱【域名企业邮箱服务器注册申请办理】沧州网络优化公司哪家好、沧州软件开发外包价格、沧州高端企业网站页面制作设计专业公司、沧州微信公众号小程序购物支付搭建制作公司
沧州市,河北省地级市,地处河北省东南部、河北平原东部的黑龙港流域,位于北纬37°29′~38°57′,东经115°42′~117°50′之间。东部滨临渤海,北部与天津、廊坊接壤,西部及西南部与保定、衡水毗邻,南隔漳卫新河与山东省的滨州、德州相望。
沧州市因濒临渤海而得名,市中心北距天津市120千米、北京市240千米,西南距省会石家庄220千米。沧州市辖2个市辖区,4个县级市,10个县及沧州渤海新区、沧州经济开发区、沧州高新技术产业开发区,总面积1.4万平方公里。 [1-3]
2020年10月,入选河北省第一批新型智慧城市建设试点名单。
我们在示例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-8中的第(6)行到第(8)行形成了一个程序块,因为它们永远是连续执行的。由于每一行花的时间都是O(1),所以第(6)行到第(8)行的程序块所花的时间也是O(1)。
请注意,不应该把第(5)行算在程序块中,因为它是第(4)行if
语句的一部分。也就是说,有时候即便不执行第(5)行,第(6)行至第(8)行也会执行。
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-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-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视为某个单变量函数的替代物。
if-else
选择语句具有如下形式:
if(<condition
>)
<if-part
>
else
<else-part
>
其中
1. 条件是待评估的表达式;
2. if
部分的语句只有在条件为真(表达式的值不为0)时才执行;
3. else
部分的语句只有在条件为假(评估为0)时才执行,else
后的<else-part>
是可选的。
只要条件中没有函数调用,不管条件多么复杂,都只需要计算机执行一定量的基本操作。因此,条件评估所花的时间为O(1)。
假设在条件中没有函数调用,而且if
部分和else
部分分别具有大O上界f (n)和g(n)。还假设f (n)和g(n)不会都为0,也就是说,尽管else
部分可能不存在,但if
部分是不会为空的。我们将确定两部分都为空的时候会发生什么留作本节的习题。
如果f (n)是O(g(n)),那么可以将O(g(n))作为选择语句运行时间的上界。原因包括:
1. 可以忽略条件所花的时间O(1);
2. 如果else
部分执行,就可知g(n)是运行时间的边界;
3. 如果if
部分(而不是else
部分)执行,那么运行时间将是O(g(n)),因为f (n)是O(g(n))。
类似地,如果g(n)是O(f (n)),就可以通过O(f (n))确定选择语句运行时间的边界。请注意,当else
部分不存在时(情况也常常是这样),g(n)为0,就肯定是O(f (n))。
当f 和g之间不存在大O关系时,问题出现了。我们知道if
部分或else
部分肯定有一种要执行,但不可能都执行,所以运行时间的安全上界就是f (n)和g(n)中的较大者。正如我们在示例3.10中看到的,二者谁比较大可能取决于n。因此,要将选择语句的运行时间表示为O(max(f (n),g(n)))。
沧州网站制作要多少钱【域名企业邮箱服务器注册申请办理】沧州网络优化公司哪家好、沧州软件开发外包价格、沧州高端企业网站页面制作设计专业公司、沧州微信公众号小程序购物支付搭建制作公司
备案号: 苏ICP备11067224号
CopyRight © 2011 书生商友信息科技 All Right Reserved
24小时服务热线:400-111-6878 E-MAIL:1120768800@qq.com QQ:1120768800
网址: https://www.768800.com 网站建设:上往建站
关键词: 网站建设| 域名邮箱| 服务器空间| 网站推广| 上往建站| 网站制作| 网站设计| 域名注册| 网络营销| 网站维护|
企业邮箱| 虚拟主机| 网络建站| 网站服务| 网页设计| 网店美工设计| 网站定制| 企业建站| 网站设计制作| 网页制作公司|
400电话办理| 书生商友软件| 葬花网| 调温纤维| 海洋馆运营维护| 北京保安公司| 殡仪馆服务| 殡葬服务| 昌平殡葬| 朝阳殡葬|
欢迎您免费咨询,请填写以下信息,我们收到后会尽快与您联系
服务热线:400-111-6878