第一章算法概述

第一章算法概述2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析1第一頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析2什么是算法？簡單的說，算法是指解決某一問題的運(yùn)算序列或者說算法是問題求解過程的運(yùn)算描述，一個(gè)算法由有限條可完全機(jī)械地執(zhí)行的、有確定結(jié)果的指令組成。指令正確地描述了要完成的任務(wù)和它們被執(zhí)行的順序。計(jì)算機(jī)按算法所描述的順序執(zhí)行算法的指令能在有限的步驟內(nèi)終止，或終止于給出問題的解，或終止與指出問題對此輸入數(shù)據(jù)無解。第二頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析3算法的五個(gè)特性確定性：每條指令的意義都是清晰的，無歧義的；

能行性：每條運(yùn)算指令是能夠?qū)崿F(xiàn)的基本運(yùn)算且能在有限時(shí)間內(nèi)完成；有窮性：每條指令的執(zhí)行次數(shù)和執(zhí)行時(shí)間都是有限的；

如：不允許有諸如“x/0”或“x與1或2相加”之類的運(yùn)算。因?yàn)榍罢呓Y(jié)果不能確定，而后者不能確定兩種可能的運(yùn)算應(yīng)該執(zhí)行哪一個(gè)。輸入：有零個(gè)或多個(gè)輸入；輸出：至少產(chǎn)生一個(gè)量作為輸出。如：如果算法中的循環(huán)步長為零，運(yùn)算進(jìn)入無限循環(huán)，這是不允許的。如：兩個(gè)實(shí)數(shù)相加是可行的；但兩個(gè)實(shí)數(shù)相除，例如求2/3的值，在沒有指明位數(shù)時(shí)需由無窮個(gè)十進(jìn)制位表示，并不可行。第三頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析4算法與過程對任何合法輸入，算法將在有限時(shí)間內(nèi)通過有窮步計(jì)算后終止。過程可以是有窮的，也可以是無窮的，不一定會(huì)終止。第四頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析5算法與程序程序是某個(gè)算法或過程在計(jì)算機(jī)上的一個(gè)具體的實(shí)現(xiàn)。程序是依賴于程序設(shè)計(jì)語言的，甚至依賴于計(jì)算機(jī)結(jié)構(gòu)的。算法是脫離具體的計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)語言的。第五頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析6算法的復(fù)雜性算法的復(fù)雜性是指算法運(yùn)行時(shí)所需要的計(jì)算機(jī)資源的量多少，所需資源量越多則復(fù)雜性越高，反之所需資源量越少則復(fù)雜性越低。其中最為重要的是：時(shí)間復(fù)雜性：需要時(shí)間的資源量。空間復(fù)雜性：需要空間的資源量。這里人們通常更為關(guān)注的是時(shí)間復(fù)雜性。第六頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析7決定算法復(fù)雜性的因素算法的復(fù)雜性取決于(1)求解問題的規(guī)模；(2)具體的輸入數(shù)據(jù)；(3)算法本身的設(shè)計(jì)。若令N、I、和A分別表示問題的規(guī)模、具體的輸入和算法本身，則C=F(N,I,A)或C=FA(N,I)=F(N,I)第七頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析8時(shí)間復(fù)雜性的計(jì)算通常用算法執(zhí)行的總語句（運(yùn)算）的數(shù)量級決定算法的時(shí)間復(fù)雜度。就算法分析而言，一條語句的數(shù)量級即執(zhí)行它的頻數(shù)，一個(gè)算法的數(shù)量級是指它所有語句執(zhí)行頻數(shù)之和。因此，算法的數(shù)量級直接決定算法的時(shí)間復(fù)雜度。第八頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析9算法的數(shù)量級觀察以下程序段：(1)x=x+1;若把程序段看成相應(yīng)算法的主體，則：(1)語句執(zhí)行頻數(shù)為1，算法數(shù)量級為1；(2)for(k=1;k<=n;k++){x=x+y;y=x+y;s=x+y;}(2)每個(gè)賦值語句執(zhí)行頻數(shù)為n，算法數(shù)量級為3n；(3)for(t=1,k=1;k<=n;k++){t=t*2;for(j=1;j<=t;j++)s=s+j;}(3)內(nèi)循環(huán)的賦值語句執(zhí)行頻數(shù)為2+22+…+2n=2(2n-1)；時(shí)間復(fù)雜度為O(1);時(shí)間復(fù)雜度為O(n);取c=2，2(2n-1)<2*2n;時(shí)間復(fù)雜度為O(2n);第九頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析10最壞、最好或平均的情況令：D為規(guī)模為N的合法輸入的集合；

I*表示在最壞情況下的輸入；

I#表示在最好情況下的輸入；P(I)輸入I出現(xiàn)的概率。W(N)=maxIDT(N,I)=T(N,I*)B(N)=minIDT(N,I)=T(N,I#)A(N)=

IDP(I)T(N,I)三者中最常用的是W(N)。第十頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析11復(fù)雜性分析的簡化在算法分析中，我們往往采用能近似表達(dá)性能的方法來展示某個(gè)算法的性能指標(biāo)。例如，當(dāng)n比較大時(shí)，計(jì)算機(jī)對n2和n2+2n的響應(yīng)速度幾乎沒有什么區(qū)別，可直接認(rèn)為二者復(fù)雜度均為n2。在分析算法時(shí)，隱藏細(xì)節(jié)的數(shù)學(xué)表示法稱為大寫O記法。第十一頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析12上界標(biāo)記設(shè)f(N)、g(N)都是定義在正整數(shù)集上的函數(shù)。上界記號(hào)O：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≧N0

時(shí)有|f(N)|≦C|g(N)|，則f(N)有上界函數(shù)g(N)，記為f(N)=O(g(N))。

即當(dāng)n足夠大時(shí)，算法的實(shí)際運(yùn)行時(shí)間不會(huì)超過g(n)的某個(gè)常數(shù)倍時(shí)間。例如第十二頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析13常見時(shí)間復(fù)雜度函數(shù)關(guān)系多項(xiàng)式算法時(shí)間：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)約定logn表示以2為底的對數(shù)。指數(shù)時(shí)間算法時(shí)間：O(2n)<O(n!)<O(nn)隨著n的增大，指數(shù)時(shí)間算法與多項(xiàng)式時(shí)間算法在所需的時(shí)間上相差非常大。一般當(dāng)n取值比較大時(shí)，在計(jì)算機(jī)上實(shí)現(xiàn)指數(shù)時(shí)間算法是不可能的，就是比O(nlogn)時(shí)間復(fù)雜度高的多項(xiàng)式時(shí)間算法運(yùn)行也很困難。第十三頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析14幾個(gè)記號(hào)下界記號(hào)Ω：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≧N0

時(shí)有|f(N)|≧C|g(N)|，則f(N)有下界函數(shù)g(N)，記為f(N)=Ω(g(N))。

即算法的實(shí)際運(yùn)行時(shí)間至少需要g(n)的某個(gè)常數(shù)倍時(shí)間。同階記號(hào)Θ：f(N)=Θ(g(N))表示f(N)和g(N)同階。

即算法的實(shí)際運(yùn)行時(shí)間大約為g(n)的某個(gè)常數(shù)倍時(shí)間。低階記號(hào)o：f(N)=o(g(N))表示f(N)比g(N)低階。第十四頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析15常用的算法設(shè)計(jì)技術(shù)分治法(DivideandConquer)動(dòng)態(tài)規(guī)劃法(DynamicProgramming)貪心法(Greedy)回溯法(Backtracking)分支界限法(BranchandBound)這些算法中都使用了遞歸(Recursion)。第十五頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析16描述算法的語言和基本數(shù)據(jù)結(jié)構(gòu)對于算法的描述，教材采用了自然語言表述和以類C語言形式化描述兩種方式。書中使用的類C語言的說明詳見P5頁第十六頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析17本書還將用到幾種常見的數(shù)據(jù)結(jié)構(gòu)，它們分別是：1、線性表

一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列，在一個(gè)非空集合中，它存在唯一的一個(gè)被稱為“第一個(gè)”的數(shù)據(jù)元素，存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素，除第一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)，除最后一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。2、樹

樹是n個(gè)結(jié)點(diǎn)的有限集合。在一棵非空樹中，有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(>0)個(gè)互不相交的有限集T1，T2，……，Tm，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹。3、圖

一個(gè)圖G是一個(gè)有序三元組，G=(V，E，Ψ)，其中：

（1）V是非空頂點(diǎn)集合；

（2）E是邊集合，E∩V=Φ；

（3）Ψ是E到{uv|u，v∈V}的映射，稱為關(guān)聯(lián)函數(shù)。

第十七頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析18偽代碼程序員常常被要求以一種常人能夠讀懂的方式描述算法。這樣的描述不是計(jì)算機(jī)程序，但比通常的描述更結(jié)構(gòu)化。它們還便于對數(shù)據(jù)結(jié)構(gòu)和算法執(zhí)行高級分析。這樣的描述稱為偽代碼。第十八頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析19例如：從鍵盤輸入整數(shù)n，按C語言的鍵盤輸入函數(shù)應(yīng)寫為：scanf(“%d”,&n);

可簡寫為：scanf(n)或輸入整數(shù)n。要輸出整數(shù)量a(1),a(2),…,a(n)，按C語言的輸出函數(shù)應(yīng)寫為：

for(k=1;k<=n;k++)printf(“%d”,a[k]);

可簡寫為：printf(a[1]~a[n])或輸出a(1~n)第十九頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析20偽代碼實(shí)例數(shù)組最大值問題：在存儲(chǔ)n個(gè)整數(shù)的數(shù)組A中找出最大元素。算法arrayMax的偽代碼描述如下：arrayMax(A,n)

{輸入：存儲(chǔ)n≥1個(gè)整數(shù)的數(shù)組A

輸出：A中的最大元素currentMax←A[0]fori←1ton-1doifcurrentMax<A[i]currentMax←A[i]returncurrentMax}偽代碼比等價(jià)的實(shí)際軟件代碼段更簡潔，更容易理解和閱讀。第二十頁，共二十二頁，編輯于2023年，星期四2023/6/21計(jì)算機(jī)算法設(shè)計(jì)與分析21什么是偽代碼？偽代碼是自然語言和高級程序設(shè)計(jì)語言的混合物，它描述數(shù)據(jù)結(jié)構(gòu)或算法的一般實(shí)現(xiàn)的主要實(shí)現(xiàn)。然而，由于偽代碼依賴于自然語言，因?yàn)閷?shí)際上偽代碼語言沒有精確的定義。編寫偽代碼時(shí)，切忌是為讀者而不是為計(jì)算機(jī)編寫的。因此，應(yīng)力圖傳達(dá)一些高級思想，而不是低級的實(shí)現(xiàn)細(xì)節(jié)。同時(shí)，對于重要步驟，不能一筆帶過。就像人類的許多交流形式，找到合適的平衡是一項(xiàng)重要的技能，大家可以通過實(shí)踐逐步改進(jìn)。第二十一頁，共二十二頁，編輯于2023年，星期四