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