对程序设计初学者谈程序的效率

【摘要】设计高效率的程序是个重要话题。限于基础，初学者往往不得要领。本文试图较通俗地传达算法设计和分析中的一些观点、方法。帮助学生树立算法的概念，注重将来算法理论的学习。 在学习了循环以后，我们可以做程序，解决些大问题了。我想谈谈关于程序执行效率的问题。 评价一个程序的标准中，第一是正确；第二是可读性好，以此使程序易于修改和维护；第三就是效率的问题了，要求程序运行要尽可能快，占用内存

【摘要】设计高效率的程序是个重要话题。限于基础，初学者往往不得要领。本文试图较通俗地传达算法设计和分析中的一些观点、方法。帮助学生树立算法的概念，注重将来算法理论的学习。

在学习了循环以后，我们可以做程序，解决些大问题了。我想谈谈关于程序执行效率的问题。

评价一个程序的标准中，第一是正确；第二是可读性好，以此使程序易于修改和维护；第三就是效率的问题了，要求程序运行要尽可能快，占用内存空间要尽可能小。关注效率，可以使我们的好程序能在“小设备”上运行，这在移动计算、物联网时代很要紧。还有些问题，复杂得不得了，也只有借助于设计高效率算法和程序的能力，才有可能将之解决。

以计算1/2-2/3+3/4-…+19/20的程序为例说明。凭借以前的数学知识，同学们会将式子视为纯粹的加法，待加的通项式为(-1)n×i/(i+1)，可以编出如图1所示的程序：

#include Cmath 

int main()

{int i, sign, n=19;

 double d,k;

 i=1,k=0;

 while(i =n)

 { sign=pow(-1,i);

 d=double(i)/(i+1);

 k=k+sign*d;

 i++;

 cout "k=" k endl;

 return 0;

}

图1  O(n2)级低效率的程序         

 

图1的程序没有错，但pow求幂运算本身是个复杂运算，应该要避免的。尤其在学习C语言和C++时，效率的观念一定要有。否则i++和i=i+1、i+=2和i=i+2更没有必要区别了。

更进一步来些分析（此处引入了一些算法分析的知识，以后专业课中要学，我讲得通俗些）。在while循环中，有加法、乘法、除法等运算。乘法需要的运行时间远高于加法（理解一下，为什么？m*n是n个m相加嘛。）。除法和乘法一样复杂。所以算法分析中找主要矛盾，忽略加法。为简单起见，除法我们也不说了，就从乘法次数上说事。从表面上看，循环1次执行1次乘法，循环n次，共执行了n次乘法。但注意到循环中pow(-1,i)是需要用乘法实现的，pow(-1,i)需要执行i 次乘法。在n次循环中，用于计算pow(-1,i)的乘法次数分别为1、2、3……n，共计1+2+…+n=n(n-1)/2。此程序需要的乘法次数达n(n-1)/2+n=(n2+n)/2，从数量级上讲，是n2级别的。（当n足够大时，式子中的常系数1/2也可以被忽略）。在算法分析中，称其时间复杂度为O(n2)。

有没有好的办法？图2给出了通过迭代变换通项符号的程序。不难发现，需要的乘法次数就是n次，时间复杂度为O(n)。

 

int main()

{int i,sign=1,n=19;

 double d,k;

 i=1,k=0;

 while(i =n)

 { d=double(i)/(i+1);

 k=k+sign*d;

 sign=-sign;

 i++;

 cout "k=" k endl;

 return 0;

}

            图2  O(n)级高效率的程序

  

图1的算法很直观，有人不想放弃这个算法。是不是可以改进pow函数的算法来做呢？

下面的问题是：求x的n次幂，即xn=x*x*…*x（共n个）的值。

直接用循环构造程序，程序段如图3所示。

pow=1;

while(j =n)

 pow=pow*x;

 j++;

}

  图3 直接用循环构造求幂程序             

还有一种快速求幂算法，如图4所示。这段程序不分析了，同学们给出x和n值，如求37，走查一遍（一定要自己走查一下），数一数用了几次循环，感叹吧。设想n很大，如30或更大，接着感叹吧。

pow=1

while (n 0)

 if (n%2 == 1)

 pow=pow * x;

 x = x * x;

 n = n / 2;

}

图4 快速求幂算法

 

由此可见，图2的算法比图1的算法绝对好。无论在图1的局部做多少努力，大局不可改变。

不想费脑筋的同学可以直接看下一段。快速求幂算法的背后是数论中的一个结论（我不知道定理名称，想知道百度一下即可，实际上定理叫什么并不重要要了）。这个结论是：任何一个正整数，都可以表示为一个偶数加1或0。多么朴素的结论。18=18+0，17=16+1。显然得不得了。继续下去，18或者16除以2后，无论是奇数还是偶数，也可以用同样的形式表示。品一品，循环、迭代的味道出来了。例如：18=9*2+0=(4*2+1)*2+0=((2*2+0)*2+1)*2+0，再明确些是18=1×24+0×23+1×21+0×21。这不是十进制转二进制的方法吗？就这样用上了。的确，输入是x=3，n=18，即要计算时318时，走查一下，和上式的分解是一样的。算法的设计实际上就是基于这样的数学知识得来的。数学在计算机科学中如此重要，咱就不讲大道理了。总之，学多少数学，都不算多，当然要学会用数学知识。

有些同学会拿出并行计算、高性能计算等说理，讲不必这么抠算法的效率，认为当计算硬件和平台足够强大时，这样的思维并不显得有太大的价值。甚至我亲自聆听过一位著名教授的言论：“我们不需要在算法方面花那么大的精力，利用机群，增加并行度，是一种更直接和简单的方法。”我们不应该忽视了教授此言之中暗含的前提而就此将教授奚落一番了事。此言有点道理，但事情并非如些。

面对一块巨石，等待一位大力士将之移开是一种办法。但为什么不找来一根杠杆，用很小的力量将之撬动呢？这里需要的是智慧的力量，体现出的是智慧的美。当这块巨石足够大，以至于任何大力士都无法憾动时，我们依靠的只有智慧了。

学习计算机，学习用编程的方法解决问题，注重效率是一种基本的品质。你将来在算法科学的领域内，会掌握更多处理问题的典型方法。这是我们要的基本功，是职业素养的表现。

程序初学者推荐学习的三种热门编程语言 在当前的社会需求中，市场上运用最多的、最为广泛的、最热门的、最常用的编程语言可以大致分为一下三种：C语言、JAVA语言、Python语言。
学习编程照着别人的代码敲进去有效率吗？ 这是很多新手都有的一个困惑：书/视频都看懂了，就是不会自己写。 这也是当初一行学编程时非常困扰的一个问题，之后不会写就对着敲代码
学习汇编语言的15大好处 破解高价商业软件 分析商业软件高价值功能 分析高盈利辅助的变态功能，基址，CALL 分析传播急速的病毒的实现与防护 分析高利润盗号木马的实现与防护 分析所有游戏数据基址与CALL，变态功能等 易语言，VC++，Delphi，vb等开发环境内嵌汇编 分析游戏驱动保护与过保护驱动 分析百万乃至千万用户使用的软件ODAY漏洞 读懂各类需要汇编语言基础的书籍与文章。
贺利坚 烟台大学计算机学院教师，建设系列学习资源，改革教学方法，为IT菜鸟建跑道，让大一的孩子会编程，为迷茫的大学生出主意，一起追求快乐的大学。 著书《逆袭大学：传给IT学子的正能量》，帮助处于迷茫中的大学