計(jì)算機(jī)算法基礎(chǔ)(第一章)

算法設(shè)計(jì)與分析

DesignandAnalysisofComputerAlgorithm有兩種思想,像珠寶商放在天鵝絨上的寶石一樣熠熠生輝.一個(gè)是微積分，另一個(gè)就是算法.微積分以及在微積分基礎(chǔ)上建立起來的數(shù)學(xué)分析體系造就了現(xiàn)代科學(xué),而算法造就了現(xiàn)代世界.——DavidBerlinski算法的研究?jī)?nèi)容問題是否可解1930’s研究集中于判斷特定問題在計(jì)算機(jī)上是否可解，基本方法為：選定一個(gè)計(jì)算模型，觀察是否能在該模型上創(chuàng)建能解決問題的算法。這些計(jì)算模型包括：Postmachines、Turingmachines等。這一階段的成果是：大部分問題為不可解。高效率的解決方法隨著計(jì)算機(jī)的發(fā)展和數(shù)據(jù)資源的增加，算法研究轉(zhuǎn)向針對(duì)可解的問題，找到高效率的解決方法。算法的應(yīng)用數(shù)據(jù)庫(kù)中的檢索搜索引擎中的檢索公共密鑰加密和數(shù)字簽名技術(shù)優(yōu)化問題最短路徑資源分配…章節(jié)安排《計(jì)算機(jī)算法基礎(chǔ)》，余祥宣、崔國(guó)華、鄒海明著，華中科技大學(xué)出版社第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu) √第二章分治法 √第三章貪心方法 √第四章動(dòng)態(tài)規(guī)劃 √第五章檢索與周游 √第六章回溯法 √第七章分枝-限界 √第八章NP-問題 ⊙

預(yù)備知識(shí)數(shù)學(xué)：集合、證明方法（直接、間接、反證、反例、歸納假設(shè)）、對(duì)數(shù)基礎(chǔ)、FLOOR&CEILING函數(shù)、階乘、遞歸關(guān)系數(shù)據(jù)結(jié)構(gòu)：鏈接表、圖、樹、二元樹第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1.1算法的定義及特性什么是算法？一系列將問題的輸入轉(zhuǎn)換為輸出的計(jì)算或操作步驟。

2.算法的五個(gè)重要特性確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。例：不符合確定性的運(yùn)算5/0將6或7與x相加未賦值變量參與運(yùn)算2）能行性算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在有限的時(shí)間內(nèi)完成。例：整數(shù)的算術(shù)運(yùn)算是“能行”的實(shí)數(shù)的算術(shù)運(yùn)算是“不能行”的3）輸入每個(gè)算法有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合——定義域（或值域）4）輸出一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。5）有窮性一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。

計(jì)算過程：只滿足確定性、能行性、輸入、輸出四個(gè)特性但不一定能終止的一組規(guī)則。

準(zhǔn)確理解算法和計(jì)算過程的區(qū)別：不能終止的計(jì)算過程：操作系統(tǒng)算法是“可以終止的計(jì)算過程”算法的時(shí)效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投入到計(jì)算機(jī)上運(yùn)行3.我們的主要任務(wù)算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容：1）設(shè)計(jì)算法：創(chuàng)造性的活動(dòng)2）表示算法：思想的表示形式3）確認(rèn)算法：證明算法的正確性程序的證明4）分析算法：算法時(shí)空特性分析5）測(cè)試程序：調(diào)試和作出時(shí)空分布圖本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)4.算法描述語(yǔ)言自然語(yǔ)言,數(shù)學(xué)語(yǔ)言,流程圖,程序設(shè)計(jì)語(yǔ)言等等.5.問題的求解過程2)建立數(shù)學(xué)模型1)問題的陳述3)算法設(shè)計(jì)用科學(xué)規(guī)范的語(yǔ)言,對(duì)所求解的問題做準(zhǔn)確的描述.通過對(duì)問題的分析,找出其中的所有操作對(duì)象及操作對(duì)象之間的關(guān)系并用數(shù)學(xué)語(yǔ)言加以描述.根據(jù)數(shù)學(xué)模型設(shè)計(jì)問題的計(jì)算機(jī)求解算法.4)算法的正確性證明5)算法的程序?qū)崿F(xiàn)6)算法分析證明算法對(duì)一切合法輸入均能在有限次計(jì)算后產(chǎn)生正確輸出.對(duì)執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算.將算法正確地編寫成機(jī)器語(yǔ)言程序.1.2分析算法1.分析算法的目的在于：通過對(duì)算法的分析，在把算法變成程序?qū)嶋H運(yùn)行前，就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無益的人力和物力浪費(fèi)。算法分析是計(jì)算機(jī)領(lǐng)域的古老而前沿的課題。進(jìn)行算法分析的基本技術(shù)：抽象2.重要的假設(shè)和約定1）計(jì)算機(jī)模型的假設(shè)Turing機(jī)模型：計(jì)算機(jī)形式理論模型通用計(jì)算機(jī)模型：?jiǎn)翁幚砥饔凶銐虻摹皟?nèi)存”能在固定的時(shí)間內(nèi)存取數(shù)據(jù)單元2）計(jì)算的約定確定使用什么樣的運(yùn)算及其執(zhí)行時(shí)間。從計(jì)算時(shí)間上，運(yùn)算的分類：

時(shí)間囿界于常數(shù)的運(yùn)算：盡管每種運(yùn)算的執(zhí)行時(shí)間不同，但一般只花一個(gè)固定量的時(shí)間（單位時(shí)間）就可完成。

·基本算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除

·字符運(yùn)算

·賦值運(yùn)算

·過程調(diào)用等2）計(jì)算的約定（續(xù)）其他運(yùn)算：

·字符串操作：與字符串中字符的數(shù)量成正比

·記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān)

·

特點(diǎn)：運(yùn)算時(shí)間無定量如何分析非時(shí)間囿界于常數(shù)的運(yùn)算：分解成若干時(shí)間囿界于常數(shù)的運(yùn)算。

如：Tstring=Length（String）*tchar算法的執(zhí)行時(shí)間=∑Fi*ti其中，F(xiàn)i是算法中用到的某種運(yùn)算i的次數(shù)，ti是該運(yùn)算執(zhí)行一次所用的時(shí)間。3）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運(yùn)行算法，以了解算法的性能。測(cè)試數(shù)據(jù)集的生成作為算法分析的數(shù)據(jù)集：典型特征作為程序性能測(cè)試的數(shù)據(jù)集：對(duì)執(zhí)行指標(biāo)產(chǎn)生影響的性質(zhì)3.如何進(jìn)行算法分析？對(duì)算法進(jìn)行全面分析，可分兩個(gè)階段進(jìn)行：事前分析：就算法本身，通過對(duì)其執(zhí)行性能的理論分析，得出關(guān)于算法特性——時(shí)間和空間的一個(gè)特征函數(shù)（Ο、Ω）——與計(jì)算機(jī)物理軟硬件沒有直接關(guān)系。事后測(cè)試：將算法編制成程序后實(shí)際放到計(jì)算機(jī)上運(yùn)行，收集其執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，進(jìn)行分析判斷——直接與物理實(shí)現(xiàn)有關(guān)。1）事前分析目的：試圖得出關(guān)于算法執(zhí)行特性的一種形式描述，以“理論上”衡量算法的“好壞”。如何給出反映算法執(zhí)行特性的描述？最直接方法：統(tǒng)計(jì)算法中各種運(yùn)算的執(zhí)行情況，包括：運(yùn)用了哪些運(yùn)算每種運(yùn)算被執(zhí)行的次數(shù)該種運(yùn)算執(zhí)行一次所花費(fèi)的時(shí)間等。

算法的執(zhí)行時(shí)間=∑Fi*ti頻率計(jì)數(shù)例：x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)分析：(a)：x←x+y執(zhí)行了1次(b)：x←x+y執(zhí)行了n次(c)：x←x+y執(zhí)行了n2次定義：

頻率計(jì)數(shù)：一條語(yǔ)句或一種運(yùn)算在算法（或程序）體中的執(zhí)行次數(shù)。

算法2.7插入分類procedureINSERTIONSORT(A,n)//將A(1：n)中的元素按非降次序分類，n≥1//1A(0)←-∞//設(shè)置初始邊界值2forj←2tondo//A(1:j-1)已分類//3item←A(j);i←j-14whileitem<A(i)do//0≤i<j//5A(i+1)←A(i);i←i-16repeat7A(i+1)←item;8repeatendINSERTIONSORT

(8,5,4,9)(8,5,4,9)

(5,8,4,9)(5,8,

4,9)(4,5,8,9)(4,5,8,9)一條語(yǔ)句在整個(gè)程序運(yùn)行時(shí)實(shí)際執(zhí)行時(shí)間=

頻率計(jì)數(shù)*每執(zhí)行一次該語(yǔ)句所需的時(shí)間如何刻畫算法執(zhí)行特性的形式描述實(shí)際執(zhí)行時(shí)間受約于諸多實(shí)際因素，如機(jī)器類型、編程與語(yǔ)言、操作系統(tǒng)等，沒有統(tǒng)一的描述模型。在事前分析中，只限于確定與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)的頻率計(jì)數(shù)，依此建立理論分析模型。數(shù)量級(jí)

語(yǔ)句的數(shù)量級(jí)：語(yǔ)句的執(zhí)行頻率例：1，n，n2

算法的數(shù)量級(jí)：算法所包含的所有語(yǔ)句的執(zhí)行頻率之和。算法的數(shù)量級(jí)從本質(zhì)上反映了一個(gè)算法的執(zhí)行特性。例：假如求解同一個(gè)問題的三個(gè)算法分別具有n，n2，n3數(shù)量級(jí)。若n=10，則可能的執(zhí)行時(shí)間將分別是10，100，1000個(gè)單位時(shí)間——與環(huán)境因素?zé)o關(guān)。計(jì)算時(shí)間/頻率計(jì)數(shù)的表示函數(shù)通過事前分析給出算法計(jì)算時(shí)間（頻率計(jì)數(shù)）的一個(gè)函數(shù)表示形式，一般記為與輸入規(guī)模n有關(guān)的函數(shù)形式：f(n)注：最高次項(xiàng)與函數(shù)整體的關(guān)系空間特性分析（略）2）事后測(cè)試目的：運(yùn)行程序，確定程序?qū)嶋H耗費(fèi)的時(shí)間與空間，驗(yàn)證先前的分析結(jié)論——包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計(jì)的算法。分析手段：作時(shí)、空性能分布圖4.計(jì)算時(shí)間的漸近表示記：算法的計(jì)算時(shí)間為f(n)數(shù)量級(jí)限界函數(shù)為g(n)其中，n是輸入或輸出規(guī)模的某種測(cè)度。f(n)表示算法的“實(shí)際”執(zhí)行時(shí)間—與機(jī)器及語(yǔ)言有關(guān)。g(n)是形式簡(jiǎn)單的函數(shù)，如nm，logn，2n，n!等。是事前分析中通過對(duì)計(jì)算時(shí)間或頻率計(jì)數(shù)統(tǒng)計(jì)分析所得的、與機(jī)器及語(yǔ)言無關(guān)的函數(shù)。

以下給出算法執(zhí)行時(shí)間：上界（О）、下界（Ω）、“平均”（）的定義。1）上界函數(shù)定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)|≤c|g(n)|則記作f(n)=Ο(g(n))含義：如果算法用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)。試圖求出最小的g(n)，使得f(n)=Ο(g(n))。

多項(xiàng)式定理:定理1若A(n)=amnm+…+a1n+a0是一個(gè)m次多項(xiàng)式，則有A(n)=Ο(nm)即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階。

證明：取n0=1,當(dāng)n≥n0時(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|則，定理得證。計(jì)算時(shí)間的數(shù)量級(jí)對(duì)算法有效性的影響數(shù)量級(jí)的大小對(duì)算法的有效性有決定性的影響。例：假設(shè)解決同一個(gè)問題的兩個(gè)算法，它們都有n個(gè)輸入，計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則，n=1024：分別需要1048576和10240次運(yùn)算。n=2048：分別需要4194304和22528次運(yùn)算。分析：在n加倍的情況下，一個(gè)Ο(n2)的算法計(jì)算時(shí)間增長(zhǎng)4倍，而一個(gè)Ο(nlogn)算法則只用兩倍多一點(diǎn)的時(shí)間即可完成。算法2.8歸并分類

procedureMERGESORT(low,high)//A(low:high)是一個(gè)全程數(shù)組，它含有high-low+1≥0個(gè)待分類的元素//integerlow,highiflow<highthen

mid←//計(jì)算中分點(diǎn)//callMERGESORT(low,mid)//在第一個(gè)子集合上分類(遞歸)//callMERGESORT(mid+1,high)//在第二個(gè)子集合上分類(遞歸)//callMERGE(low,mid,high)//歸并已分類的兩子集合//endifendMERGESORTMerge算法示例(4,5,8,9)|(1,2,6,7)

(1,2,4,5,6,7,8,9)參數(shù)：low=1;high=8;mid=4(4,5,8,9)|(1,2,6,7)hjjjjhh(14256789)j算法分類（計(jì)算時(shí)間）多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界的算法。常見的多項(xiàng)式限界函數(shù)有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法常見的指數(shù)時(shí)間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)說明：當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)間上非常懸殊。典型的計(jì)算時(shí)間函數(shù)曲線當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行具有比Ο(nlogn)復(fù)雜度還高的算法是比較困難的。指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算機(jī)的速度。計(jì)算時(shí)間函數(shù)值比較定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)|≥c|g(n)|則記作f(n)=Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)下界函數(shù)。試圖求出“最大”的g(n)，使得f(n)=Ω(g(n))。2）下界函數(shù)定義1.3如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|則記作含義：算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔衒(n)=Ω(g(n))，又有f(n)=Ο(g(n))3）“平均情況”限界函數(shù)4）限界函數(shù)的性質(zhì)1）若且，則。即О具有傳遞性。（同）2）當(dāng)且僅當(dāng)3）若，則。即，定義了一個(gè)等價(jià)關(guān)系（等價(jià)類）5.常用的整數(shù)求和公式在算法分析中，在統(tǒng)計(jì)語(yǔ)句的頻率時(shí)，求和公式的一般表示形式為：如：1+1+…+1（有n項(xiàng)1）=n1+2+…+n=n212+22+…+n2=n320+21+…+2n=2n+11.3關(guān)于SPARKS語(yǔ)言本書為描述算法選用的一種類計(jì)算機(jī)語(yǔ)言類PASCAL語(yǔ)言結(jié)構(gòu)化程序描述1.基本語(yǔ)法成分1）數(shù)據(jù)類型：整型、實(shí)型、布爾型、字符型2）變量聲明：integeri,j;booleanb;charc3）賦值運(yùn)算：（變量）←（表達(dá)式）4）邏輯運(yùn)算：andornot5）關(guān)系運(yùn)算：＜≤＝≠≥＞6）變量聲明：類型說明符變量；7）數(shù)組聲明：integerA（1：5，7：20）8）控制結(jié)構(gòu)：

順序:分支:

·ifconditionthenS1elseS2endif

·case:cond1:S1;:cond2:S2;…:condn:Sn:else:Sn+1endcase循環(huán):

·whileconddoSrepeat

·loopSuntilcondrepeat

·forvble←starttofinishbyincrementdoSrepeat

2.同質(zhì)異項(xiàng)3.其它

函數(shù)的定義與調(diào)用、函數(shù)和過程、變量與形式參數(shù)1.4基本數(shù)據(jù)結(jié)構(gòu)1.棧和隊(duì)列棧和隊(duì)列：n個(gè)元素的線性表利用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)——鏈表實(shí)現(xiàn)?；蜿?duì)列利用靜態(tài)數(shù)據(jù)結(jié)構(gòu)——數(shù)組實(shí)現(xiàn)棧或隊(duì)列基于以上兩種表示形式的棧和隊(duì)列上的基本運(yùn)算隊(duì)列的數(shù)組表示棧的數(shù)組表示用一維數(shù)組STACKS（1:n）表示棧底：STACKS（1）第i個(gè)元素STACKS(i)棧頂指針：topprocedureADD(item,STACAK,n,top)iftop≥nthencallSTACKFULLendiftop←top+1STACK(top)←itemendaddprocedureDELETE(item,STACK,top)iftop≤0thencallSTACKEMPTYendifitem←STACK(top)top←top-1endDELETE棧的數(shù)組表示——增加、刪除棧的鏈接表表示一種單向鏈接表兩個(gè)信息段：DATA存放數(shù)據(jù)，LINK指向前一節(jié)點(diǎn)節(jié)點(diǎn)插入callGETNODE(T)DATA(T)←itemLINK(T)←STACKSTACK←T節(jié)點(diǎn)刪除item←DATA(STACK)T←STACKSTACK←LINK(SATCK)callRETNODE(T)ASTACK0棧的鏈接表表示——增加、刪除2.樹1）樹的一般定義定義1.4樹（tree）是一個(gè)或多個(gè)結(jié)點(diǎn)的有限集合，它使得：有一個(gè)指定為根（root）的結(jié)點(diǎn)剩余結(jié)點(diǎn)被劃分成m≥0個(gè)不相交的集合：T1，…，Tm這些集合的每一個(gè)又都是一棵樹，并稱T1，…，Tm為根的子樹。關(guān)于樹的重要概念結(jié)點(diǎn)的度（degree）：一個(gè)結(jié)點(diǎn)的子樹數(shù)樹的度：樹中結(jié)點(diǎn)度的最大值結(jié)點(diǎn)的級(jí)（level）（又叫層）：設(shè)根是1級(jí)，若某結(jié)點(diǎn)在p級(jí)，則它的兒子在p+1級(jí)樹的高度（或深度）：樹中結(jié)點(diǎn)的最大級(jí)數(shù)葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)森林：m≥0個(gè)不相交樹的集合。樹的表示方法用鏈接表表示

每個(gè)結(jié)點(diǎn)三個(gè)信息段：TAG,DATA,LINK

TAG＝0，DATA存數(shù)據(jù)；TAG=1,DATA存鏈接信息，指向一棵子樹2）二元樹定義1.5二元樹（binarytree）是結(jié)點(diǎn)的有限集合，它或者為空，或者由一個(gè)根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。二元樹與度為2的樹的區(qū)別二元樹性質(zhì)1：引理1.1一棵二元樹第i級(jí)的最大結(jié)點(diǎn)數(shù)是2i-1。深度為k的二元樹的最大結(jié)點(diǎn)數(shù)為2k-1,k>0。

特殊形態(tài)的二元樹

滿二元樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二元樹

完全二元樹：一棵有n個(gè)結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹中編號(hào)為1到n的結(jié)點(diǎn)時(shí)，稱該二元樹是完全的。完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級(jí)上。完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個(gè)一維數(shù)組中（性質(zhì)見引理1.2）。二元樹的表示方法1.數(shù)組表示法：對(duì)于完全二元樹，空間效率好；其他二元樹，要浪費(fèi)大量空間2.鏈表法：結(jié)構(gòu)簡(jiǎn)單，有效。鏈表中每個(gè)結(jié)點(diǎn)有三個(gè)信息段，LCHILD,DATA和RCHILD③堆：堆是一棵完全二元樹，它的每個(gè)結(jié)點(diǎn)的值至少和該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大（max-堆）（或小，min-堆）。

④二分檢索樹：二分檢索樹Ｔ是一棵二元樹，它或者為空，或者其每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且有：·Ｔ的左子樹的所有元素比根結(jié)點(diǎn)中的元素?。弧ぃ缘挠易訕涞乃性乇雀Y(jié)點(diǎn)中的元素大；·Ｔ的左子樹和右子樹也是二分檢索樹。

注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異3.樹的應(yīng)用——不相交集合的合并及搜索問題問題描述：給定一個(gè)全集U，該集合包含n個(gè)元素很明顯該集合包含多個(gè)不相交的子集某些應(yīng)用需要實(shí)現(xiàn)這些不相交子集的合并、查找操作，并且這些操作最終可形成序列如何高效率實(shí)現(xiàn)這些操作序列就是我們要解決的問題集合操作舉例n=10，U={1,2,3,4,5,6,7,8,9,10}s1={1,7,8,9};s2={2,5,10};s3={3,4,6}合并運(yùn)算：s1∪s2={1,7,8,9,2,5,10}查找運(yùn)算：元素4包含在s1,s2,s3的哪個(gè)集合中？方法一——位向量方法一：位向量s1={1,0,0,0,0,0,1,1,1,0}；s2={0,1,0,0,1,0,0,0,0,1}；利用位運(yùn)算可得出s1∪s2={1,1,0,0,1,0,1,1,1,1}缺點(diǎn)：n很大，超過一個(gè)機(jī)器字長(zhǎng)，而參與運(yùn)算的集合的勢(shì)很小時(shí)，運(yùn)算與n成正比。方法二——集合元素表s1={1,7,8,9};s2={2,5,10}合并操作：|s1|+|s2|查找操作：最壞為|n|方法三——樹數(shù)據(jù)結(jié)構(gòu)字符數(shù)組U={1,2,3,4,5,6,7,8,9,10}子集s1={1,7,8,9};s2={2,5,10}則用數(shù)組Parent表示集合s1和s2：數(shù)組中記錄的是節(jié)點(diǎn)U[i]的父節(jié)點(diǎn)在Parent中的位置（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）00……2…1112合并操作U(1,2)后：（Parent[1]=2）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）20……2…1112查找元素F(9)U操作為常量時(shí)間，F(xiàn)操作則與查找元素在集合樹中的層數(shù)有關(guān)。U和F的性能問題——退化樹問題描述：有集合如下：（1）（2）…（n）000依次作下列操作：U(1,2),F(1),U(2,3),F(1),…,U(n-1,n)按照算法U和F，最終得到的樹及時(shí)間耗費(fèi)分析U：每次都是常量時(shí)間，因此總共是O(n-1)F(1)：2+3+…+(n-1)，因此是O(n^2)癥結(jié)？合并操作！加權(quán)規(guī)則節(jié)點(diǎn)數(shù)少的樹合并到節(jié)點(diǎn)數(shù)多的樹中。字符數(shù)組U={1,2,3,4,5,6,7,8,9,10}子集s1={1,7,8,9};s2={2,5,10}（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）-4-3……2…1112UnionF序列演示分析Union(1,2),F(1),Union(2,3),F(1),…,Union(n-1,n)Union合并的開銷較u要大，但仍然是常量時(shí)間每次查找1耗費(fèi)時(shí)間為2，常量時(shí)間，則執(zhí)行n-2次查找耗費(fèi)時(shí)間為O(n)注意：本例的查找耗時(shí)不是最壞情況最壞情況由引理1.3給出引理1.3引理1.3設(shè)T是一棵由算法union所產(chǎn)生的有n個(gè)節(jié)點(diǎn)的樹。在T中沒有節(jié)點(diǎn)的級(jí)數(shù)會(huì)大于（logn的下界+1）證明：n=1，顯然引理為真；i為T的級(jí)數(shù)，假設(shè)當(dāng)i<=n-1時(shí)，引理為真，現(xiàn)證對(duì)于i=n，引理也為真；令k和j是形成樹T的最后一次合并，即Union(k,j)；用count()表示數(shù)的節(jié)點(diǎn)數(shù)，假設(shè)count(j)=m，那么count(k)=n-m；不失一般性，可假設(shè)1<=m<n/2，則有m<=n-m；那么經(jīng)Union合并后，j的父親為k；如右圖：則T的級(jí)數(shù)：1）等于k的級(jí)數(shù)：log(n-m)的下界+1<=（logn的下界+1）2）或者等于（j的級(jí)數(shù)+1）：（logm的下界+2）<=（log(n/2)的下界+2）<=（logn的下界+1）得證壓縮規(guī)則更快的平均查找時(shí)間，適用于頻繁查找操作例1.2在下圖示例中實(shí)現(xiàn)8次對(duì)元素8的查找，用Find(8)算法實(shí)現(xiàn)總共20次，優(yōu)于使用F的8*3=24次結(jié)論：對(duì)于m次Find和n次Union的混合序列（m>=n），處理時(shí)間接近O(m)，但稍差。詳細(xì)描述見引理1.4。例1.24.圖圖Ｇ由稱之為結(jié)點(diǎn)Ｖ和邊Ｅ的兩個(gè)集合組成，記為G=（V，E）。其中，Ｖ是一個(gè)有限非空的結(jié)點(diǎn)集合；Ｅ是結(jié)點(diǎn)對(duì)偶的集合，Ｅ的每一對(duì)偶表示Ｇ的一條邊。有關(guān)圖的的重要概念無向圖：邊的表示（ｉ，ｊ）有向圖：邊的表示〈ｉ，ｊ〉成本：帶有成本的圖稱為網(wǎng)絡(luò)鄰接：結(jié)點(diǎn)的度（出度／