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

第二章算法分析基礎(chǔ)第1頁，課件共40頁，創(chuàng)作于2023年2月算法分析的任務(wù):對設(shè)計(jì)出的每一個(gè)具體的算法,利用數(shù)學(xué)工具，討論其復(fù)雜度。2.1算法分析體系及計(jì)量第2頁，課件共40頁，創(chuàng)作于2023年2月對算法的評價(jià)有兩個(gè)大的方面：一.對算法的維護(hù)的方便性。二.算法在實(shí)現(xiàn)運(yùn)行時(shí)占有的機(jī)器資源的多少,即算法的運(yùn)行的時(shí)間和空間效率。2.1.1算法分析的評價(jià)體系第3頁，課件共40頁，創(chuàng)作于2023年2月

對算法的分析和評價(jià)，一般應(yīng)考慮正確性、可維護(hù)性、可讀性、運(yùn)算量及占用存儲空間等諸多因素。其中評價(jià)算法的三條主要標(biāo)準(zhǔn)是：(1)算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間；(2)算法實(shí)現(xiàn)所所耗費(fèi)的存儲空間，其中主要考慮輔助存儲空間；(3)算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。第4頁，課件共40頁，創(chuàng)作于2023年2月

1.和算法執(zhí)行時(shí)間相關(guān)的因素：

1）問題中數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)2）算法采用的數(shù)學(xué)模型

3）算法設(shè)計(jì)的策略

4）問題的規(guī)模

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

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

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

2.1.2算法的時(shí)間復(fù)雜性

第5頁，課件共40頁，創(chuàng)作于2023年2月2．算法效率的衡量方法

通常有兩種衡量算法效率的方法:1）事后統(tǒng)計(jì)法（有缺點(diǎn)，較少使用）2）事前分析估算法算法的時(shí)間效率是問題規(guī)模的函數(shù)。假如,隨著問題規(guī)模n的增長,算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同,則可記作:T(n)=Ο(f(n))稱T(n)為算法的漸近時(shí)間復(fù)雜度(AsymptoticTimeComplexity),簡稱時(shí)間復(fù)雜度。Ο是數(shù)量級的符號。第6頁，課件共40頁，創(chuàng)作于2023年2月3．時(shí)間復(fù)雜度估算因?yàn)椋?/p>

算法=控制結(jié)構(gòu)+原操作(固有數(shù)據(jù)類型的操作)

所以：

算法的執(zhí)行時(shí)間=原操作的執(zhí)行次數(shù)*原操作的執(zhí)行時(shí)間

語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。

一個(gè)算法轉(zhuǎn)換為算法后所耗費(fèi)的時(shí)間,除了與所用的計(jì)算軟、硬件環(huán)境有關(guān)外，主要取決于算法中指令重復(fù)執(zhí)行的次數(shù)，即語句的頻度相關(guān)。第7頁，課件共40頁，創(chuàng)作于2023年2月一個(gè)算法中所有語句的頻度之和構(gòu)成了該算法的運(yùn)行時(shí)間。例如：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。算法運(yùn)行時(shí)間為：3*n2+2n+2。

第8頁，課件共40頁，創(chuàng)作于2023年2月

經(jīng)常從算法中選取一種對于所研究的問題來說是基本(或者說是主要)的原操作,以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。這個(gè)原操作,多數(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];}該算法的基本操作是乘法操作,時(shí)間復(fù)雜度為n3。

第9頁，課件共40頁，創(chuàng)作于2023年2月例:n2+n+1的時(shí)間復(fù)雜度?解:與n2的數(shù)量級相等(該表達(dá)式當(dāng)n足夠大時(shí)約等于n2),這個(gè)算法的時(shí)間復(fù)雜度為：T(n)=O(n2)。

數(shù)量級相等是這樣定義的,設(shè)f(n)是一個(gè)關(guān)于正整數(shù)n的函數(shù),若存在一個(gè)常數(shù)C，使則稱f(n)與g(n)是同數(shù)量級的函數(shù)。

上節(jié)下節(jié)第10頁，課件共40頁，創(chuàng)作于2023年2月算法(漸進(jìn))時(shí)間復(fù)雜度,一般均表示為以下幾種數(shù)量級的形式(n為問題的規(guī)模,c為一常量)：

Ο(1)稱為常數(shù)級Ο(logn)稱為對數(shù)級Ο(n)稱為線性級Ο(nc)稱為多項(xiàng)式級Ο(cn)稱此為指數(shù)級Ο(n!)稱為階乘級

上節(jié)下節(jié)第11頁，課件共40頁，創(chuàng)作于2023年2月以上時(shí)間復(fù)雜度級別是由低到高排列的,其隨規(guī)模n的增長率，由圖2-1可見一斑：圖2-1T(n)與規(guī)模n的函數(shù)關(guān)系第12頁，課件共40頁，創(chuàng)作于2023年2月原則上一個(gè)算法的時(shí)間復(fù)雜度,最好不要采用指數(shù)級和階乘級的算法,而應(yīng)盡可能選用多項(xiàng)式級或線性級等時(shí)間復(fù)雜度級別較小的算法。對于較復(fù)雜的算法，可將它分隔成容易估算的幾個(gè)部分，然后再利用“O"的求和原則得到整個(gè)算法的時(shí)間復(fù)雜度。例：若算法的兩個(gè)部分的時(shí)間復(fù)雜度分別為T1(n)=O(f(n))和T2(n)=O(g(n))，則總的時(shí)間復(fù)雜度為：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)))。

第13頁，課件共40頁，創(chuàng)作于2023年2月4．問題時(shí)間復(fù)雜度的上界和下界略第14頁，課件共40頁，創(chuàng)作于2023年2月5.算法時(shí)間復(fù)雜度的最好情況和最壞情況

我們要確定能反映出算法在各種情況下工作的數(shù)據(jù)集,選取的數(shù)據(jù)要能夠反映、代表各種計(jì)算情況下的估算,包括最好情況下的時(shí)間復(fù)雜度(Tmax)最壞情況下的時(shí)間復(fù)雜度(Tmin)平均情況下的時(shí)間復(fù)雜度(Tavg)最有實(shí)際價(jià)值的,是最壞情況下的時(shí)間復(fù)雜性。第15頁，課件共40頁，創(chuàng)作于2023年2月算法的存儲量包括：

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

第16頁，課件共40頁，創(chuàng)作于2023年2月研究算法的空間效率，只需要分析除輸入和算法之外的額外空間。若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作,否則,它應(yīng)當(dāng)是規(guī)模的一個(gè)函數(shù)。

算法的空間復(fù)雜度是指算法在執(zhí)行過程中所占輔助存儲空間的大小用S(n)表示。算法的空間復(fù)雜度S(n)也可表示為:S(n)=Ο(g(n))表示隨著問題規(guī)模n的增大,算法運(yùn)行所需存儲量的增長率與g(n)的增長率相同。

第17頁，課件共40頁，創(chuàng)作于2023年2月NP完全性問題:屬于“計(jì)算復(fù)雜性”研究的課題。計(jì)算復(fù)雜性:就是用計(jì)算機(jī)求解問題的難易程度。度量標(biāo)準(zhǔn)：一.計(jì)算所需的步數(shù)或指令條數(shù)(這叫時(shí)間復(fù)雜度)。二.計(jì)算所需的存儲單元數(shù)量(這叫空間復(fù)雜度)。

上節(jié)下節(jié)2.1.4NP完全問題

第18頁，課件共40頁，創(chuàng)作于2023年2月問題的復(fù)雜性和算法的復(fù)雜性的區(qū)別：只就時(shí)間復(fù)雜性說，算法的復(fù)雜性是指解決問題的一個(gè)具體的算法的執(zhí)行時(shí)間，這是算法的性質(zhì)；問題的復(fù)雜性是指這個(gè)問題本身的復(fù)雜程度。P類問題:就是所有復(fù)雜度為多項(xiàng)式時(shí)間的問題的集合(易解的問題類,否則為難解的問題)。例如:梵塔問題推銷員旅行問題等第19頁，課件共40頁，創(chuàng)作于2023年2月NP問題:至今沒有找到多項(xiàng)式時(shí)間算法解的一類問題,可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問題,亦稱為易驗(yàn)證問題類。

NP完全問題(NPC問題,C代表complete):從NP類的問題中分出復(fù)雜性最高的一個(gè)子類。如果一個(gè)NPC問題存在多項(xiàng)式時(shí)間的算法，則所有的NP問題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P=NP成立!!要么每個(gè)NP完全問題都存在多項(xiàng)式時(shí)間的算法（即通常所指的有效算法）；要么所有NP完全問題都不存在多項(xiàng)式時(shí)間的算法。第20頁，課件共40頁，創(chuàng)作于2023年2月目前已知的NP完全問題就有2000多個(gè),其中有許多是非常重要的問題,如:貨郎問題、最大獨(dú)立集問題、背包問題、裝箱問題、…等等。

第21頁，課件共40頁，創(chuàng)作于2023年2月遇到這類問題時(shí)，通常從以下幾個(gè)方面來考慮并尋求解決辦法:1)特殊情形特殊方法2)動態(tài)規(guī)劃和分枝限界方法3)概率分析4)近似算法5)啟發(fā)式算法

上節(jié)下節(jié)第22頁，課件共40頁，創(chuàng)作于2023年2月

一具體算法的時(shí)間復(fù)雜度和空間復(fù)雜度往往是不獨(dú)立的，在算法設(shè)計(jì)中要在時(shí)間效率和空間效率之間折衷。

2.2算法分析實(shí)例第23頁，課件共40頁，創(chuàng)作于2023年2月

1．僅依賴于問題規(guī)模的時(shí)間復(fù)雜度有一類簡單的問題，其操作具有普遍性，也就是說對所有的數(shù)據(jù)均等價(jià)地進(jìn)行處理，這類算法的時(shí)間復(fù)雜度，很容易分析。

2.2.1非遞歸算法分析第24頁，課件共40頁，創(chuàng)作于2023年2月【例1】交換i和j的內(nèi)容。Temp=i；i=j；j=temp；以上三條單個(gè)語句的頻度均為1，該算法段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=Ο(1)。

如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句,其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是Ο(1)。

上節(jié)下節(jié)第25頁，課件共40頁，創(chuàng)作于2023年2月【例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)有若干個(gè)循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。

上節(jié)下節(jié)y++第26頁，課件共40頁，創(chuàng)作于2023年2月【例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ù)：則該算法段的時(shí)間復(fù)雜度為：T(n)=O(n3/6+低次項(xiàng))=O(n3)。第27頁，課件共40頁，創(chuàng)作于2023年2月2.算法的時(shí)間復(fù)雜度還與輸入實(shí)例的初始狀態(tài)有關(guān)。

這類算法的時(shí)間復(fù)雜度的分析比較復(fù)雜，一般分最好情況（處理最少的情況),最壞情況(處理最多的情況)和平均情況分別進(jìn)行討論。

【例4】第28頁，課件共40頁，創(chuàng)作于2023年2月【例4】在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下：(1)i=n-1；(2)while(i>=0andA[i]<>k)(3)i=i-1；(4)returni；

第29頁，課件共40頁，創(chuàng)作于2023年2月

此算法的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及k的取值有關(guān)：

1.若A中沒有與k相等的元素，則語句(2)的頻度f(n)=n；這是最壞情況。2.若A的最后一個(gè)元素等于k,則語句(2)的頻度f(n)是常數(shù)1;這是最好情況。第30頁，課件共40頁，創(chuàng)作于2023年2月在求平均情況時(shí)，一般地假設(shè)查找不同元素的概率P是相同的,則算法的平均復(fù)雜度為：

若對于查找不同元素的概率P不相同時(shí)，其算法復(fù)雜度就只能做近似分析，或在構(gòu)造更好的算法或存儲結(jié)構(gòu)后，做較準(zhǔn)確的分析。

上節(jié)下節(jié)第31頁，課件共40頁，創(chuàng)作于2023年2月2.2.2遞歸算法分析

第32頁，課件共40頁，創(chuàng)作于2023年2月【例1】求N！構(gòu)造算法中的兩個(gè)步驟：1）N!=N*(N-1)！2）0!=1，1!=1。

遞歸算法如下：

以n=3為例,調(diào)用過程如下：fact(3)-fact(2)-fact(1)-fact(2)-fact(3)遞歸回溯第33頁，課件共40頁，創(chuàng)作于2023年2月迭代法介紹：

用迭代方法估計(jì)遞歸算法的解,就是充分利用遞歸算法中的遞歸關(guān)系,通過一定的代數(shù)運(yùn)算和數(shù)學(xué)分析的級數(shù)知識,得到問題的復(fù)雜度。

遞歸方程具體就是利用遞歸算法中的遞歸關(guān)系寫出遞歸方程,迭代地展開的右端，使之成為一個(gè)非遞歸的和式,然后通過對和式的估計(jì)來達(dá)到對方程左端即方程的解的估計(jì)。

上節(jié)下節(jié)第34頁，課件共40頁，創(chuàng)作于2023年2月

【例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)

第35頁，課件共40頁，創(chuàng)作于2023年2月【例2】抽象地考慮以下復(fù)雜一點(diǎn)的遞歸方程，且假設(shè)n=2k，則迭代求解過程如下：

=O(n)

第36頁，課件共40頁，創(chuàng)作于2023年2月一般地，當(dāng)遞歸方程為：T（n）=aT（n/c）+O(n)，T（n）的解為：①O(n)a<c且c>1時(shí)②O(nlogcn)a=c且c>1時(shí)③O(nlogca)a>c且c>1時(shí)第37頁，課件共40頁，創(chuàng)作于2023年2月在滿足正確性、可靠性、健壯性、可讀性等質(zhì)量因素的前下，設(shè)法提高算法的效率。看兩組操作：(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ù)”。雖然第