計(jì)算機(jī)算法基礎(chǔ)1課件

1、2022-3-18序序?qū)I(yè)基礎(chǔ)課程： 數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)語(yǔ)言 操作系統(tǒng)、編譯如何編寫計(jì)算機(jī)程序：l數(shù)據(jù)結(jié)構(gòu)+算法 = 程序l算法：計(jì)算機(jī)軟件的“靈魂” 算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心2022-3-18教材： 計(jì)算機(jī)算法基礎(chǔ) 余祥宣等編著 華中科技大學(xué)出版社參考書： 算法設(shè)計(jì)與分析 王曉東編著 清華大學(xué)出版社 計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析 盧開(kāi)澄編著 清華大學(xué)出版社 Introduction To Algorithm 高教出版社，MIT Press 學(xué)時(shí)：32+8學(xué)時(shí)2022-3-18章節(jié)安排章節(jié)安排l第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu) l第二章 分治法 l第三章 貪心方法 l第四章 動(dòng)態(tài)規(guī)劃 l第五章

2、檢索與周游 l第六章 回溯法l第七章 分枝-限界l第八章 NP-問(wèn)題? 2022-3-18第一章第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1.1 算法的定義及特性1. 什么是算法？ 算法如數(shù)字、計(jì)算一樣，是一個(gè)基本概念。 算法是解一確定類問(wèn)題的任意一種特殊的方法。 在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問(wèn)題的精確、有效方法的代名詞； 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型 問(wèn)題的一系列運(yùn)算。2022-3-182. 算法的五個(gè)重要特性 確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：不符合確定性的運(yùn)算l 5/0 l 將6或7與x相加l

3、 未賦值變量參與運(yùn)算2022-3-182）能行性 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在“有限”的時(shí)間內(nèi)完成。例：整數(shù)的算術(shù)運(yùn)算是“能行”的 實(shí)數(shù)的算術(shù)運(yùn)算是“不能行”的2022-3-183）輸入 每個(gè)算法有0個(gè)或多個(gè)輸入。這些輸入是在算法開(kāi)始之前給出的量，取自于特定的對(duì)象集合定義域（或值域）4）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。2022-3-185）有窮性 一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。 計(jì)算過(guò)程：只滿足確定性、能行性、輸入、輸出四個(gè)特性的一組規(guī)則。 l 算法和計(jì)算過(guò)程的區(qū)別： 計(jì)算過(guò)程：操作系統(tǒng)(不終止的運(yùn)行過(guò)程

4、) 算法是“可以終止的計(jì)算過(guò)程”l 算法的時(shí)效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投 入到計(jì)算機(jī)上運(yùn)行2022-3-184. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容： 1）設(shè)計(jì)算法：創(chuàng)造性的活動(dòng) 2）表示算法：思想的表示形式，SPARKS語(yǔ)言 3）確認(rèn)算法：證明算法對(duì)所有可能的合法輸入都能得出正確的答案。 算法證明：證明算法的正確性，與語(yǔ)言無(wú)關(guān) 程序證明：證明程序的正確性 4）分析算法：對(duì)算法的時(shí)、空特性做定量分析，以了解算法的好壞 5）測(cè)試程序： 調(diào)試：“調(diào)試只能指出有錯(cuò)誤，而不能指出它們不存在錯(cuò)誤” 作時(shí)空分布圖：驗(yàn)證分析結(jié)論，優(yōu)化算法設(shè)計(jì) 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過(guò)學(xué)習(xí)，

5、掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)2022-3-185. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)語(yǔ)言：結(jié)構(gòu)化設(shè)計(jì) 數(shù)學(xué)基礎(chǔ) 非數(shù)值計(jì)算領(lǐng)域的基本知識(shí)2022-3-181.2 分析算法1. 分析算法的目的 在于：通過(guò)對(duì)算法的分析，在把算法變成程序?qū)嶋H運(yùn)行前，就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無(wú)益的人力和物力浪費(fèi)。 算法分析是計(jì)算機(jī)領(lǐng)域的“古老”而“前沿”的課題。 2022-3-182. 重要的假設(shè)和約定1）計(jì)算機(jī)模型的假設(shè)l 計(jì)算機(jī)形式理論模型： Turing機(jī)模型l 通用計(jì)算機(jī)模型： 順序計(jì)算機(jī) 有足夠的“內(nèi)存” 能在固定

6、的時(shí)間內(nèi)存取數(shù)據(jù)單元 2022-3-182）計(jì)算的約定 算法的執(zhí)行時(shí)間=fi*ti 其中，fi是算法中用到的某種運(yùn)算i的次數(shù)稱為該運(yùn)算的“頻率計(jì)數(shù)” ti是該運(yùn)算執(zhí)行一次所用的時(shí)間 與程序語(yǔ)言和硬件有關(guān) 確定：使用何種運(yùn)算及其執(zhí)行時(shí)間。l 從運(yùn)算的“時(shí)間特性”上將運(yùn)算的分類： 時(shí)間囿界于常數(shù)的運(yùn)算： 基本算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除 字符運(yùn)算、賦值運(yùn)算、過(guò)程調(diào)用等 特點(diǎn)：盡管每種運(yùn)算的執(zhí)行時(shí)間不同，但一般只花一個(gè) 固定量的時(shí)間（單位時(shí)間）就可完成。2022-3-182）計(jì)算的約定（續(xù)） 其他運(yùn)算： 字符串操作：與字符串中字符的數(shù)量成正比 記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān) 特

7、點(diǎn)：運(yùn)算時(shí)間無(wú)定量。 如何分析非時(shí)間囿界于常數(shù)的運(yùn)算：分解成若干時(shí)間囿界于常數(shù)的運(yùn)算。 如：tstring = Length（String）* tchar2022-3-183）工作數(shù)據(jù)集的選擇l編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運(yùn)行算法，以了解算法的性能。 編制測(cè)試數(shù)據(jù)是程序測(cè)試與算法分析中的關(guān)鍵技術(shù)之一。 作為算法分析的數(shù)據(jù)集：反映算法的典型特征 作為程序正確性及性能測(cè)試的數(shù)據(jù)集：測(cè)試程序的對(duì)錯(cuò)，反映對(duì)性能指標(biāo)產(chǎn)生影響的方面,如邊界值2022-3-183. 如何進(jìn)行算法分析？ 對(duì)算法進(jìn)行全面分析，可分兩個(gè)階段進(jìn)行：l事前分析：求算法的一個(gè)時(shí)間/空間限

8、界函數(shù)，即通過(guò)對(duì)算 法的“理論”分析，得出關(guān)于算法時(shí)間和空間特性 的特征函數(shù)（、）與計(jì)算機(jī)物理軟硬 件沒(méi)有直接關(guān)系。l事后測(cè)試：將算法編制成程序后實(shí)際放到計(jì)算機(jī)上運(yùn)行， 收集其執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，進(jìn)行 分析判斷直接與物理實(shí)現(xiàn)有關(guān)。2022-3-181）事前分析l目的：試圖得出關(guān)于算法特性的一種形式描 述，以“理論上”衡量算法的“好壞”。l如何給出反映算法特性的描述？ 統(tǒng)計(jì)算法中各種運(yùn)算的執(zhí)行情況，包括： 引用了哪些運(yùn)算 每種運(yùn)算被執(zhí)行的次數(shù) 該種運(yùn)算執(zhí)行一次所花費(fèi)的時(shí)間等。 算法的執(zhí)行時(shí)間=fi*ti2022-3-18l頻率計(jì)數(shù) 頻率計(jì)數(shù)：算法中語(yǔ)句或運(yùn)算的執(zhí)行次數(shù)。 例： xx+y

9、 for i 1 to n do for i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b) (c) 分析： (a)： xx+y執(zhí)行了1次 (b)： xx+y執(zhí)行了n次 (c)： xx+y執(zhí)行了n2次 2022-3-18一條語(yǔ)句在整個(gè)程序運(yùn)行時(shí)實(shí)際執(zhí)行時(shí)間= 頻率計(jì)數(shù) * 每執(zhí)行一次該語(yǔ)句所需的時(shí)間l在事前分析中，只限于確定與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)的頻率計(jì)數(shù)，依此建立一種理論上分析模型。2022-3-18l數(shù)量級(jí) 衡量頻率計(jì)數(shù)的“大小”的一種測(cè)度 語(yǔ)句的數(shù)量級(jí)：語(yǔ)句的執(zhí)行頻率 例：1，n ，n2

10、 算法的數(shù)量級(jí)：算法所包含的所有語(yǔ)句的執(zhí)行頻率之和。 數(shù)量級(jí)反映了算法復(fù)雜度的最本質(zhì)的特征。例：假如求解同一個(gè)問(wèn)題的三個(gè)算法分別具有n， n2 ， n3數(shù)量級(jí)。 若n=10，則可能的執(zhí)行時(shí)間將分別是10，100，1000個(gè)單 位時(shí)間與環(huán)境因素?zé)o關(guān)。2022-3-18l 頻率計(jì)數(shù)的函數(shù)表示 就計(jì)算時(shí)間而言，事前分析階段求得算法在頻率計(jì)數(shù)上的函數(shù)表示與規(guī)模n有關(guān)的函數(shù)形式，記為： g(n) 不同的算法，g(n)的具體形式是不同的，如 logn，nlogn，n2等 g(n)的一般形式：關(guān)于n的簡(jiǎn)單函數(shù)式 “實(shí)際”能夠得到的： 1) 函數(shù)式的最高次項(xiàng) 2)最高次項(xiàng)與函數(shù)整體的關(guān)系。l空間特性分析（與時(shí)

11、間特性的分析類似，略） 2022-3-182）事后測(cè)試l目的：運(yùn)行程序，統(tǒng)計(jì)執(zhí)行實(shí)際耗費(fèi)的準(zhǔn)確的時(shí)間與空間，與事前分析的結(jié)論進(jìn)行比較，驗(yàn)證先前的分析結(jié)論包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計(jì)的算法。l分析手段：作時(shí)、空性能分布圖2022-3-184. 計(jì)算時(shí)間的漸近表示記：算法的實(shí)際計(jì)算時(shí)間為f(n)，計(jì)算時(shí)間的限界函數(shù)為g(n)其中，l n是輸入或輸出規(guī)模的某種測(cè)度。l f(n)表示算法的“實(shí)際”執(zhí)行時(shí)間與機(jī)器及語(yǔ)言有關(guān)。l g(n)是事前分析的結(jié)果一個(gè)形式簡(jiǎn)單的函數(shù)，如nm，logn，2n，n!等。是與頻率計(jì)數(shù)有關(guān)、而與機(jī)器及語(yǔ)言無(wú) 關(guān)的函數(shù)。 以下給出算法執(zhí)行時(shí)間：上界（）、下界（）、

12、“平均”（ ）的定義。2022-3-181）上界函數(shù)定義1 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n)含義：l如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)。 f(n)的數(shù)量級(jí)就是g(n)。l試圖求出最小的g(n)，使得f(n) = (g(n)。 2022-3-18多項(xiàng)式定理 定理1 若A(n) = amnm+a1n+a0是一個(gè)m次多項(xiàng)式，則有 A(n) = (nm) 即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階 nm同階。

13、 證明：取n0=1,當(dāng)nn0時(shí)，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 則，定理得證。2022-3-18計(jì)算時(shí)間的數(shù)量級(jí)的大小對(duì)算法的有效性有決定性的影響 例：假設(shè)解決同一個(gè)問(wèn)題的兩個(gè)算法，它們都有n個(gè)輸入, 計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運(yùn)算。 n=2048：分別需要4194304和22528次運(yùn)算。 分析： 同等規(guī)模下的計(jì)算量比較： 規(guī)模增大情況下的比較：在n加倍的情況下，一個(gè)

14、(n2)的算法計(jì)算時(shí)間增長(zhǎng)4倍，而一個(gè)(nlogn)算法則只用兩倍多一點(diǎn)的時(shí)間即可完成。2022-3-18多項(xiàng)式時(shí)間算法和指數(shù)時(shí)間算法多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界 的算法。 常見(jiàn)的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法 常見(jiàn)的指數(shù)時(shí)間限界函數(shù)： (2n) (n！) 0。 2022-3-182022-3-18l 特殊形態(tài)的二元樹 滿二元樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二元樹 2022-3-18 完全二元樹：一棵有n個(gè)結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的 結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹中編號(hào)為1到

15、n的結(jié)點(diǎn)時(shí)，稱該二元樹是完全的。 完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級(jí)上。 完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個(gè)一維數(shù)組中（性質(zhì)見(jiàn)引理1.2）。2022-3-18 堆：堆是一棵完全二元樹，它的每個(gè)結(jié)點(diǎn)的值至少和 該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大 （ max-堆）（或小， min-堆）。二分檢索樹：二分檢索樹是一棵二元樹，它或者為空， 或者每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且 有：的左子樹的所有元素比根結(jié)點(diǎn)中的元素小；的右子樹的所有元素比根結(jié)點(diǎn)中的元素大；的左子樹和右子樹也是二分檢索樹。注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異2022-3-183. 圖 圖由稱之為結(jié)點(diǎn)和邊的兩

16、個(gè)集合組成，記為 G=（V，E） 其中，是一個(gè)有限非空的結(jié)點(diǎn)集合；是結(jié)點(diǎn)對(duì)偶的集合，的每一對(duì)偶表示的一條邊。2022-3-18有關(guān)圖的的重要概念l無(wú)向圖：邊表示為（，）l有向圖：邊表示為，l成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖）l鄰接l結(jié)點(diǎn)的度（出度入度）l路徑：由結(jié)點(diǎn)vp到vq的一條路（path）是結(jié)點(diǎn) vp ， vi1 ， vi2 ， ， vim ， vq的一個(gè)序列，它使得 ( vp ， vi1 ) ，( vi1 ，vi2 ) ， ，( vim ， vq ) 是E（G）的邊。l路的長(zhǎng)度：組成路的邊數(shù)。2022-3-18l簡(jiǎn)單路徑：除了第一和最后一個(gè)結(jié)點(diǎn)可以相同以外，其它 所有結(jié)點(diǎn)都不同。l環(huán)

17、：第一個(gè)和最后一個(gè)結(jié)點(diǎn)相同的簡(jiǎn)單路。l連通圖：在無(wú)向圖中，如果每對(duì)結(jié)點(diǎn)之間都存在一條路徑，則 稱該圖是連通的。l子圖：是由G的結(jié)點(diǎn)集V的子集（記為VB）和邊集E中連接VB 中結(jié)點(diǎn)的邊的子集所組成的圖。l連通分圖：一個(gè)圖的最大連通子圖。l有向圖的強(qiáng)連通性：在有向圖中，如果對(duì)于每一對(duì)結(jié)點(diǎn)i和j， 既存在一條從i到j(luò)的路，又存在一條從j 到i的路，則稱該有向圖是強(qiáng)連通的。2022-3-18圖的表示方法l鄰接矩陣 鄰接表2022-3-181.5 遞歸和消去遞歸1. 遞歸l 遞歸是一種強(qiáng)有力的設(shè)計(jì)方法l 遞歸的效率問(wèn)題2022-3-18 例1.3 斐波那契(Fibonacci)序列： F0 = F1 =

18、 1 Fi = Fi-1 + Fi-2 （i1)算法1.7 求斐波那契數(shù) procedure F(n) /返回第n個(gè)斐波那契數(shù)/ integer n if nb / if b=0 then return(a) else return (GCD(b,a mod b) endif end GDC 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;2022-3-18例1.5 用遞歸策略設(shè)計(jì)的檢索算法 已知元素x和元素表A（1：n），判斷x是否等于A中某元素的值。 算法1.9 在A（1：n）中檢索x procedure SEARCH(i) /如果在A（

19、1：n）/中有一元素A（k）=x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0/ global n,x,A(1:n) case :in: return(0) :A(i) = x; return(i) :else: return(SEARCH(i+1) endcase end SEARCH2022-3-182. 消去遞歸直接遞歸的消去規(guī)則： 基本思路：將遞歸調(diào)用的地方用等價(jià)的非遞歸代碼來(lái)代替，并對(duì)return語(yǔ)句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用和return語(yǔ)句，將之轉(zhuǎn)換成等價(jià)的迭代代碼。l 初始化 在過(guò)程的開(kāi)始部分，插入說(shuō)明為棧的代碼并將其初始化為空。在一般情況下，這個(gè)棧用來(lái)存放參數(shù)、局

20、部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 將標(biāo)號(hào)L1附于第一條可執(zhí)行語(yǔ)句。然后對(duì)于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來(lái)代替。2022-3-18l 處理遞歸調(diào)用語(yǔ)句 將所有參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個(gè)全程變量來(lái)看待。 建立第i個(gè)新標(biāo)號(hào)Li，并將i存入棧。這個(gè)標(biāo)號(hào)的i值將用來(lái)計(jì)算返回地址。 此標(biāo)號(hào)放在規(guī)則所描述的程序段中。 計(jì)算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 插入一條無(wú)條件轉(zhuǎn)向語(yǔ)句轉(zhuǎn)向過(guò)程的開(kāi)始部分： goto L12022-3-18l 對(duì)退出一層遞歸調(diào)用后的處理 如果這過(guò)程是函數(shù)，則對(duì)遞歸過(guò)程中含有此次函數(shù)調(diào)用的那條語(yǔ)句做如下處

21、理：將該語(yǔ)句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來(lái)代替，其余部分的代碼按原描述方式照抄，并將中建立的標(biāo)號(hào)附于這條語(yǔ)句上。 如果此過(guò)程不是函數(shù)，則將中建立的標(biāo)號(hào)附于所產(chǎn)生的轉(zhuǎn)移語(yǔ)句后面的那條語(yǔ)句。 以上步驟消去過(guò)程中的遞歸調(diào)用。下面對(duì)過(guò)程中出現(xiàn)return語(yǔ)句進(jìn)行處理。 （純過(guò)程結(jié)束處的end可看成是一條沒(méi)有值與之聯(lián)系的return語(yǔ)句）2022-3-18l 對(duì)每個(gè)有return語(yǔ)句的地方，執(zhí)行下述規(guī)則： 如果棧為空，則執(zhí)行正常返回。 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)，out/ inout型）的當(dāng)前值賦給棧頂上的那些對(duì)應(yīng)的變量。 如果棧中有返回地址標(biāo)號(hào)的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個(gè)下標(biāo)賦給一個(gè)未使用的變量。 從棧中退出所有局部變量和參數(shù)的值并吧它們賦給對(duì)應(yīng)的變量。 如果這個(gè)過(guò)程是函數(shù)，則插入以下指令，這些指令用來(lái)計(jì)算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。2022-3-18例1.6 遞歸調(diào)用示例 求數(shù)