Flyingis

作者：Flyingis

算法作為實(shí)現(xiàn)計(jì)算機(jī)程序?qū)崿F(xiàn)時(shí)解決問題的方法，在計(jì)算機(jī)應(yīng)用領(lǐng)域發(fā)揮著舉足輕重的作用。它研究的內(nèi)容是解決問題的方法，而不是計(jì)算機(jī)程序的本身。一個(gè)優(yōu)秀的算法可以運(yùn)行在比較慢的計(jì)算機(jī)上，但一個(gè)劣質(zhì)的算法在一臺性能很強(qiáng)的計(jì)算機(jī)上也不一定能滿足應(yīng)用的需要，因此，在計(jì)算機(jī)程序設(shè)計(jì)中，算法設(shè)計(jì)往往處于核心地位。如何去設(shè)計(jì)一個(gè)適合特定應(yīng)用的優(yōu)秀算法是眾多開發(fā)人員所關(guān)注的焦點(diǎn)，在算法設(shè)計(jì)時(shí)，需要了解算法設(shè)計(jì)的規(guī)則。

要想充分理解算法并有效地應(yīng)用于實(shí)際問題，關(guān)鍵是對算法的分析。通常我們可以利用實(shí)驗(yàn)對比分析、數(shù)學(xué)方法來分析算法。實(shí)驗(yàn)對比分析很簡單，兩個(gè)算法相互比較，它們都能解決同一問題，在相同環(huán)境下，哪個(gè)算法的速度快我們一般就會認(rèn)為這個(gè)算法性能更好。數(shù)學(xué)方法能將算法分析的更為細(xì)致，能在嚴(yán)密的邏輯推理基礎(chǔ)上判斷算法的優(yōu)劣，但在完成實(shí)際項(xiàng)目過程中，我們很多時(shí)候都不能去做這種嚴(yán)密的論證與推斷，因?yàn)槲覀儾皇窃谕瓿梢坏罃?shù)學(xué)難題，也不是數(shù)學(xué)領(lǐng)域的專家，將大量的時(shí)間花費(fèi)在公式的計(jì)算與證明上會導(dǎo)致整個(gè)項(xiàng)目進(jìn)度緩慢、成本過高，因此，在算法設(shè)計(jì)中，我們往往采用能近似表達(dá)性能的方法來展示某個(gè)算法的性能指標(biāo)。例如，計(jì)算機(jī)對n²和n²+2n的響應(yīng)速度，當(dāng)n比較大的時(shí)候幾乎一樣沒什么區(qū)別，我們便可直接認(rèn)為后者算法的復(fù)雜度為n²。在分析算法時(shí)，隱藏細(xì)節(jié)的數(shù)學(xué)表示法成為大O記法，它可以幫助我們簡化算法復(fù)雜度的許多細(xì)節(jié)，提取主要成分，這和遙感圖像處理中的主成分分析思想相近。

基于算法復(fù)雜度簡化表達(dá)的思想基礎(chǔ)上，我們通常會對算法進(jìn)行最壞情況分析和平均情況分析。對于一個(gè)給定的算法，如果能保證它的最壞情況下的性能依然不錯(cuò)當(dāng)然很好，但是在某些情況下，程序的最壞情況算法的運(yùn)行時(shí)間和實(shí)際情況的運(yùn)行時(shí)間相差很大，在實(shí)際應(yīng)用中我們幾乎不會碰到最壞情況下的輸入，那么此時(shí)進(jìn)行最壞情況分析顯得有些畫蛇添足，特別是分析最壞情況算法會花費(fèi)大量精力的時(shí)候。算法的平均情況分析可以幫助我們估計(jì)程序的性能，作為算法分析的基本指標(biāo)之一，但是平均情況和實(shí)際情況仍然會有相差很大的時(shí)候，這時(shí)我們便可以使用隨機(jī)法來盡量模擬現(xiàn)實(shí)中的情況，這樣可以得到在嚴(yán)格的概率意義上的預(yù)測運(yùn)行時(shí)間。另外，對于一個(gè)經(jīng)典算法，我們沒有必要再去對該算法進(jìn)行改進(jìn)，研究它的上界和下界，只需要了解該算法的特性，然后在合適的時(shí)候使用它。

最后，當(dāng)一個(gè)程序變快和變慢，讓計(jì)算機(jī)反映出來的時(shí)間差幾乎不會讓人產(chǎn)生感覺的時(shí)候，我們也沒有必要去改進(jìn)這個(gè)算法，例如程序進(jìn)行1000次循環(huán)花費(fèi)0.001秒，改進(jìn)后為0.1秒，在實(shí)際應(yīng)用中通常也只需要幾千次循環(huán)，此時(shí)我們就沒有必要去花時(shí)間來研究這個(gè)算法了，只要該算法能正確完成任務(wù)即可。