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