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

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

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

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)生的機器代碼的質(zhì)量

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

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

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

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

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

所以：

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

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

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

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

經(jīng)常從算法中選取一種對于所研究的問題來說是基本(或者說是主要)的原操作,以該基本操作在算法中重復(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];}該算法的基本操作是乘法操作,時間復(fù)雜度為n3。

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

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

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

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

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

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

我們要確定能反映出算法在各種情況下工作的數(shù)據(jù)集,選取的數(shù)據(jù)要能夠反映、代表各種計算情況下的估算,包括最好情況下的時間復(fù)雜度(Tmax)最壞情況下的時間復(fù)雜度(Tmin)平均情況下的時間復(fù)雜度(Tavg)最有實際價值的,是最壞情況下的時間復(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ī)模的一個函數(shù)。

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

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

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

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

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

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

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

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

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

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

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

如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句,其執(zhí)行時間也不過是一個較大的常數(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)有若干個循環(huán)語句時，算法的時間復(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ù)：則該算法段的時間復(fù)雜度為：T(n)=O(n3/6+低次項)=O(n3)。第27頁，課件共40頁，創(chuàng)作于2023年2月2.算法的時間復(fù)雜度還與輸入實例的初始狀態(tài)有關(guān)。

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

【例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)，還與輸入實例中A的各元素取值及k的取值有關(guān)：

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

若對于查找不同元素的概率P不相同時，其算法復(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)造算法中的兩個步驟：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月迭代法介紹：

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

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

上節(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ù)雜一點的遞歸方程，且假設(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時②O(nlogcn)a=c且c>1時③O(nlogca)a>c且c>1時第37頁，課件共40頁，創(chuàng)作于2023年2月在滿足正確性、可靠性、健壯性、可讀性等質(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ù)”。雖然第