數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的基本概念第一頁，共五十二頁，2022年，8月28日1第1章數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型和算法描述抽象和實(shí)現(xiàn)術(shù)語和概念抽象數(shù)據(jù)類型算法與偽碼程序結(jié)構(gòu)化與設(shè)計(jì)風(fēng)格程序分析的方法時(shí)間復(fù)雜性分析漸進(jìn)式表示法遞歸式的復(fù)雜性計(jì)算第二頁，共五十二頁，2022年，8月28日1.1抽象和實(shí)現(xiàn)什么是抽象和實(shí)現(xiàn)？

抽象是信息隱蔽的方法，用這種方法將數(shù)據(jù)表示或處理過程中的細(xì)節(jié)對不需要（或不想）了解的人隱藏起來。

實(shí)現(xiàn)是已屏蔽掉的繁瑣的細(xì)節(jié)。第三頁，共五十二頁，2022年，8月28日數(shù)和變量平時(shí)使用的數(shù)據(jù)類型中哪些是抽象出來的？ 整型、實(shí)型、字符型、枚舉型等。抽象出來的數(shù)據(jù)類型是怎樣實(shí)現(xiàn)處理過程的？ 各種計(jì)算機(jī)語言的編譯程序有它們各自所抽象出來的數(shù)據(jù)類型與計(jì)算機(jī)自身的數(shù)值進(jìn)制有相應(yīng)的轉(zhuǎn)換規(guī)則，也能夠?qū)ζ溥M(jìn)行存儲(chǔ)和計(jì)算。變量是抽象的嗎？其作用是什么？ 變量是一種抽象。它的作用是減少程序設(shè)計(jì)人員對內(nèi)存細(xì)節(jié)的考慮，而將主要精力用于程序算法的編寫。第四頁，共五十二頁，2022年，8月28日兩維數(shù)組計(jì)算機(jī)存儲(chǔ)是按一維方式還是二維方式？ 計(jì)算機(jī)存儲(chǔ)區(qū)是按字節(jié)或字的一維或線性序列方式進(jìn)行編址。計(jì)算機(jī)是如何解釋帶有二維數(shù)組的語句的？ 通過編譯程序。二維數(shù)組的應(yīng)用 矩陣第五頁，共五十二頁，2022年，8月28日過程和抽象過程是什么？ 過程是程序設(shè)計(jì)的基本工具和方法，它將操作符和操作對象的概念一般化，使程序員不受程序設(shè)計(jì)語言提供的基本數(shù)據(jù)類型和操作符的約束，可以利用過程自由地定義操作數(shù)和操作方法。過程的優(yōu)點(diǎn) 利用過程的優(yōu)點(diǎn)在于信息的隱蔽和模塊化，它實(shí)現(xiàn)了對算法的若干部分的封裝。抽象都是程序設(shè)計(jì)語言提供的嗎？過程是一種抽象嗎？第六頁，共五十二頁，2022年，8月28日1.2術(shù)語和概念數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)對象數(shù)據(jù)就是指所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號(hào)的集合，它也是計(jì)算機(jī)操作的對象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。 注意：數(shù)據(jù)的范圍是隨著計(jì)算機(jī)的發(fā)展而不斷擴(kuò)大的。數(shù)據(jù)元素是數(shù)據(jù)中的一個(gè)個(gè)體，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。一個(gè)數(shù)據(jù)元素還可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。如整數(shù)這個(gè)集合中，10這個(gè)數(shù)就可稱是一個(gè)數(shù)據(jù)元素.又比如在一個(gè)數(shù)據(jù)庫表(關(guān)系式數(shù)據(jù)庫)中，一個(gè)記錄可稱為一條數(shù)據(jù)，每一個(gè)字段可稱為一個(gè)數(shù)據(jù)元素，而每個(gè)字段的組成部分可稱為一個(gè)數(shù)據(jù)項(xiàng)(例如出生日期中的年、月、日)。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。第七頁，共五十二頁，2022年，8月28日1.2.2數(shù)據(jù)類型在用高級(jí)語言編寫的程序中，必須對程序中出現(xiàn)的每個(gè)變量、常量和表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。數(shù)據(jù)類型是程序設(shè)計(jì)語言中對于給定變量的所有可能取值的集合。數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。每一個(gè)對象僅由單值構(gòu)成的類型稱為標(biāo)量類型或原子類型。每一個(gè)對象可由一組值構(gòu)成的類型稱為組合類型或結(jié)構(gòu)類型（有時(shí)也稱為數(shù)據(jù)結(jié)構(gòu)）第八頁，共五十二頁，2022年，8月28日1.2.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstractdatatype簡稱ADT)是一種數(shù)據(jù)類型及在這個(gè)類型上定義的一組合法的操作。程序設(shè)計(jì)語言提供的ADT定義工具 Ada提供包、c++提供類使用ADT的作用 減少程序的復(fù)雜性第九頁，共五十二頁，2022年，8月28日1.2.4數(shù)據(jù)結(jié)構(gòu)

(帶結(jié)構(gòu)的數(shù)據(jù)元素的集合)定義：

數(shù)據(jù)結(jié)構(gòu)是以某種方式聯(lián)系在一起的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容 數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)元素之間抽象化的相互關(guān)系及這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示，對每種結(jié)構(gòu)定義各自的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并用某種語言實(shí)現(xiàn)該算法。數(shù)據(jù)結(jié)構(gòu)包含的內(nèi)容： 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，甚至包括對數(shù)據(jù)的操作。 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立起來的，呈現(xiàn)在用戶面前的結(jié)構(gòu)形式。數(shù)據(jù)的物理結(jié)構(gòu)又稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的表示方法，即存儲(chǔ)形式。第十頁，共五十二頁，2022年，8月28日 比如一個(gè)表(數(shù)據(jù)庫)，我們就稱它為一個(gè)數(shù)據(jù)結(jié)構(gòu)，它由很多記錄(數(shù)據(jù)元素)組成，每個(gè)元素又包括很多字段(數(shù)據(jù)項(xiàng))組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢?對于這個(gè)表中的任一個(gè)記錄(結(jié)點(diǎn))，它只有一個(gè)直接前趨，只有一個(gè)直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個(gè)表只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，那我們知道了這些關(guān)系就能明白這個(gè)表的邏輯結(jié)構(gòu)了。常見的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合結(jié)構(gòu)。第十一頁，共五十二頁，2022年，8月28日存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像。數(shù)據(jù)元素的映像方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。(320)10=(501)8=(101000001)2(A)=(101)8=(001000001)2關(guān)系的映像方法（表示<X,Y>的方法）順序映像：以存儲(chǔ)位置的相鄰表示后繼關(guān)系。 Y的存儲(chǔ)位置和X的存儲(chǔ)位置之間相差一個(gè)常量C，而C是一個(gè)隱含值（與數(shù)據(jù)在內(nèi)存中占據(jù)的寬度有關(guān)），整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。 第十二頁，共五十二頁，2022年，8月28日

鏈?zhǔn)接诚瘢阂愿郊有畔?指針)表示后繼關(guān)系 需要一個(gè)和X在一起的附加信息指示Y的存儲(chǔ)位置。 在不同的存儲(chǔ)環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。 當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通常可用高級(jí)編程語言提供的數(shù)據(jù)類型描述之。第十三頁，共五十二頁，2022年，8月28日 例如：以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長整數(shù)時(shí)，可利用C語言中提供的整數(shù)數(shù)組類型，定義長整數(shù)為： typedefintLong_int[3]第十四頁，共五十二頁，2022年，8月28日

對數(shù)據(jù)的運(yùn)算:比如一張表格，我們需要進(jìn)行查找，增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢?這也就是數(shù)據(jù)的運(yùn)算，它不僅僅是加減乘除這些算術(shù)運(yùn)算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運(yùn)算常常涉及算法問題。第十五頁，共五十二頁，2022年，8月28日1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的描述研究抽象數(shù)據(jù)類型的原因？ 人們認(rèn)識(shí)到在問題的描述和程序的實(shí)現(xiàn)之間存在著一個(gè)可適當(dāng)定義的中間領(lǐng)域，這個(gè)中間領(lǐng)域比問題的描述具體些，但比最終的程序抽象些。數(shù)據(jù)結(jié)構(gòu)的類型：線性、層次、網(wǎng)狀抽象數(shù)據(jù)類型的組成部分：元素(Elements)、結(jié)構(gòu)(Structure)和操作(Operation)第十六頁，共五十二頁，2022年，8月28日抽象數(shù)據(jù)類型的說明元素結(jié)構(gòu)操作 ADT的說明基本上是功能性的說明，對具體的實(shí)現(xiàn)并不作過多的約束。在具體現(xiàn)實(shí)時(shí)，完成任務(wù)的算法、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、程序的邏輯組織甚至采用哪種程序設(shè)計(jì)語言都是可自由選擇的。第十七頁，共五十二頁，2022年，8月28日ADT的主要目的：對用戶隱蔽所有的表示方法、算法的詳細(xì)細(xì)節(jié)、實(shí)現(xiàn)操作的具體代碼及其他所有不必要的細(xì)節(jié)，這些細(xì)節(jié)被局限于具體實(shí)現(xiàn)的模塊內(nèi)部，從而實(shí)現(xiàn)了信息的隱蔽。ADT的重要優(yōu)點(diǎn)：簡單性。抽象的目的：將數(shù)據(jù)的本質(zhì)特征、它們的結(jié)構(gòu)及操作同它們的非本質(zhì)的具體表示及實(shí)現(xiàn)細(xì)節(jié)區(qū)別開來，從而得到了簡化。第十八頁，共五十二頁，2022年，8月28日抽象數(shù)據(jù)類型的表示為撲克牌設(shè)計(jì)抽象數(shù)據(jù)類型，你會(huì)怎樣設(shè)計(jì)？使用枚舉類型使用整數(shù)型使用位向量表示法 程序設(shè)計(jì)的主要目標(biāo)是產(chǎn)生一個(gè)正確的程序，并能盡量避免錯(cuò)誤的輸入對程序的結(jié)果造成不良的影響，但是還有其他第二位重要的目標(biāo)。好的程序不僅要運(yùn)行正確，而且要具有通用性、模塊化和信息隱蔽性。第十九頁，共五十二頁，2022年，8月28日實(shí)現(xiàn)的獨(dú)立性 由于在ADT的說明中，只指明了其功能而未指明要采用的何種方法，因此實(shí)現(xiàn)的獨(dú)立性是顯而易見的。 具體的實(shí)現(xiàn)只要根據(jù)ADT的數(shù)據(jù)類型及說明的各個(gè)抽象操作和ADT的表示，用某種程序設(shè)計(jì)語言寫出一個(gè)個(gè)獨(dú)立的過程和函數(shù)的具體語句來即可。第二十頁，共五十二頁，2022年，8月28日一個(gè)復(fù)數(shù)抽象數(shù)據(jù)類型元素介紹 復(fù)數(shù)的實(shí)部(rpart)和虛部(ipart)結(jié)構(gòu)說明 復(fù)數(shù)的元素之間不存在任何結(jié)構(gòu)操作部分 復(fù)數(shù)的生成(Create)，兩個(gè)復(fù)數(shù)的加(Add)、減(Sub)、乘法(Product)運(yùn)算第二十一頁，共五十二頁，2022年，8月28日編程練習(xí)： 試分別用結(jié)構(gòu)和類兩種方式實(shí)現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型的定義。 設(shè)兩個(gè)復(fù)數(shù)c1=x1+iy1，c2=x2+iy2 和sum=(x1+y1)+i(y1+y2) 差difference=(x1-x2)+i(y1-y2) 積product=(x1*x2-y1*y2)+i(x1*y2+x2*y1)第二十二頁，共五十二頁，2022年，8月28日1.4算法分析 算法+數(shù)據(jù)結(jié)構(gòu)=程序(N.沃恩)這個(gè)公式的含義是什么？算法的概念算法是能在計(jì)算機(jī)上經(jīng)過有限的時(shí)間內(nèi)完成，毫不含糊的有限的指令序列。程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制的一組指令集。 計(jì)算機(jī)對某類問題進(jìn)行某種處理，包含了兩方面的問題：一個(gè)是怎樣進(jìn)行處理；另一個(gè)是對處理的信息怎樣表示。算法：處理問題的策略（怎樣處理問題）數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型（處理的問題怎樣表示）第二十三頁，共五十二頁，2022年，8月28日例如:數(shù)值計(jì)算的程序問題結(jié)構(gòu)靜力分析計(jì)算數(shù)據(jù)模型：線性代數(shù)方程組全球天氣預(yù)報(bào)數(shù)據(jù)模型：環(huán)流模型方程第二十四頁，共五十二頁，2022年，8月28日非數(shù)值計(jì)算的程序設(shè)計(jì)問題例一：求一組(n個(gè))整數(shù)中的最大值。算法：基本操作是比較兩個(gè)數(shù)的大小模型：存儲(chǔ)這組整數(shù)所需的數(shù)據(jù)類型。第二十五頁，共五十二頁，2022年，8月28日例二：計(jì)算機(jī)對弈算法：對弈的規(guī)則和策略模型：棋盤、棋子的表示第二十六頁，共五十二頁，2022年，8月28日例三：醫(yī)院的數(shù)據(jù)庫管理算法：需要管理的項(xiàng)目？如何管理？界面？模型：各種表格和數(shù)據(jù)庫第二十七頁，共五十二頁，2022年，8月28日綜合各種程序設(shè)計(jì)問題，抽去它具體的物理含義，就可以得到幾類基本的數(shù)學(xué)模型，比如和數(shù)值計(jì)算相關(guān)的數(shù)學(xué)模型就有線性代數(shù)方程、非線性代數(shù)方程、微分方程等。它們的數(shù)值解問題，也就是計(jì)算求解的問題，就是計(jì)算數(shù)學(xué)要解決的問題。而類似的非數(shù)值計(jì)算問題，它的數(shù)學(xué)模型的表示和求解的方法就是數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。概括的說： 數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型（非數(shù)值計(jì)算）及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。第二十八頁，共五十二頁，2022年，8月28日算法與代碼 算法是為了解決某類問題而規(guī)定的一個(gè)有限長的操作序列。 簡單的說，算法是對求解某一問題的描述。 算法都必須滿足下列幾個(gè)條件：●有窮性：對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。第二十九頁，共五十二頁，2022年，8月28日●確定性：對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑(對同樣的輸入值，不管在什么條件下，重復(fù)執(zhí)行多遍，都能夠得到相同的結(jié)果)?！窨尚行裕核惴ㄖ械乃胁僮鞫急仨氉銐蚧荆伎梢酝ㄟ^已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。 例如：將x和y兩個(gè)正整數(shù)的最大公因子賦值給z，由于求最大公因子本身就是一個(gè)算法，因此這個(gè)操作不是基本操作。 例如：將變量x的值增加，看似簡單，但到底給x增加多少卻并不明確，因此它也不是基本操作。第三十頁，共五十二頁，2022年，8月28日●有輸入：作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際已被嵌入算法之中。 例如求100以內(nèi)的素?cái)?shù)。數(shù)據(jù)的范圍是從1到100，此時(shí)的數(shù)據(jù)就沒有從鍵盤輸入而是嵌入到了算法之中?！裼休敵觯核且唤M與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。第三十一頁，共五十二頁，2022年，8月28日算法設(shè)計(jì)的原則1.正確性程序中不含語法錯(cuò)誤程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果第三十二頁，共五十二頁，2022年，8月28日2.可讀性 算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法易于人的理解，另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3.健壯性 當(dāng)輸入的數(shù)據(jù)合法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)的處理，而不是莫名其妙地輸出結(jié)果。并且處理出錯(cuò)的方法不應(yīng)時(shí)中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。第三十三頁，共五十二頁，2022年，8月28日4.高效率與低存儲(chǔ)量需求通常，效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。兩者都與問題的規(guī)模有關(guān)。第三十四頁，共五十二頁，2022年，8月28日用來寫算法的方式有好幾種，一般而言，我們可以分為下列4種方式：●條列式的步驟： 以條列式的步驟來描述解決問題的方法。●流程圖： 以圖形符號(hào)來描述解決問題的方法。僅適用于小問題，不過現(xiàn)在已很少用。●偽碼： 以夾雜程序語法和自然語言(如：中文、英文)的形式來描述解決問題的方法。●程序語句： 直接以程序語法來描述解決問題的方法。第三十五頁，共五十二頁，2022年，8月28日程序結(jié)構(gòu)化與設(shè)計(jì)風(fēng)格注釋變量命名 變量名要遵守以下規(guī)則： (1)不能是C++保留字。 (2)第一個(gè)字符必須是字母或下劃線。 (3)變量名中除了使用26個(gè)英文大小寫字母和數(shù)字外，只能使用下劃線。 (4)一般不要超過31個(gè)字符。 (5)變量名不要與C++中的庫函數(shù)名、類名和對象名相同。程序縮排段落第三十六頁，共五十二頁，2022年，8月28日算法的時(shí)間復(fù)雜性

算法衡量的方法和準(zhǔn)則 一個(gè)程序結(jié)構(gòu)的好壞，關(guān)鍵通常在于該程序是否能以最短的時(shí)間及最小的空間來運(yùn)行出結(jié)果。但是“時(shí)間”與“空間”常常是“魚與熊掌”無法兼得，如果希望以最短的時(shí)間來完成該程序，則常常需要運(yùn)用更多的存儲(chǔ)空間，來換取最短的執(zhí)行時(shí)間；如果希望以最小的存儲(chǔ)空間來完成該程序，相反的也必須用較久的時(shí)間，才能完成該程序。第三十七頁，共五十二頁，2022年，8月28日通常有兩種衡量算法的方法：1.事后統(tǒng)計(jì)法 缺點(diǎn)：●必須執(zhí)行程序

●其它因素掩蓋算法本質(zhì)2.事前統(tǒng)計(jì)法（推薦）第三十八頁，共五十二頁，2022年，8月28日和算法執(zhí)行時(shí)間相關(guān)的因素1.算法選用的策略2.問題的規(guī)模3.編寫程序的語言（匯編語言的速度比C語言快）4.編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5.計(jì)算機(jī)執(zhí)行指令的速度 其中后3條與計(jì)算機(jī)本身的運(yùn)算速度有關(guān)，與算法無關(guān)。因此我們在設(shè)計(jì)算法的時(shí)候不考慮后3條。 一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模(通常用整數(shù)n表示)，或者說，它是問題規(guī)模的函數(shù)。第三十九頁，共五十二頁，2022年，8月28日

定義：如某算法執(zhí)行時(shí)間T(n)是O(f(n))，意思是說存在常數(shù)c和n0，使得對于一切n≥n0，T(n)≤cf(n)都成立。如果一個(gè)程序的時(shí)間復(fù)雜性是O(f(n))，就說該程序的運(yùn)行時(shí)間增加一個(gè)上界為f(n)，或說T(n)是f(n)的大O函數(shù)。 假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率與f(n)相同，則可記作： T(n)=O(f(n)) 稱T(n)為算法的(漸近)時(shí)間復(fù)雜性。 其中，O()表示函數(shù)T(n)與f(n)成正比，或者說它們是一個(gè)數(shù)量級(jí)的。第四十頁，共五十二頁，2022年，8月28日算法的時(shí)間復(fù)雜性 我們將每個(gè)程序所花費(fèi)的運(yùn)行次數(shù)稱為該程序的“時(shí)間復(fù)雜性(Timecomplexity)”，運(yùn)用時(shí)間復(fù)雜性的概念，我們即可判斷該程序的執(zhí)行效率是否良好，也方便對兩個(gè)程序進(jìn)行分析與比較。 從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量標(biāo)準(zhǔn)。●最佳狀況（Best-Case），記做：B(n)●最壞狀況(Worst-Case)，記做：W(n)●一般狀況的時(shí)間復(fù)雜性，記做：E(n))●平均狀況的時(shí)間復(fù)雜性，記做：A(n)第四十一頁，共五十二頁，2022年，8月28日大O運(yùn)算規(guī)則規(guī)則1： 對于任何的常數(shù)k和任何的函數(shù)f，kf(n)=O(f(n))規(guī)則2 Iff(n)=O(g(n))andg(n)=O(h(n)) Thenf(n)=O(h(n))規(guī)則3 f(n)+g(n)=O(max{f(n),g(n)})規(guī)則4 Iff1(n)=O(g1(n))andf2(n)=O(g2(n)) Thenf1(n)*f2(n)=O(g1(n)*g2(n))第四十二頁，共五十二頁，2022年，8月28日1.4.4事件復(fù)雜性分析

如何估算算法的時(shí)間復(fù)雜性算法=控制結(jié)構(gòu)+若干原操作這里所說的原操作本來應(yīng)該是計(jì)算機(jī)的基本指令，但當(dāng)我們用高級(jí)語言來描述算法的時(shí)候，也可以把固有數(shù)據(jù)類型的操作看成是原操作。算法的執(zhí)行時(shí)間= ∑原操作的執(zhí)行次數(shù)*原操作的執(zhí)行時(shí)間由于原操作的執(zhí)行時(shí)間對于不同的算法來說都是一個(gè)定值。因此，算法的執(zhí)行時(shí)間與原操作執(zhí)行次數(shù)之和成正比。第四十三頁，共五十二頁，2022年，8月28日 從算法中選取一種對于所研究的問題來說是基本操作（在所有原操作中起到?jīng)Q定性的作用）的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量標(biāo)準(zhǔn)。第四十四頁，共五十二頁，2022年，8月28日例一：矩陣相乘FOR(I=1;I<=N;I++) FOR(J=1;J<=N;J++) { C[I,J]=0; FOR(K=1;K<=N;K++) C[I,J]+=A[I,K]*B[K,J]; }原操作：賦值、加法、乘法基本操作：乘法操作時(shí)間復(fù)雜性O(shè)(N3)第四十五頁，共五十二頁，2022年，8月28日例2：選擇排序（時(shí)間復(fù)雜性是問題規(guī)模的函數(shù)，與輸入數(shù)據(jù)無關(guān)）Voidselect_sort(inta[],intn)//將a中整數(shù)序列重新排列成從小至大有序的整數(shù)序列{ for(i=0;i<n-1;i++) { j=i; for(k=i+1;k<n;k++) Ifa[k]<a[j] j=k; If(j!=i) A[j]<-->a[i]; }}基本操作：比較數(shù)據(jù)元素當(dāng)I=0時(shí)比較的次數(shù)為N-1次，當(dāng)I=N-2時(shí)比較的次數(shù)為1次，即總次數(shù)為(N-1)+(N-2)+…+1=N*(N-1)/2也就是說比較次數(shù)與N2/2成正比，即與N2成正比時(shí)間復(fù)雜性：O(N2)第四十六頁，共五十二頁，2022年，8月28日例3：冒泡排序（時(shí)間復(fù)雜性既是問題規(guī)模的函數(shù)，又與輸入數(shù)據(jù)有關(guān)）Voidbubble_sort(inta[],intn)//將a中整數(shù)