首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

算法时间复杂度与程序执行时间计算(3)

算法时间复杂度与程序执行时间计算(3)

6.2
指令相对变化率
依据定义1我们能够计算出指令增速表达式,但是由于在n的值变动的情况下,我们仍然不能直接比较出各种形式的表达式指令增速的快慢,为了能够在统一的范围内进行比较,我们引入单位指令重复执行次数下的指令增速,即指令相对变化率的概念。
定义2:指令增速与指令重复执行次数的比,称为指令相对变化率。
用μ表示指令相对变化率,即有μ=υ(n)/ F(n)。由指令相对变化率的大小就可以知道,不同类型算法的指令增速对程序执行时间长短的影响程度。
这样,表达式(2)的指令相对变化率
μ=υ(n)/ F(n)= nc /(1c+2c+3c+...+nc)
表达式(3)的指令相对变化率
μ=υ(n)/ F(n)= 2n /(20+21+22+...+2n-1+2n)
表达式(4)的指令相对变化率
μ=υ(n)/ F(n)= n! /(1!+2!+3!+...+(n-1)!+n!)
表达式(5)的指令相对变化率
μ=υ(n)/ F(n)= nlgn /( lg1+2lg2+3lg3+...+(n-1)lg(n-1)+nlgn)
表达式(6)的指令相对变化率
μ=υ(n)/ F(n)= nn /(11+22+33+...+(n-1)n-1+nn)
在这些公式中只要确定n值,就可以求出指令相对变化率。
6.3
算法指令增速
做为一种算法,一般都要研究公式(1)中kn的全局变化情况。这种变化会随着kn的值超大变化带来诸多的未知状况,为此对kn向着无穷大方向的变化,就体现了与算法相关的指令执行重复数的整体变化规律。对于一元函数的情况,我们引入算法指令增速的概念。
定义3:指令相对变化率的极限称为算法指令增速。
我们希望在n较大的时候,通过算法一元函数全局的变化,来寻找算法类型对指令执行重复数的增长规律。如此我们对上面的几种类型指令相对变化率求极限。
表达式(2)的算法指令增速为
nc /(1c+2c+3c+...+(n-1)c+ nc)=0
表达式(3)的算法指令增速为 lim 2n /(20+21+22+...+2n-1+2n) =1/(2-n+2-n+1+...+2-1+1)=1/2;这是一个等比序列,如果幂底数是常数c,那么结果将是(c-1)/c
表达式(4)的算法指令增速为 limn! /(1!+2!+3!+...+(n-1)!+n!)=1
表达式(5)的算法指令增速为 lim nlgn /( lg1+2lg2+3lg3+...+(n-1)lg(n-1)+nlgn)

这个极限是多少?我没能求出,依指令增速判断应该是0。请有兴趣的读者帮我补充一下。
表达式(6)的算法指令增速为 lim nn /(11+22+33+...+(n-1)n-1+nn)=1
(上面各极限n->∞)
    由指令增速与指令重复执行次数的定义可知,μ=υ(n)/ F(n)是一个01之间的数。因而0是最小的算法指令增速,1是最大的算法指令增速。由此知从算法全局来看,多项式型算法的指令增速最小,阶乘型或幂指型增速最快,而指数型介于它们之间。
需要说明,算法指令增速是对算法全局的一种属性描述,它并不能够代表算法程序执行的实际时间。这是因为不论何种算法,只要n趋向无穷,那么算法程序执行就不会有完结的时候,因而也就无所谓程序执行时间快慢问题了。
算法指令增速很像算法时间复杂度,但算法指令增速是真实依据时间计算获得的概念,就此一点就说明比没有确切定义的算法时间复杂度更加实用。
7.
结论
计算程序执行时间,要通过程序写出的指令重复执行次数进行,指令重复执行次数的多少,取决于程序循环结构的循环次数和循环层数这两个变量。通俗地讲,循环层数和循环次数越大,程序运行得出结果所消耗的时间越长。
任何在计算机上完成任务的程序运行,都需要在有限时间内解决问题,不然我们编写的程序就失去了意义。因而研究程序运行时间的有限性,远比研究程序执行时间的无限性更为重要。但是为了定性地比较算法的效率,我们引入了算法指令增速的概念,作者相信,依据算法指令增速的概念可以推进算法的深入研究,也或许对PNP的讨论会有所帮助。
继承事业,薪火相传
返回列表