转自：http://blog.sciencenet.cn/blog-340399-861142.html
5.
程序执行时间比较
关于算法程序时间复杂度，一种流行的观点认为多项式类型的算法复杂度较低，而且认为多项式类型算法程序运行耗时最少。其实在大多数情况下这是一种错觉。
从公式（1）我们知道，决定算法程序执行时间长短的有两个因素，一个是多项式的幂指数k，另一个是多项式的幂底数n。当幂指数k较大的时候，虽然它是一个常数，我们也不能够认为多项式时间类型算法程序运行时间消耗会最少。特别在n<k时，从（1）式立即知道，nk多项式型算法程序时间的消耗会大于幂nn型算法程序的耗时。这说明在较大的循环层数的范围内，不能够就认为多项式时间具有较低的复杂度，当然也不能够认为这种情况的算法程序耗时最短。我们不妨仅就一项来进行比较。例如设n=5，k=7，那么nk=57=78125；而nn=55=3125。由此可见用多项式时间复杂度来说明算法程序耗时长短是不太靠谱的事情。有人也许会说，n趋于无穷才对。想象一下，n趋于无穷大对程序执行的时间计算的意义有多大？
6.
算法指令增速
在前面我们已经指出，程序执行时间要用指令重复执行次数为计算单位。并给出了二元多项式型计算公式。这自然会引出什么样的算法程序耗时较多，什么样的算法程序耗时较少的问题。由于同样的问题或任务可以采用不同形式的算法解决，故而研究不同算法程序执行耗时的多少具有现实意义。
6.1
指令增速
将（1）这个公式进行一元函数变换，即或者固定比较次数，或者固定循环层数，可以得到各种与实际问题有关的一元函数。例如我们用c表示常数，n表示变量，（1）式可以演化出nc、cn、nn、nlogcn等多种类型程序指令重复执行次数的计算公式。不同的类型公式直接与程序执行的耗时有关，因而我们有兴趣去研究，那些能够判定出采用何种类型算法更能够耗时较少的方法。
为了统一且不失一般性，我们让循环各层参与执行的指令都尽可能的少些，比如各层执行的指令只有一个。那么由（1）式可以得到下面一些类型的指令重复次数的一元函数表达式。这个函数我们用F(n)表示。
F(n)=1c+2c+3c+...+nc （2）
F(n)=20+21+22+...+2n-1+2n （3）
F(n)=1!+2!+3!+...+(n-1)!+n! （4）
F(n)= lg1+2lg2+3lg3+...+(n-1)lg(n-1)+nlgn （5）
F(n)=11+22+33+...+(n-1)n-1+nn （6）
这些表达式中的变量n或者表示循环中指令重复执行次数，或者表示程序循环结构的层数，也可以具有两者同步的属性。为了研究各种算法程序执行过程中F(n)的增长快慢，我们引入F(n)的指令增长速度概念。
定义1：F(n)中变量n增加一个单位的指令重复次数增长量，称为指令增速。
由定义可知指令增速是与n有关的函数。将定义1用表达式写出，并用υ(n)来记，则有：υ(n)=F(n) - F(n-1)
于是，表达式（2）的指令n点增速υ(n)= nc；
表达式（3）的指令增速υ(n)=2n；
表达式（4）的指令增速υ(n)=n!；
表达式（5）的指令增速υ(n)= nlgn；
表达式（6）的指令增速υ(n)=nn。
例，n=10，求上列各算法指令增速。
表达式（2）的指令增速是υ(n)=nc=10 c.
表达式（3）的指令增速是υ(n)=2n=210=1024.
表达式（4）的指令增速是υ(n)=n!=10!=3628800.
表达式（5）的指令增速是υ(n)= nlgn=10 lg10=10.
表达式（6）的指令增速是υ(n)=nn=1010=10000000000.
指令增速不是表示算法程序执行时间缩短的指标，而是在算法中指令重复执行的次数增加的快慢指标。如果指令增速较大，则说明在某种程序设计之下指令重复执行的次数增加很快。例如在n=9到n=10的变化中，上面各种算法程序指令增速最快的是幂nn型，指令增速最慢的是nlgn型。所谓的多项式型由指数常量确定，c=1时指令增速最慢，若是c的值超过10，那么在这个地方，会成为指令增速最快的算法形式。因而我们说所谓的O(nk)表示的多项式时间程序执行最快是不靠谱的。
公式（1）的每一种确定的变化形式都代表一种算法。指令增速无疑能够表示在确定的循环次数或循环层数处指令重复执行次数的增长快慢。这自然可以大致描述n值附近的程序执行耗时的变化。例如n=10，我们立即可以计算出由n=9变到n=10的指令增速，从而判定出那种算法在此处耗时增加快慢。 |
