第二章-算法分析基礎(chǔ)

算法分析的任務(wù):對設(shè)計出的每一個具體的算法,利用數(shù)學(xué)工具，探討其困難度。2.1算法分析體系及計量對算法的評價有兩個大的方面：一.對算法的維護(hù)的便利性。二.算法在實現(xiàn)運行時占有的機(jī)器資源的多少,即算法的運行的時間和空間效率。2.1.1算法分析的評價體系

對算法的分析和評價，一般應(yīng)考慮正確性、可維護(hù)性、可讀性、運算量及占用存儲空間等諸多因素。其中評價算法的三條主要標(biāo)準(zhǔn)是：(1)算法實現(xiàn)所耗費的時間；(2)算法實現(xiàn)所所耗費的存儲空間，其中主要考慮協(xié)助存儲空間；(3)算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。1.和算法執(zhí)行時間相關(guān)的因素：1）問題中數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)2）算法接受的數(shù)學(xué)模型3）算法設(shè)計的策略

4）問題的規(guī)模

5）實現(xiàn)算法的程序設(shè)計語言

6）編譯算法產(chǎn)生的機(jī)器代碼的質(zhì)量

7）計算機(jī)執(zhí)行指令的速度

2.1.2算法的時間困難性

2．算法效率的衡量方法通常有兩種衡量算法效率的方法:1）事后統(tǒng)計法（有缺點，較少運用）2）事前分析估算法算法的時間效率是問題規(guī)模的函數(shù)。假如,隨著問題規(guī)模n的增長,算法執(zhí)行時間的增長率和f(n)的增長率相同,則可記作:T(n)=Ο(f(n))稱T(n)為算法的漸近時間困難度(AsymptoticTimeComplexity),簡稱時間困難度。Ο是數(shù)量級的符號。3．時間困難度估算因為：算法=限制結(jié)構(gòu)+原操作(固有數(shù)據(jù)類型的操作)所以：算法的執(zhí)行時間=原操作的執(zhí)行次數(shù)*原操作的執(zhí)行時間語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。一個算法轉(zhuǎn)換為算法后所耗費的時間,除了與所用的計算軟、硬件環(huán)境有關(guān)外，主要取決于算法中指令重復(fù)執(zhí)行的次數(shù)，即語句的頻度相關(guān)。一個算法中全部語句的頻度之和構(gòu)成了該算法的運行時間。例如：for(j=1;j<=n;++j)for(k=1;k<=n;++k)++x；

語句“++x、k<=n、++k”的頻度是n2，語句“j=1、k=1”的頻度是1，語句“j<=n;++j”的頻度是n。算法運行時間為：3*n2+2n+2。

常常從算法中選取一種對于所探討的問題來說是基本(或者說是主要)的原操作,以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運行時間的衡量準(zhǔn)則。這個原操作,多數(shù)狀況下是最深層次循環(huán)體內(nèi)的語句中的原操作。例如：for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=0;k<=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j];}該算法的基本操作是乘法操作,時間困難度為n3。

例:n2+n+1的時間困難度?解:與n2的數(shù)量級相等(該表達(dá)式當(dāng)n足夠大時約等于n2),這個算法的時間困難度為：T(n)=O(n2)。數(shù)量級相等是這樣定義的,設(shè)f(n)是一個關(guān)于正整數(shù)n的函數(shù),若存在一個常數(shù)C，使則稱f(n)與g(n)是同數(shù)量級的函數(shù)。

上節(jié)下節(jié)算法(漸進(jìn))時間困難度,一般均表示為以下幾種數(shù)量級的形式(n為問題的規(guī)模,c為一常量)：Ο(1)稱為常數(shù)級Ο(logn)稱為對數(shù)級Ο(n)稱為線性級Ο(nc)稱為多項式級Ο(cn)稱此為指數(shù)級Ο(n!)稱為階乘級上節(jié)下節(jié)以上時間困難度級別是由低到高排列的,其隨規(guī)模n的增長率，由圖2-1可見一斑：圖2-1T(n)與規(guī)模n的函數(shù)關(guān)系原則上一個算法的時間困難度,最好不要接受指數(shù)級和階乘級的算法,而應(yīng)盡可能選用多項式級或線性級等時間困難度級別較小的算法。對于較困難的算法，可將它分隔成簡潔估算的幾個部分，然后再利用“O"的求和原則得到整個算法的時間困難度。例：若算法的兩個部分的時間困難度分別為T1(n)=O(f(n))和T2(n)=O(g(n))，則總的時間困難度為：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)))。

4．問題時間困難度的上界和下界略5.算法時間困難度的最好狀況和最壞狀況

我們要確定能反映出算法在各種狀況下工作的數(shù)據(jù)集,選取的數(shù)據(jù)要能夠反映、代表各種計算狀況下的估算,包括最好狀況下的時間困難度(Tmax)最壞狀況下的時間困難度(Tmin)平均狀況下的時間困難度(Tavg)最有實際價值的,是最壞狀況下的時間困難性。算法的存儲量包括：

1)輸入數(shù)據(jù)所占空間:取決于問題本身,與算法無關(guān)2)算法本身所占空間:相對固定3)協(xié)助變量所占空間2.1.3算法的空間困難性

探討算法的空間效率，只須要分析除輸入和算法之外的額外空間。若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作,否則,它應(yīng)當(dāng)是規(guī)模的一個函數(shù)。算法的空間困難度是指算法在執(zhí)行過程中所占協(xié)助存儲空間的大小用S(n)表示。算法的空間困難度S(n)也可表示為:S(n)=Ο(g(n))表示隨著問題規(guī)模n的增大,算法運行所需存儲量的增長率與g(n)的增長率相同。

NP完全性問題:屬于“計算困難性”探討的課題。計算困難性:就是用計算機(jī)求解問題的難易程度。度量標(biāo)準(zhǔn)：一.計算所需的步數(shù)或指令條數(shù)(這叫時間困難度)。二.計算所需的存儲單元數(shù)量(這叫空間困難度)。上節(jié)下節(jié)2.1.4NP完全問題

問題的困難性和算法的困難性的區(qū)分：只就時間困難性說，算法的困難性是指解決問題的一個具體的算法的執(zhí)行時間，這是算法的性質(zhì)；問題的困難性是指這個問題本身的困難程度。P類問題:就是全部困難度為多項式時間的問題的集合(易解的問題類,否則犯難解的問題)。例如:梵塔問題推銷員旅行問題等NP問題:至今沒有找到多項式時間算法解的一類問題,可以在多項式時間內(nèi)驗證一個解是否正確的問題,亦稱為易驗證問題類。

NP完全問題(NPC問題,C代表complete):從NP類的問題中分出困難性最高的一個子類。假如一個NPC問題存在多項式時間的算法，則全部的NP問題都可以在多項式時間內(nèi)求解，即P=NP成立!!要么每個NP完全問題都存在多項式時間的算法（即通常所指的有效算法）；要么全部NP完全問題都不存在多項式時間的算法。目前已知的NP完全問題就有2000多個,其中有很多是特別重要的問題,如:貨郎問題、最大獨立集問題、背包問題、裝箱問題、…等等。

遇到這類問題時，通常從以下幾個方面來考慮并尋求解決方法:1)特殊情形特殊方法2)動態(tài)規(guī)劃和分枝限界方法3)概率分析4)近似算法5)啟發(fā)式算法上節(jié)下節(jié)一具體算法的時間困難度和空間困難度往往是不獨立的，在算法設(shè)計中要在時間效率和空間效率之間折衷。

2.2算法分析實例

1．僅依靠于問題規(guī)模的時間困難度有一類簡潔的問題，其操作具有普遍性，也就是說對全部的數(shù)據(jù)均等價地進(jìn)行處理，這類算法的時間困難度，很簡潔分析。

2.2.1非遞歸算法分析【例1】交換i和j的內(nèi)容。Temp=i；i=j；j=temp；以上三條單個語句的頻度均為1，該算法段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間困難度為常數(shù)階，記作T(n)=Ο(1)。假如算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句,其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間困難度是Ο(1)。上節(jié)下節(jié)【例2】循環(huán)次數(shù)干脆依靠規(guī)模n(1)x=0；=0；(2)for(k-1；<=n；++)(3)x++；(4)for(i=1；<=n；++)(5)for(j=1；j<=n；++)(6)y++；T(n)=Ο(n2)。當(dāng)有若干個循環(huán)語句時，算法的時間困難度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)確定的。上節(jié)下節(jié)y++【例3】循環(huán)次數(shù)間接依靠規(guī)模n(1)x=1；(2)for(i=1；i<=n；i++)(3)for(j=1；j<=i；j++)(4)for(k=1；k<=j；k++)(5)x++；該算法段中頻度最大的語句是(5)，從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：則該算法段的時間困難度為：T(n)=O(n3/6+低次項)=O(n3)。2.算法的時間困難度還與輸入實例的初始狀態(tài)有關(guān)。

這類算法的時間困難度的分析比較困難，一般分最好狀況（處理最少的狀況),最壞狀況(處理最多的狀況)和平均狀況分別進(jìn)行探討?！纠?】【例4】在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下：(1)i=n-1；(2)while(i>=0andA[i]<>k)(3)i=i-1；(4)returni；

此算法的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值及k的取值有關(guān)：1.若A中沒有與k相等的元素，則語句(2)的頻度f(n)=n；這是最壞狀況。2.若A的最終一個元素等于k,則語句(2)的頻度f(n)是常數(shù)1;這是最好狀況。在求平均狀況時，一般地假設(shè)查找不同元素的概率P是相同的,則算法的平均困難度為：若對于查找不同元素的概率P不相同時，其算法困難度就只能做近似分析，或在構(gòu)造更好的算法或存儲結(jié)構(gòu)后，做較精確的分析。上節(jié)下節(jié)2.2.2遞歸算法分析

【例1】求N！構(gòu)造算法中的兩個步驟：1）N!=N*(N-1)！2）0!=1，1!=1。

遞歸算法如下：

以n=3為例,調(diào)用過程如下：fact(3)-fact(2)-fact(1)-fact(2)-fact(3)遞歸回溯迭代法介紹：用迭代方法估計遞歸算法的解,就是充分利用遞歸算法中的遞歸關(guān)系,通過確定的代數(shù)運算和數(shù)學(xué)分析的級數(shù)學(xué)問,得到問題的困難度。遞歸方程具體就是利用遞歸算法中的遞歸關(guān)系寫出遞歸方程,迭代地綻開的右端，使之成為一個非遞歸的和式,然后通過對和式的估計來達(dá)到對方程左端即方程的解的估計。上節(jié)下節(jié)

【例1】求n!遞歸方程為：T(n)=T(n-1)+O(1)其中O(1)為一次乘法操作.

迭代求解過程如下：T(n)=T(n-2)+O(1)+O(1)=T(n-3)+O(1)+O(1)+O(1)……=O(1)+……+O(1)+O(1)+O(1)=n*O(1)=O(n)

【例2】抽象地考慮以下困難一點的遞歸方程，且假設(shè)n=2k，則迭代求解過程如下：=O(n)

一般地，當(dāng)遞歸方程為：T（n）=aT（n/c）+O(n)，T（n）的解為：①O(n)a<c且c>1時②O(nlogcn)a=c且c>1時③O(nlogca)a>c且c>1時在滿足正確性、牢靠性、健壯性、可讀性等質(zhì)量因素的前下，設(shè)法提高算法的效率?？磧山M操作：(1)a=a+b；b=a-b；a=a-b；(2)t=a；a=b；b=t；

2.2.3提高算法質(zhì)量兩組操作的功能都是：“交換變量a、b中的數(shù)據(jù)”。雖然第一組操作節(jié)約了一個存儲空間，但失去了可讀性，是不行取的。下面給出一些原則上的建議：