【摘要】設計高效率的程序是個重要話題。限于基礎，初學者往往不得要領。本文試圖較通俗地傳達算法設計和分析中的一些觀點、方法。幫助學生樹立算法的概念，注重將來算法理論的學習。

　　在學習了循環以后，我們可以做程序，解決些大問題了。我想談談關于程序執行效率的問題。

　　評價一個程序的標準中，第一是正確；第二是可讀性好，以此使程序易于修改和維護；第三就是效率的問題了，要求程序運行要盡可能快，占用內存空間要盡可能小。關注效率，可以使我們的好程序能在“小設備”上運行，這在移動計算、物聯網時代很要緊。還有些問題，復雜得不得了，也只有借助于設計高效率算法和程序的能力，才有可能將之解決。

　　以計算1/2-2/3+3/4-…+19/20的程序為例說明。憑借以前的數學知識，同學們會將式子視為純粹的加法，待加的通項式為(-1)ⁿ×i/(i+1)，可以編出如圖1所示的程序：

圖1  O(n²)級低效率的程序         

　　圖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=(n²+n)/2，從數量級上講，是n²級別的。（當n足夠大時，式子中的常系數1/2也可以被忽略）。在算法分析中，稱其時間復雜度為O(n²)。

　　有沒有好的辦法？圖2給出了通過迭代變換通項符號的程序。不難發現，需要的乘法次數就是n次，時間復雜度為O(n)。

            圖2  O(n)級高效率的程序

　　圖1的算法很直觀，有人不想放棄這個算法。是不是可以改進pow函數的算法來做呢？

　　下面的問題是：求x的n次冪，即xⁿ=x*x*…*x（共n個）的值。

　　直接用循環構造程序，程序段如圖3所示。

　　還有一種快速求冪算法，如圖4所示。這段程序不分析了，同學們給出x和n值，如求3⁷，走查一遍（一定要自己走查一下），數一數用了幾次循環，感嘆吧。設想n很大，如30或更大，接著感嘆吧。

　　由此可見，圖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×2⁴+0×2³+1×2¹+0×2¹。這不是十進制轉二進制的方法嗎？就這樣用上了。的確，輸入是x=3，n=18，即要計算時3¹⁸時，走查一下，和上式的分解是一樣的。算法的設計實際上就是基于這樣的數學知識得來的。數學在計算機科學中如此重要，咱就不講大道理了。總之，學多少數學，都不算多，當然要學會用數學知識。

　　有些同學會拿出并行計算、高性能計算等說理，講不必這么摳算法的效率，認為當計算硬件和平臺足夠強大時，這樣的思維并不顯得有太大的價值。甚至我親自聆聽過一位著名教授的言論：“我們不需要在算法方面花那么大的精力，利用機群，增加并行度，是一種更直接和簡單的方法。”我們不應該忽視了教授此言之中暗含的前提而就此將教授奚落一番了事。此言有點道理，但事情并非如些。

　　面對一塊巨石，等待一位大力士將之移開是一種辦法。但為什么不找來一根杠桿，用很小的力量將之撬動呢？這里需要的是智慧的力量，體現出的是智慧的美。當這塊巨石足夠大，以至于任何大力士都無法憾動時，我們依靠的只有智慧了。

　　學習計算機，學習用編程的方法解決問題，注重效率是一種基本的品質。你將來在算法科學的領域內，會掌握更多處理問題的典型方法。這是我們要的基本功，是職業素養的表現。