时尚美容网站建设,适合中层管理的培训,深圳市住房和建设局工程交易中心,宜昌市水利建设工程协会网站算法效率的度量方法 事后统计方法 事后统计方法#xff1a;这种方法主要是通过设计好的测试程序和数据#xff0c;利用计算机计时器对不同算法编制的程序的运行时间进行比较#xff0c;从而确定算法效率的高低。 但这种方法显然是有很大缺陷的#xff1a; 必须依据算法事先…算法效率的度量方法 事后统计方法 事后统计方法这种方法主要是通过设计好的测试程序和数据利用计算机计时器对不同算法编制的程序的运行时间进行比较从而确定算法效率的高低。 但这种方法显然是有很大缺陷的 必须依据算法事先编制好程序这通常需要花费大量的时间和精力。如果编制出来发现它根本就是很糟糕的算法不是竹篮打水一场空吗时间的比较依赖计算机硬件和软件等环境因素有时会掩盖算法本身的优劣。要知道现在的一台四核处理器的计算机跟当年286、386、486等老爷爷辈的机器相比在处理算法的运算速度上是不能相提并论的而所用的操作系统、编译器、运行框架等软件的不同也可以影响它们的结果就算是同一台机器CPU使用率和内存占用情况不一样也会造成细微的差异。算法的测试数据设计困难并且程序的运行时间往往还与测试数据的规模有很大关系效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序不管用什么算法差异几乎是零。而如果有一百万个随机数字排序那不同算法的差异就非常大了而随机的散乱程度有好有坏会使得算法比较变得不够客观。那么我们为了比较算法到底用多少数据来测试测试多少次才算可以这是很难判断的问题。 基于事后统计方法有这样那样的缺陷我们考虑不予采纳。 事前分析估算方法
我们的计算机前辈们为了对算法的评判更科学研究出了一种叫做事前分析估算的方法。
事前分析估算方法在计算机程序编制前依据统计方法对算法进行估算。 经过分析我们发现一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素 算法采用的策略、方法编译产生的代码质量。问题的输入规模机器执行指令的速度。 1条当然是算法好坏的根本第2条要由软件来支持第4条要看硬件性能。
也就是说抛开这些与计算机硬件、软件有关的因素一个程序的运行时间依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少.
我们来看看今天刚上课时举的例子两种求和的算法;
第一种算法注意for循环最后还要多执行一次条件判断
int i,sum0,n100;//执行1次
for(i1;in;i)//执行n1次
{
sumsumi; //执行n次
}
printf(%d,sum);//执行1次
第二种算法
int sum0,n100;//执行一次
sum(1n)*n/2;//执行一次
printf(%d,sum);//执行一次
显然第一种算法执行了1(n1)n1次2n3次而第二种算法是1113次。
事实上两个算法的第一条和最后一条语句是一样的所以我们关注的代码其实是中间的那部分我们把循环看作一个整体忽略头尾循环判断的开销那么这两个算法其实是n次与1次的差距。算法好坏显而易见。
我们再来延伸一下上面这个例子
int i,j,x0,sum0,n100;//执行一次
for(i1;in;i)
{
for(j1;jn;j)
{
x; //执行n*n次
sumsumx;
}
}
printf(%d,sum);//执行一次
在这个例子中i从1到100每次都要让循环100次而当中的x和sum sumx:其实就是123…10000也就是次所以这个算法当中循环部分的代码整体需要执行n²忽略循环体头尾的开销次。
显然这个算法的执行次数对于同样的输入规模n100要多于前面两种算法这个算法的执行时间随着n的增加也将远远多于前面两个。
此时你会看到测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。
我们不关心编写程序所用的程序设计语言是什么也不关心这些程序将跑在什么样的计算机中我们只关心它所实现的算法。这样不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作最终在分析程序的运行时间时最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
可以从问题描述中得到启示同样问题的输入规模是n求和算法的第一种求12…n需要一段代码运行n次。那么这个问题的输入规模使得操作数量是f(n)n显然运行100次的同一段代码规模是运算10次的10倍。而第二种无论n为多少运行次数都为1即f(n)1第三种运算100次是运算10次的100倍因为它是f(n)n²。
我们在分析一个算法的运行时间时重要的是把基本操作的数量与输入规模关联起来即基本操作的数量必须表示成输入规模的函数如下图所示 我们可以这样认为随着n值的越来越大它们在时间效率上的差异也就越来越大。
好比你们当中有些人每天都在学习我指有用的学习而不是只为考试的死读书每天都在进步而另一些人打打游戏睡睡大觉。入校时大家都一样但毕业时结果可能就大不一样前者名企争抢着要后者求职无门。
函数的渐近增长
我们现在来判断一下以下两个算法A和B哪个更好。假设两个算法的入规模都是n函教值为执行次数算法A要做2n3次操作你可以理解为先有一个n次的循环执行完成后再有一个n次循环最后有三次赋值或运算共2n3次操作。算法B要做3n1次操作。你觉得它们谁更快呢
准确说来答案是不一定的如下表所示。
次数n)算法A(2n3)算法A2(2n)算法B3n1算法B2(3n)15243274763961091023203130100203200301300 当n1时算法A效率不如算法B次数比算法B要多一次。而当n2时两者效率相同当n2时算法A就开始优于算法B了随着n的增加算法A比算法B越来越好了执行的次数比B要少。于是我们可以得出结论算法A总体上要好过算法B。
此时我们给出这样的定义输入规模n在没有限制的情况下只要超过一个数值N,这个函数就总是大于另一个函数我们称函数是渐近增长的。 函数的渐近增长给定两个函数f(n)和g(n)如果存在一个整数N使得对于所有的nNf(n)总是比g(n)大那么我们说f(n)的增长渐近快于g(n) 我们可以从中发现随着n的增大后面的3还是1其实是不影响最终的算法变化的例如算法A2 和算法B2所以我们可以忽略这些加法常数。后面的例子这样的常数被被忽略的意义可能会更加明显。
我们来看第二个例子算法C是4n8算法D是21。
次数n)算法C4n8算法C(n)算法D21算法D2)11213121629432031991048102011001004081002000110000100040081000200000110000000
当n≤3的时候算法C要差于算法D因为算法C次数比较多但当n3后算法C就越来越优于算法D了到后来更是远远胜过。而当后面的常数去掉后我们发现其实结果没有改变。甚至我们再观察发现哪怕去掉与n相乘的常数这样的结果也没有改变算法C2的次数随着n的增长还是远远小于算法D2。
也就是说与最高次项乘的常数并不重要。
我们再来看第三个例子。算法E是2n²3n1算法F是23n1。
次数算法23n1)算法E2)算法F(23n1)算法F2()161612154238328964271023110020311000100203011000020003011000000
当n1的时候算法E与算法F结果相同但当n1后算法E的优势就要开始优于算法F随着n的增大差异越来越明显。通过观察发现高次项的指数大的函数随着n的增长结果也会增长更快。
我们来看最后一个例子。算法G是2n²算法H是3n1算法I是2n²3n1。
次数(n)算法G(2)算法H(3n1)算法I(23n11246287155501666102003123110020000301203011000200000030012003001100002000000003000120003000110000020000000000300001200003000011000000200000000000030000012000003000001
这组数据应该就看得很清楚。当n的值越来越大时你会发现3n1已经没法和2n²的结果相比最终几乎可以忽略不记。也就是说随着n值变得非常大以后算法G其实已经很趋近算法I。 于是我们可以得到这样一个结论判断一个算法的效率时函数中的常数和其他次要项常常可以忽略而更应该关注主项最高阶项的阶数。 判断一个算法好不好我们只通过少量的数据是不能做出准确判断的。
根据刚才的几个样例我们发现如果我们可以对比这几个算法的关键执行次数函数的渐近增长性基本就可以分析出某个算法随着n的增大它会越来越优于另一算法或者越来越差于另一算法。这其实就是事前估算方法的理论依据通过算法时间复杂度来估算算法时间效率。
算法时间复杂度 若某个算法的运行次数函数是T(n)若有某个辅助函数f(n)使当n趋近无穷大时 的值为不等于0的常数则称f(n)为T(n)的同量级函数记作T(n)O(f(n)) 称O(f(n))为算法的渐近时间复杂度简称时间复杂度 这样用大写O( )来体现算法时间复杂度的记法我们称之为大O记法。
一般情况下随着n的增大T(n)增长最慢的算法为最优算法。
显然由此算法时间复杂度的定义可知我们的三个求和算法的时间复杂度分别为O(n)O(1)O(n²。我们分别给它们取了非官方的名称O(1)叫常数阶、O(n叫线性阶、O(n²)叫平方阶当然还有其他的一些阶我们之后会介绍。 推导大O阶方法
那么如何分析一个算法的时间复杂度呢即如何推导大O阶呢我们给出了下面的推导方法基本上这也就是总结前面我们举的例子。 推导大O阶 1用常数数1取代运行时间中的所有加法常数。 2在修改后的运行次数函数中只保留最高阶项 3如果最高阶项存在旦其系数不是1则去除与这个项相乘的系数。 得到的结果就是大O阶。 哈仿佛是得到了游戏攻略一样我们好像已经得到了一个推导算法时间复杂度的万能公式。
可事实上分析一个算法的时间复杂度没有这么简单我们还需要多看几个例子。
我们可以举个例子
就上面的算法H而言T(n)3n1f(n)n容易得到当n趋向无穷时3容易得到算法H的时间复杂度为O(1)
常数阶
首先介绍顺序结构的时间复杂度。
下面这个算法为什么时间复杂度不是O(3)而是O(1)。
int sum0.n100;//执行一次
sum(1n)*n/2;//执行一次
printf(%d,sum);//执行一次
这个算法的运行次数函数是f(n)3。根据我们推导大O阶的方法第一步就是把常数项3改为1。在保留最高阶项时发现它根本没有最高阶项所以这个算法的时间复杂度就是O(1)。
另外我们试想一下如果这个算法当中的语句sum(1n)*n/2有10句即
int sum0,n100;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
sum(1n)*n/2;
printf(%d,sum);
事实上无论n为多少上面的两段代码就是3次和12次执行的差异。这种与问题的大 小n的大小无关执行时间恒定的算法我们称之为具有O(1)的时间复杂度又叫常 数阶。 注意不管这个常数是多少我们都记作0(1)而不能是O(3)、O(12)等其他任何数字这是初学者常常犯的错误。 对于分支结构而言无论是真还是假执行的次数都是恒定的不会随着n的变大而发生变化所以单纯的分支结构不包含在循环结构中其时间复杂度也是0(1)。
线性阶
线性阶的循环结构会复杂很多。
要确定某个算法的阶次我们常常需要确定某个特定语句或某个语句集运行的次数。
因此我们要分析算法的复杂度关键就是要分析循环结构的运行情况。
下面这段代码它的循环的时间复杂度为O(n)因为循环体中的代码需要执行n次。
inti;
for(i 0;i n;i)
{
/*时间复杂度为0(1)的程序步骤序列 */
}
对数阶
下面的这段代码时间复杂度又是多少呢
int count 1;
while(count n)
{
count*2;
/* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后就距离n更近了一分。
也就是说有多少个2相乘后大于n则会退出循环。
由n得到x。所以这个循环的时间复杂度为O(logn。
平方阶
下面例子是一个循环嵌套它的内循环刚才我们已经分析过时间复杂度为O(n)。
int i,j;
for(i0;in;i)
{
for (j 0; j n; j)
{/* 时间复杂度为0(1)的程序步骤序列 */}}
而对于外层的循环不过是内部这个时间复杂度为O(n)的语句再循环n次。所以这段代码的时间复杂度为O(n²。
如果外循环的循环次数改为了m时间复杂度就变为O(mxn)。
int i,j;
for(i0;im;i)
{
for (j 0; j n; j)
{/* 时间复杂度为0(1)的程序步骤序列 */}}
所以我们可以总结得出循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
那么下面这个循环嵌套它的时间复杂度是多少呢
int i,j;
for(i0;ini)
for (j i; jn; j /*注意j i而不是0*/
{
/*时间复杂度为O(1)的程序步骤序列 */
} 由于当i0时内循环执行了n次当i1时执行了n-1次……当in-1时执行了1次。所以总的执行次数为n(n-1)(n-2)……1 用我们推导大O阶的方法 第一条没有加法常数不予考虑 第二条只保留最高阶项因此保留n²/2 第三条去除与这个项相乘的常数也就是去除1/2最终这段代码的时间复杂度为0(n²)。 从这个例子我们也可以得到一个经验其实理解大O阶推导不算难难的是对数列的一些相关运算这更多的是考察你的数学知识和能力。
我们继续看例子对于方法调用的时间复杂度又如何分析。
int i,j;
for(i0;in;i)
{
function(i);
}
上面这段代码调用一个函数function()。
void function (int count)
{
print(count);
}
函数体是打印count这个参数。其实这很好理解function()函数的时间复杂度是O(1)。
所以整体的时间复杂度为O(n。
假如function()是下面这样的
void function (int count)
{
int j;
for(jcount;j n; j)
{
/*时间复杂度为O(1的程序步骤序列*/
}
}
事实上这和刚才举的例子是一样的。只是因为把嵌套内循环放到了函数中所以最终的时间复杂度为O(。
下面这段相对复杂的语句
n;
function(n);
int i,j;
for(i0;in;i)
{function(i);
}for(i0;in;i)
{for(ji;jn;j){printf(hello);}
} 它的执行次数f(n)1nn²根据推导大O阶的方法最终这段代码的时间复杂度也是O(n。
时间复杂度所耗费的时间比较
时间复杂度所耗费的时间比较从小到大依次是 最坏情况与平均情况
你早晨上班出门后突然想起来手机忘记带了这年头钥匙、钱包、手机三大件出门哪件也不能少呀。于是回家找。打开门一看手机就在门口玄关的台子上原来是出门穿鞋时忘记拿了。这当然是比较好基本没花什么时间寻找。可如果不是放在那里你就得进去到处找找完客厅找卧室、找完卧室找厨房、找完厨房找卫生间就是找不到时间一分一秒地过去你突然想起来可以用家里座机打一下手机循着手机铃声来找呀真是笨。终于找到了在床上枕头下面。你再去上班迟到。见鬼这一年的全勤奖就因为找手机给黄了。
找东西有运气好的时候也有怎么也找不到的时候。但在现实中通常我们碰到的 绝大多数既不是最好的也不是最坏的所以算下来是平均情况居多。
算法的分析也是类似我们查找一个有n个随机数字数组中的某个数字最好的情况是第一个数字就是那么算法的时间复杂度为O(1)但也有可能这个数字就在最后一位置上待着那么算法的时间复杂度就是O(n)这是最坏的一种情况了。
最坏情况运行时间是一种保证那就是运行时间不会再坏了。在应用中这是一种最重要的需求。通常除非特别指定我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间也就是从概率的角度看这个数字在每一个位置的可能性是相同的所以平均的查找时间为(n1)/2次后发现这个目标元素。
平均运行时间是所有情况中最有意义的因为它是期望的运行时间。也就是说我们运行一段程序代码时是希望看到平均运行时间的。可现实中平均运行时间很难通过分析得到一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析一种方法是计算所有情况的平均值这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度这种方法称为最坏时间复杂度。
一般在没有特殊说明的情况下都是指最坏时间复杂度。
