Posted on 2006-01-22 11:39
Flyingis 閱讀(981)
評論(3) 編輯 收藏 引用 所屬分類:
Algorithm
作者：Flyingis
算法作為實現(xiàn)計算機(jī)程序?qū)崿F(xiàn)時解決問題的方法，在計算機(jī)應(yīng)用領(lǐng)域發(fā)揮著舉足輕重的作用。它研究的內(nèi)容是解決問題的方法，而不是計算機(jī)程序的本身。一個優(yōu)秀的算法可以運(yùn)行在比較慢的計算機(jī)上，但一個劣質(zhì)的算法在一臺性能很強(qiáng)的計算機(jī)上也不一定能滿足應(yīng)用的需要，因此，在計算機(jī)程序設(shè)計中，算法設(shè)計往往處于核心地位。如何去設(shè)計一個適合特定應(yīng)用的優(yōu)秀算法是眾多開發(fā)人員所關(guān)注的焦點(diǎn)，在算法設(shè)計時，需要了解算法設(shè)計的規(guī)則。
要想充分理解算法并有效地應(yīng)用于實際問題，關(guān)鍵是對算法的分析。通常我們可以利用實驗對比分析、數(shù)學(xué)方法來分析算法。實驗對比分析很簡單，兩個算法相互比較，它們都能解決同一問題，在相同環(huán)境下，哪個算法的速度快我們一般就會認(rèn)為這個算法性能更好。數(shù)學(xué)方法能將算法分析的更為細(xì)致，能在嚴(yán)密的邏輯推理基礎(chǔ)上判斷算法的優(yōu)劣，但在完成實際項目過程中，我們很多時候都不能去做這種嚴(yán)密的論證與推斷，因為我們不是在完成一道數(shù)學(xué)難題，也不是數(shù)學(xué)領(lǐng)域的專家，將大量的時間花費(fèi)在公式的計算與證明上會導(dǎo)致整個項目進(jìn)度緩慢、成本過高，因此，在算法設(shè)計中，我們往往采用能近似表達(dá)性能的方法來展示某個算法的性能指標(biāo)。例如，計算機(jī)對n2和n2+2n的響應(yīng)速度，當(dāng)n比較大的時候幾乎一樣沒什么區(qū)別，我們便可直接認(rèn)為后者算法的復(fù)雜度為n2。在分析算法時，隱藏細(xì)節(jié)的數(shù)學(xué)表示法成為大O記法，它可以幫助我們簡化算法復(fù)雜度的許多細(xì)節(jié)，提取主要成分，這和遙感圖像處理中的主成分分析思想相近。
基于算法復(fù)雜度簡化表達(dá)的思想基礎(chǔ)上，我們通常會對算法進(jìn)行最壞情況分析和平均情況分析。對于一個給定的算法，如果能保證它的最壞情況下的性能依然不錯當(dāng)然很好，但是在某些情況下，程序的最壞情況算法的運(yùn)行時間和實際情況的運(yùn)行時間相差很大，在實際應(yīng)用中我們幾乎不會碰到最壞情況下的輸入，那么此時進(jìn)行最壞情況分析顯得有些畫蛇添足，特別是分析最壞情況算法會花費(fèi)大量精力的時候。算法的平均情況分析可以幫助我們估計程序的性能，作為算法分析的基本指標(biāo)之一，但是平均情況和實際情況仍然會有相差很大的時候，這時我們便可以使用隨機(jī)法來盡量模擬現(xiàn)實中的情況，這樣可以得到在嚴(yán)格的概率意義上的預(yù)測運(yùn)行時間。另外，對于一個經(jīng)典算法，我們沒有必要再去對該算法進(jìn)行改進(jìn)，研究它的上界和下界，只需要了解該算法的特性，然后在合適的時候使用它。
最后，當(dāng)一個程序變快和變慢，讓計算機(jī)反映出來的時間差幾乎不會讓人產(chǎn)生感覺的時候，我們也沒有必要去改進(jìn)這個算法，例如程序進(jìn)行1000次循環(huán)花費(fèi)0.001秒，改進(jìn)后為0.1秒，在實際應(yīng)用中通常也只需要幾千次循環(huán)，此時我們就沒有必要去花時間來研究這個算法了，只要該算法能正確完成任務(wù)即可。