算法分析的目的是什么

目的是評(píng)價(jià)算法的效率，通過評(píng)價(jià)可以選用更加好更加適合的算法來完成。

算法分析

算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。 算法(Algorithm)是解題的步驟，可以把算法定義成解一確定類問題的任意一種特殊的方法。在計(jì)算機(jī)科學(xué)中，算法要用計(jì)算機(jī)算法語言描述，算法代表用計(jì)算機(jī)解一類問題的精確、有效的方法。

作用

評(píng)價(jià)算法的好壞

算法是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算，是對(duì)解題方案內(nèi)的準(zhǔn)確與完整地描述。制定一個(gè)算法，一般要經(jīng)過設(shè)計(jì)、確認(rèn)、分析、編碼、測(cè)試、調(diào)試、計(jì)時(shí)等階段。

算法+數(shù)據(jù)結(jié)構(gòu)=程序，求解一個(gè)給定的可計(jì)算或可解的問題，不同的人可以編寫出不同的程序，來解決同一個(gè)問題，這里存在兩個(gè)問題：一是與計(jì)算方法密切相關(guān)的算法問題;二是程序設(shè)計(jì)的技術(shù)問題。算法和程序之間存在密切的關(guān)系。分析算法可以預(yù)測(cè)這一算法適合在什么樣的環(huán)境中有效地運(yùn)行，對(duì)解決同一問題的不同算法的有效性作出比較。

通常對(duì)于一個(gè)實(shí)際問題的解決，可以提出若干個(gè)算法，如何從這些可行的算法中找出最有效的算法呢?或者有了一個(gè)解決實(shí)際問題的算法后，如何來評(píng)價(jià)它的好壞呢?這些問題都需要通過算法分析來確定。評(píng)價(jià)算法分析性能的標(biāo)準(zhǔn)主要從算法執(zhí)行時(shí)間和占用存儲(chǔ)空間兩個(gè)方面進(jìn)行考慮，即通過分析算法執(zhí)行所需要的時(shí)間和存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。

時(shí)間復(fù)雜度

一個(gè)程序的時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。

影響因素

一個(gè)算法是由控制結(jié)構(gòu)(順序、分支和循環(huán)3種)和原操作(指固定數(shù)據(jù)類型的操作)構(gòu)成的，其執(zhí)行時(shí)間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對(duì)于所研究的問題來說基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般情況下，算法中原操作重復(fù)執(zhí)行次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)。許多時(shí)候要精確的計(jì)算T(n)是困難的，引入漸進(jìn)時(shí)間復(fù)雜度在數(shù)量上估計(jì)一個(gè)算法的執(zhí)行時(shí)間，也能夠達(dá)到分析算法的目的。

計(jì)算方法

計(jì)算時(shí)間復(fù)雜度的時(shí)候，主要考慮算法中最高階項(xiàng)的開銷，只要找出算法中最高階的復(fù)雜度，就可以忽略低階和常數(shù)的復(fù)雜度。

當(dāng)要計(jì)算某個(gè)算法的時(shí)間復(fù)雜度F(n)時(shí)，可以找一個(gè)更簡(jiǎn)單的、階數(shù)相同的簡(jiǎn)單算法g(n)等同計(jì)算，這里的g(n)是指替代函數(shù)，它具有和原算法一樣更高階復(fù)雜度。

常見的漸進(jìn)時(shí)間復(fù)雜度

通常用O(1)表示常數(shù)計(jì)算時(shí)間。常見的漸進(jìn)時(shí)間復(fù)雜度有：

規(guī)則

為了便于估算一個(gè)算法的時(shí)間復(fù)雜度，我們約定一下幾條可操作的規(guī)則：

(1)讀寫單個(gè)常量或單個(gè)變量、賦值、算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算等，計(jì)為一個(gè)單位時(shí)間。

(2)條件語句if(C){s}，執(zhí)行時(shí)間為(條件C的執(zhí)行時(shí)間)+(語句塊s的執(zhí)行時(shí)間)。

(3)條件語句if(C)s1 else s2，執(zhí)行時(shí)間為(條件C的執(zhí)行時(shí)間)+(語句塊s1和s2中執(zhí)行時(shí)間最長(zhǎng)的那個(gè)時(shí)間)。

(4)switch...case語句的執(zhí)行時(shí)間是所有case子句中，執(zhí)行時(shí)間最長(zhǎng)的語句塊。

(5)訪問一個(gè)數(shù)據(jù)的單個(gè)元素或一個(gè)結(jié)構(gòu)體變量的單個(gè)元素只需要一個(gè)單位時(shí)間。

(6)執(zhí)行一個(gè)for循環(huán)語句需要的時(shí)間等于執(zhí)行該循環(huán)體所需要時(shí)間乘上循環(huán)次數(shù)。

(7)執(zhí)行一個(gè)while(C){s}循環(huán)語句或者執(zhí)行一個(gè)do{s} while(C)語句，需要的時(shí)間等于計(jì)算條件表達(dá)式C的時(shí)間與執(zhí)行循環(huán)s的時(shí)間之和再乘以循環(huán)的次數(shù)。

(8)對(duì)于嵌套結(jié)構(gòu)，算法的時(shí)間復(fù)雜度由嵌套最深層語句的執(zhí)行次數(shù)決定的。

(9)對(duì)于函數(shù)調(diào)用語句，它們需要的時(shí)間包括兩部分，一部分用于實(shí)現(xiàn)控制轉(zhuǎn)移，另一部分用于執(zhí)行函數(shù)本身。