【摘要】設(shè)計(jì)高效率的程序是個(gè)重要話題。限于基礎(chǔ)，初學(xué)者往往不得要領(lǐng)。本文試圖較通俗地傳達(dá)算法設(shè)計(jì)和分析中的一些觀點(diǎn)、方法。幫助學(xué)生樹立算法的概念，注重將來算法理論的學(xué)習(xí)。

　　在學(xué)習(xí)了循環(huán)以后，我們可以做程序，解決些大問題了。我想談?wù)勱P(guān)于程序執(zhí)行效率的問題。

　　評價(jià)一個(gè)程序的標(biāo)準(zhǔn)中，第一是正確；第二是可讀性好，以此使程序易于修改和維護(hù)；第三就是效率的問題了，要求程序運(yùn)行要盡可能快，占用內(nèi)存空間要盡可能小。關(guān)注效率，可以使我們的好程序能在“小設(shè)備”上運(yùn)行，這在移動(dòng)計(jì)算、物聯(lián)網(wǎng)時(shí)代很要緊。還有些問題，復(fù)雜得不得了，也只有借助于設(shè)計(jì)高效率算法和程序的能力，才有可能將之解決。

　　以計(jì)算1/2-2/3+3/4-…+19/20的程序?yàn)槔f明。憑借以前的數(shù)學(xué)知識，同學(xué)們會(huì)將式子視為純粹的加法，待加的通項(xiàng)式為(-1)ⁿ×i/(i+1)，可以編出如圖1所示的程序：

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

　　圖1的程序沒有錯(cuò)，但pow求冪運(yùn)算本身是個(gè)復(fù)雜運(yùn)算，應(yīng)該要避免的。尤其在學(xué)習(xí)C語言和C++時(shí)，效率的觀念一定要有。否則i++和i=i+1、i+=2和i=i+2更沒有必要區(qū)別了。

　　更進(jìn)一步來些分析（此處引入了一些算法分析的知識，以后專業(yè)課中要學(xué)，我講得通俗些）。在while循環(huán)中，有加法、乘法、除法等運(yùn)算。乘法需要的運(yùn)行時(shí)間遠(yuǎn)高于加法（理解一下，為什么？m*n是n個(gè)m相加嘛。）。除法和乘法一樣復(fù)雜。所以算法分析中找主要矛盾，忽略加法。為簡單起見，除法我們也不說了，就從乘法次數(shù)上說事。從表面上看，循環(huán)1次執(zhí)行1次乘法，循環(huán)n次，共執(zhí)行了n次乘法。但注意到循環(huán)中pow(-1,i)是需要用乘法實(shí)現(xiàn)的，pow(-1,i)需要執(zhí)行i 次乘法。在n次循環(huán)中，用于計(jì)算pow(-1,i)的乘法次數(shù)分別為1、2、3……n，共計(jì)1+2+…+n=n(n-1)/2。此程序需要的乘法次數(shù)達(dá)n(n-1)/2+n=(n²+n)/2，從數(shù)量級上講，是n²級別的。（當(dāng)n足夠大時(shí)，式子中的常系數(shù)1/2也可以被忽略）。在算法分析中，稱其時(shí)間復(fù)雜度為O(n²)。

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

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

　　圖1的算法很直觀，有人不想放棄這個(gè)算法。是不是可以改進(jìn)pow函數(shù)的算法來做呢？

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

　　直接用循環(huán)構(gòu)造程序，程序段如圖3所示。

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

　　由此可見，圖2的算法比圖1的算法絕對好。無論在圖1的局部做多少努力，大局不可改變。

　　不想費(fèi)腦筋的同學(xué)可以直接看下一段。快速求冪算法的背后是數(shù)論中的一個(gè)結(jié)論（我不知道定理名稱，想知道百度一下即可，實(shí)際上定理叫什么并不重要要了）。這個(gè)結(jié)論是：任何一個(gè)正整數(shù)，都可以表示為一個(gè)偶數(shù)加1或0。多么樸素的結(jié)論。18=18+0，17=16+1。顯然得不得了。繼續(xù)下去，18或者16除以2后，無論是奇數(shù)還是偶數(shù)，也可以用同樣的形式表示。品一品，循環(huán)、迭代的味道出來了。例如：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¹。這不是十進(jìn)制轉(zhuǎn)二進(jìn)制的方法嗎？就這樣用上了。的確，輸入是x=3，n=18，即要計(jì)算時(shí)3¹⁸時(shí)，走查一下，和上式的分解是一樣的。算法的設(shè)計(jì)實(shí)際上就是基于這樣的數(shù)學(xué)知識得來的。數(shù)學(xué)在計(jì)算機(jī)科學(xué)中如此重要，咱就不講大道理了。總之，學(xué)多少數(shù)學(xué)，都不算多，當(dāng)然要學(xué)會(huì)用數(shù)學(xué)知識。

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

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

　　學(xué)習(xí)計(jì)算機(jī)，學(xué)習(xí)用編程的方法解決問題，注重效率是一種基本的品質(zhì)。你將來在算法科學(xué)的領(lǐng)域內(nèi)，會(huì)掌握更多處理問題的典型方法。這是我們要的基本功，是職業(yè)素養(yǎng)的表現(xiàn)。