标题:
算法时间复杂度与程序执行时间计算(3)
[打印本页]
作者:
yuyang911220
时间:
2016-7-16 08:48
标题:
算法时间复杂度与程序执行时间计算(3)
6.2
指令相对变化率
依据定义
1
我们能够计算出指令增速表达式,但是由于在
n
的值变动的情况下,我们仍然不能直接比较出各种形式的表达式指令增速的快慢,为了能够在统一的范围内进行比较,我们引入单位指令重复执行次数下的指令增速,即指令相对变化率的概念。
定义
2
:指令增速与指令重复执行次数的比,称为指令相对变化率。
用μ表示指令相对变化率,即有μ
=
υ
(
n
)/ F(n)
。由指令相对变化率的大小就可以知道,不同类型算法的指令增速对程序执行时间长短的影响程度。
这样,表达式(
2
)的指令相对变化率
μ
=
υ
(
n
)/ F(n)=
nc
/(1c+2c+3c+...+
nc
)
;
表达式(
3
)的指令相对变化率
μ
=
υ
(
n
)/ F(n)= 2
n
/(20+21+22+...+2
n
-1+2
n
)
;
表达式(
4
)的指令相对变化率
μ
=
υ
(
n
)/ F(n)=
n
! /(1!+2!+3!+...+(
n
-1)!+
n
!)
;
表达式(
5
)的指令相对变化率
μ
=
υ
(
n
)/ F(n)=
n
lg
n
/( lg1+2lg2+3lg3+...+(
n-
1)lg(n-1)+
n
lg
n
)
;
表达式(
6
)的指令相对变化率
μ
=
υ
(
n
)/ F(n)=
nn
/(11+22+33+...+(
n
-1)
n
-1+
nn
)
。
在这些公式中只要确定
n
值,就可以求出指令相对变化率。
6.3
算法指令增速
做为一种算法,一般都要研究公式(
1
)中
k
或
n
的全局变化情况。这种变化会随着
k
与
n
的值超大变化带来诸多的未知状况,为此对
k
或
n
向着无穷大方向的变化,就体现了与算法相关的指令执行重复数的整体变化规律。对于一元函数的情况,我们引入算法指令增速的概念。
定义
3
:指令相对变化率的极限称为算法指令增速。
我们希望在
n
较大的时候,通过算法一元函数全局的变化,来寻找算法类型对指令执行重复数的增长规律。如此我们对上面的几种类型指令相对变化率求极限。
表达式(
2
)的算法指令增速为
nc
/(1c+2c+3c+...+(
n
-1)c+
nc
)=0
;
表达式(
3
)的算法指令增速为 lim
2
n
/(20+21+22+...+2
n
-1+2
n
) =
1/(
2-n+2-n+1+...+2-1+1)=1/2
;这是一个等比序列,如果幂底数是常数
c
,那么结果将是
(c-1)/c
。
表达式(
4
)的算法指令增速为 lim
n
! /(1!+2!+3!+...+(
n
-1)!+
n
!)=1
表达式(
5
)的算法指令增速为 lim
n
lg
n
/( lg1+2lg2+3lg3+...+(
n-
1)lg(n-1)+
n
lg
n
)
这个极限是多少?我没能求出,依指令增速判断应该是
0
。请有兴趣的读者帮我补充一下。
表达式(
6
)的算法指令增速为 lim
nn
/(11+22+33+...+(
n
-1)
n
-1+
nn
)=1
(上面各极限n->∞)
由指令增速与指令重复执行次数的定义可知,μ
=
υ
(
n
)/ F(
n
)
是一个
0
与
1
之间的数。因而
0
是最小的算法指令增速,
1
是最大的算法指令增速。由此知从算法全局来看,多项式型算法的指令增速最小,阶乘型或幂指型增速最快,而指数型介于它们之间。
需要说明,算法指令增速是对算法全局的一种属性描述,它并不能够代表算法程序执行的实际时间。这是因为不论何种算法,只要
n
趋向无穷,那么算法程序执行就不会有完结的时候,因而也就无所谓程序执行时间快慢问题了。
算法指令增速很像算法时间复杂度,但算法指令增速是真实依据时间计算获得的概念,就此一点就说明比没有确切定义的算法时间复杂度更加实用。
7.
结论
计算程序执行时间,要通过程序写出的指令重复执行次数进行,指令重复执行次数的多少,取决于程序循环结构的循环次数和循环层数这两个变量。通俗地讲,循环层数和循环次数越大,程序运行得出结果所消耗的时间越长。
任何在计算机上完成任务的程序运行,都需要在有限时间内解决问题,不然我们编写的程序就失去了意义。因而研究程序运行时间的有限性,远比研究程序执行时间的无限性更为重要。但是为了定性地比较算法的效率,我们引入了算法指令增速的概念,作者相信,依据算法指令增速的概念可以推进算法的深入研究
,也或许对
P
与
NP
的讨论会有所帮助。
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)
Powered by Discuz! 7.0.0