數(shù)據(jù)結(jié)構(gòu)：第1章 緒論

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)n平時(shí)平時(shí)(實(shí)驗(yàn)實(shí)驗(yàn))：40% n期末考試期末考試(閉卷閉卷)：60%成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)關(guān)于實(shí)驗(yàn)報(bào)告關(guān)于實(shí)驗(yàn)報(bào)告 電子版形式電子版形式 統(tǒng)一實(shí)驗(yàn)報(bào)告格式統(tǒng)一實(shí)驗(yàn)報(bào)告格式 每次實(shí)驗(yàn)寫一個(gè)實(shí)驗(yàn)報(bào)告每次實(shí)驗(yàn)寫一個(gè)實(shí)驗(yàn)報(bào)告 每次實(shí)驗(yàn)報(bào)告在下次上課前提交每次實(shí)驗(yàn)報(bào)告在下次上課前提交實(shí)驗(yàn)報(bào)告文檔命名實(shí)驗(yàn)報(bào)告文檔命名 個(gè)人個(gè)人word文檔命名方式例子：文檔命名方式例子： “實(shí)驗(yàn)實(shí)驗(yàn)1-班級(jí)班級(jí)-學(xué)號(hào)學(xué)號(hào)-名字名字.doc” 按班級(jí)統(tǒng)一壓縮文檔命名方式例子：按班級(jí)統(tǒng)一壓縮文檔命名方式例子： “實(shí)驗(yàn)實(shí)驗(yàn)1-班級(jí)班級(jí).rar” 按班級(jí)統(tǒng)一發(fā)到指定郵箱，郵件標(biāo)題例子：按班級(jí)統(tǒng)一發(fā)到指定郵箱，郵

2、件標(biāo)題例子： “實(shí)驗(yàn)實(shí)驗(yàn)1-班級(jí)班級(jí)” 每次實(shí)驗(yàn)登記每次實(shí)驗(yàn)登記“學(xué)習(xí)登記表學(xué)習(xí)登記表”，并一同發(fā)送，并一同發(fā)送到指定郵箱到指定郵箱實(shí)驗(yàn)報(bào)告內(nèi)容要求實(shí)驗(yàn)報(bào)告內(nèi)容要求 問題描述、算法描述、附加了足夠注問題描述、算法描述、附加了足夠注釋的程序代碼釋的程序代碼 算法中使用的函數(shù)、過程、參數(shù)、變算法中使用的函數(shù)、過程、參數(shù)、變量的命名要能表示含義量的命名要能表示含義 注意算法格式注意算法格式(層次嵌套、不同功能層次嵌套、不同功能塊之間留空塊之間留空)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告評(píng)分標(biāo)準(zhǔn)評(píng)分標(biāo)準(zhǔn) 文檔命名文檔命名 報(bào)告封面內(nèi)容是否齊全報(bào)告封面內(nèi)容是否齊全 報(bào)告格式是否正確報(bào)告格式是否正確 報(bào)告內(nèi)容是否齊全報(bào)告內(nèi)容是

3、否齊全 報(bào)告內(nèi)容是否正確報(bào)告內(nèi)容是否正確數(shù)據(jù)結(jié)構(gòu)-第1章 緒論7 第第1 1章章 緒緒 論論數(shù)據(jù)結(jié)構(gòu)-第1章 緒論81.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的作用和意義學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的作用和意義 是為研究和解決如何有效地組織和處理是為研究和解決如何有效地組織和處理非數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)而而產(chǎn)生的理論、技術(shù)和方法。產(chǎn)生的理論、技術(shù)和方法。 是計(jì)算機(jī)科學(xué)中的一門是計(jì)算機(jī)科學(xué)中的一門綜合綜合性的專業(yè)性的專業(yè)基礎(chǔ)基礎(chǔ)課。課。 涉及計(jì)算機(jī)軟件、硬件以及數(shù)學(xué)等涉及計(jì)算機(jī)軟件、硬件以及數(shù)學(xué)等 數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的地位：數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的地位： 系統(tǒng)分析系統(tǒng)分析 系統(tǒng)設(shè)計(jì)系統(tǒng)設(shè)計(jì) 系統(tǒng)實(shí)現(xiàn)系統(tǒng)實(shí)現(xiàn) 系統(tǒng)維護(hù)系統(tǒng)維護(hù) (Nikl

4、aus Wirth：數(shù)據(jù)結(jié)構(gòu)+算法=程序)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):問題的數(shù)學(xué)模型算法算法:處理問題的策略程序設(shè)計(jì)程序設(shè)計(jì): :為計(jì)算機(jī)處理問題編制的一組指令集 數(shù)據(jù)結(jié)構(gòu)-第1章 緒論9例例 查找某人的社會(huì)關(guān)系查找某人的社會(huì)關(guān)系計(jì)算機(jī)中如何表示計(jì)算機(jī)中如何表示/存儲(chǔ)和操作？存儲(chǔ)和操作？張三李四王五陳六趙七數(shù)據(jù)結(jié)構(gòu)-第1章 緒論10 輸入 輸出CPU 控制器 運(yùn)算器寄存器(組)內(nèi)存儲(chǔ)器外存儲(chǔ)器控制器：控制系統(tǒng)一步步從存儲(chǔ)器中取出指令、譯碼運(yùn)算器：根據(jù)指令完成算術(shù)/邏輯運(yùn)算寄存器：保持程序運(yùn)行狀態(tài)、存儲(chǔ)當(dāng)前指令信息 及下一條指令地址等0OxFF操作系統(tǒng)內(nèi)存內(nèi)存（文件）（文件）數(shù)據(jù)結(jié)構(gòu)-第1章 緒論11存儲(chǔ)

5、方案存儲(chǔ)方案1： 存儲(chǔ)方案存儲(chǔ)方案2： 存儲(chǔ)方案存儲(chǔ)方案3： 張三.王五李四陳六李四王五.204020802120張三.234李四王五.204020802120(1)(2)(3)40Byte張三.311830601596王五李四.204030603118數(shù)據(jù)結(jié)構(gòu)-第1章 緒論12數(shù)據(jù)結(jié)構(gòu)的作用范疇數(shù)據(jù)結(jié)構(gòu)的作用范疇 抽象數(shù)據(jù)對(duì)象的數(shù)學(xué)模型（邏輯結(jié)構(gòu)） 例：圖狀結(jié)構(gòu) 明確操作（運(yùn)算的定義） 例：查找、插入、 在存儲(chǔ)結(jié)構(gòu)上映射數(shù)據(jù)（物理/存儲(chǔ)結(jié)構(gòu)） 例：順序存儲(chǔ) 實(shí)現(xiàn)操作數(shù)據(jù)結(jié)構(gòu)-第1章 緒論141.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)數(shù)據(jù)數(shù)據(jù) 被計(jì)算機(jī)加工處理的對(duì)象。數(shù)據(jù)元素?cái)?shù)據(jù)元素（記錄記錄、表目

6、表目） 數(shù)據(jù)的基本單位基本單位，是數(shù)據(jù)集合中的一個(gè)個(gè)體。 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中討論的數(shù)據(jù)的最小單位最小單位。 組合項(xiàng)組合項(xiàng) 年 月 日學(xué) 號(hào) 姓 名 班 號(hào) 性別 出生日期 入學(xué)成績(jī)?cè)禹?xiàng)原子項(xiàng)數(shù)據(jù)結(jié)構(gòu)-第1章 緒論15數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 學(xué)號(hào) 姓名 班號(hào) 性別 出生日期 入學(xué)成績(jī) 001 劉影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陳誠(chéng) 02 男 19840910 638 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)對(duì)象的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲(chǔ)

7、結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和相適應(yīng)的運(yùn)算運(yùn)算（結(jié)構(gòu)的行為特征）。數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)-第1章 緒論16邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)無(wú)關(guān)。 可用一個(gè)二元組抽象表示：Data_Structure = (D,R) D數(shù)據(jù)元素的有窮集合，RD上關(guān)系的有窮集合。 例例 設(shè)有數(shù)據(jù)結(jié)構(gòu) B = (D,R) ， 其中 D= d1, d2, d3, d4, d5, d6， R=r， r=, , , , ， 試畫出其邏輯結(jié)構(gòu)圖。 d1d2 d3 d4d5 d6數(shù)據(jù)結(jié)構(gòu)-第1章 緒論17四種基本的邏輯結(jié)構(gòu)四種基本的邏輯結(jié)構(gòu)（以班級(jí)學(xué)生關(guān)系為例）(1)集合結(jié)構(gòu)集合結(jié)構(gòu) 數(shù)據(jù)元素除了“屬于同一集合”的聯(lián)系之外，沒有

8、其它的關(guān)系。(2)線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。(3)樹型結(jié)構(gòu)樹型結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。(4)圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。成員關(guān)系長(zhǎng)幼關(guān)系管理關(guān)系朋友關(guān)系數(shù)據(jù)結(jié)構(gòu)-第1章 緒論18例例 鋪設(shè)城市通信管線，使總投資最少？邏輯結(jié)構(gòu)：圖狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第1章 緒論19存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)物理結(jié)構(gòu)）：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映象表示。 數(shù)據(jù)元素的映象數(shù)據(jù)元素的映象 用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。 每個(gè)數(shù)據(jù)元素的映象稱為結(jié)點(diǎn)結(jié)點(diǎn) 每個(gè)數(shù)據(jù)項(xiàng)的映象稱為數(shù)據(jù)域數(shù)據(jù)域 關(guān)系的映象關(guān)系的映象兩種基本方法及其組合使用。

9、 順序映象：以相對(duì)的存儲(chǔ)位置表示關(guān)系 鏈?zhǔn)接诚螅阂愿郊有畔?指針)表示關(guān)系在不同的編程環(huán)境下，存儲(chǔ)結(jié)構(gòu)有不同的描述方式。用高級(jí)程序語(yǔ)言編程時(shí)，通?？捎闷涮峁┑臄?shù)據(jù)類型描述。數(shù)據(jù)結(jié)構(gòu)-第1章 緒論20數(shù)據(jù)存儲(chǔ)方式的四種常用結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)方式的四種常用結(jié)構(gòu)(1)順序存儲(chǔ)順序存儲(chǔ)：數(shù)據(jù)元素依次放在連續(xù)的存儲(chǔ)單元中。 a1 a2 . ai . an (2)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)：在存儲(chǔ)結(jié)點(diǎn)中增加若干指針域，記錄后繼或者相關(guān)結(jié)點(diǎn)的地址（指針）。 a1 1220 . a3 1342 . a2 1072 .1000 1004 1000 1004 1072 1076 1220 1224指針結(jié)點(diǎn)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)-第1章 緒

10、論21(3)索引存儲(chǔ)索引存儲(chǔ)：將數(shù)據(jù)元素分為若干子表，子表的開始位置存放在索引表中。 索引表 班級(jí) addr 主表 01 1 02 31 03 54 (4)散列存儲(chǔ)散列存儲(chǔ)：根據(jù)數(shù)據(jù)元素的關(guān)鍵字值，由散列函數(shù)計(jì)算出存儲(chǔ)地址。LOC(ai)=H(key) 432 713 王小二 李一凡1 a12 a2 31 a31 數(shù)據(jù)結(jié)構(gòu)-第1章 緒論22運(yùn)算運(yùn)算（操作操作）：在數(shù)據(jù)邏輯結(jié)構(gòu)上定義的一組數(shù)據(jù)被使用的方式，其具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。幾種常用的運(yùn)算有： (1)建立數(shù)據(jù)結(jié)構(gòu) (6)檢索* (2)清除數(shù)據(jù)結(jié)構(gòu) (7)更新 (3)插入數(shù)據(jù)元素 (8)判空和判滿* (4)刪除數(shù)據(jù)元素 (9)求長(zhǎng)* (

11、5)排序 *操作為引用型操作引用型操作，即數(shù)據(jù)值不發(fā)生變化；其它為加加工型操作工型操作。數(shù)據(jù)結(jié)構(gòu)-第1章 緒論23 數(shù)據(jù)的邏輯結(jié)構(gòu)+運(yùn)算的定義-面向用戶 （抽象數(shù)據(jù)類型） 概念層 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)+運(yùn)算的實(shí)現(xiàn)-面向計(jì)算機(jī) 實(shí)現(xiàn)層分層模型分層模型數(shù)據(jù)結(jié)構(gòu)-第1章 緒論241.3 算法的描述和分析算法的描述和分析1.3.1 算法的概念算法的概念 建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的、求解問題的一系列確切的步驟。一個(gè)算法必須滿足以下一個(gè)算法必須滿足以下五五個(gè)重要特性個(gè)重要特性 有窮性：對(duì)任何合法輸入執(zhí)行有窮步后能結(jié)束。 確定性：每條指令必須有確切的含義。 可行性：算法的每一條指令均能執(zhí)行。 輸入：有零個(gè)或多個(gè)輸入。

12、 輸出：有一個(gè)或多個(gè)輸出。數(shù)據(jù)結(jié)構(gòu)-第1章 緒論25評(píng)價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)評(píng)價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn) 正確性 可讀性 健壯性 高效性（高效率與低存儲(chǔ)量）算法效率的度量算法效率的度量 時(shí)間復(fù)雜度 空間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)-第1章 緒論261.3.2 算法的描述算法的描述 數(shù)據(jù)結(jié)構(gòu)是算法處理的對(duì)象，也是實(shí)現(xiàn)算法的基礎(chǔ)。選擇描述工具的原則選擇描述工具的原則 不依賴于具體計(jì)算機(jī)與具體程序設(shè)計(jì)語(yǔ)言的一種形式化語(yǔ)言，可用于描述或表達(dá)算法思想。 本課程采用類 C語(yǔ)言 或 偽碼語(yǔ)言特點(diǎn)特點(diǎn) 它描述的算法自然易懂，具有較好的可移植性。 算法格式算法格式 void 函數(shù)名(參數(shù)表) 返回值的類型 函數(shù)名(參數(shù)表) /算法說(shuō)

13、明 /算法說(shuō)明 語(yǔ)句序列 語(yǔ)句序列 /函數(shù)名 /函數(shù)名包括順序、判定和重復(fù)三種基本控制結(jié)構(gòu)和自然語(yǔ)言成分?jǐn)?shù)據(jù)結(jié)構(gòu)-第1章 緒論27 賦值語(yǔ)句賦值語(yǔ)句變量名 = 表達(dá)式；變量名1 = 變量名2= =變量名n = 表達(dá)式；(變量名1, 變量名2, , 變量名n) =(表達(dá)式1, 表達(dá)式2, , 表達(dá)式n)；結(jié)構(gòu)變量名 =(成員1值, 成員2值, , 成員n值)；數(shù)組變量名1下標(biāo)1.下標(biāo)2 =數(shù)組變量名2下標(biāo)3.下標(biāo)4；變量名1 變量名2；變量名 = 條件表達(dá)式？表達(dá)式T：表達(dá)式F； 條件語(yǔ)句條件語(yǔ)句if ( 條件表達(dá)式) 語(yǔ)句;else 語(yǔ)句;if (條件表達(dá)式 ) 語(yǔ)句;數(shù)據(jù)結(jié)構(gòu)-第1章 緒論2

14、8 分情況語(yǔ)句（分支語(yǔ)句）分情況語(yǔ)句（分支語(yǔ)句）switch (表達(dá)式) case 值1： 語(yǔ)句序列1； break; case 值2： 語(yǔ)句序列2； break; case 值n： 語(yǔ)句序列n； break; default: 語(yǔ)句n+1；switch case 條件條件1： 語(yǔ)句序列1； break; case 條件2： 語(yǔ)句序列2； break; case 條件n： 語(yǔ)句序列n； break; default: 語(yǔ)句n+1；數(shù)據(jù)結(jié)構(gòu)-第1章 緒論29 循環(huán)語(yǔ)句循環(huán)語(yǔ)句while （條件表達(dá)式 ） 語(yǔ)句；do 語(yǔ)句序列； while （條件表達(dá)式）；break；/強(qiáng)制循環(huán)結(jié)束continu

15、e；/強(qiáng)制循環(huán)繼續(xù)for （賦初值表達(dá)式；條件；修改表達(dá)式） 語(yǔ)句；數(shù)據(jù)結(jié)構(gòu)-第1章 緒論30 輸入輸出語(yǔ)句輸入輸出語(yǔ)句scanf (變量表)；printf (變量表)； 轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移語(yǔ)句goto 語(yǔ)句標(biāo)號(hào)； 引用語(yǔ)句引用語(yǔ)句函數(shù)名(參量表)；變量名=函數(shù)名(參量表)； 返回語(yǔ)句返回語(yǔ)句return；Return 表達(dá)式 ；exit (異常代碼)； 注釋語(yǔ)句注釋語(yǔ)句/注釋內(nèi)容/* 注釋內(nèi)容 */例例 冒泡排序算法冒泡排序算法數(shù)據(jù)結(jié)構(gòu)-第1章 緒論31void bubble_sort(int a , int n ) /將a中n個(gè)數(shù)據(jù)序列重新排列成自小至大有序的整數(shù)序列 for (i=n-1, c

16、hange=TRUE; i=1 & change; -i) change=FALSE; for ( j=0; jaj+1 ) aj aj+1; change=TRUE; /bubble_sort數(shù)據(jù)結(jié)構(gòu)-第1章 緒論32 一些約定一些約定1）預(yù)定義常量和類型：/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status作為函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Status;2）數(shù)據(jù)元素類型約定為ElemT

17、ype，使用時(shí)按需定義數(shù)據(jù)結(jié)構(gòu)-第1章 緒論331.3.3 算法分析算法分析 算法效率的度量算法效率的度量 一個(gè)具體問題的數(shù)據(jù)對(duì)象往往可以采用多種存儲(chǔ)方式的一種，一個(gè)問題的解決又常常有多種可用的算法。數(shù)據(jù)結(jié)構(gòu)-第1章 緒論34通常有兩種衡量算法效率的方法通常有兩種衡量算法效率的方法: 事后統(tǒng)計(jì)法事后統(tǒng)計(jì)法 利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程 序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分事前分析估算法事前分析估算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度(漸進(jìn)時(shí)間復(fù)雜度)空間復(fù)雜度空間復(fù)雜度缺點(diǎn)：必須執(zhí)行程序缺點(diǎn)：必須執(zhí)行程序 其它因素掩蓋算法本質(zhì)其它因

18、素掩蓋算法本質(zhì)和算法執(zhí)行時(shí)間相關(guān)的因素和算法執(zhí)行時(shí)間相關(guān)的因素(1)程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量 （問題規(guī)模）（問題規(guī)模）(2)對(duì)源程序進(jìn)行編譯所需時(shí)間對(duì)源程序進(jìn)行編譯所需時(shí)間(3)計(jì)算機(jī)執(zhí)行每條指令所需時(shí)間計(jì)算機(jī)執(zhí)行每條指令所需時(shí)間(4)程序中指令重復(fù)執(zhí)行的次數(shù)程序中指令重復(fù)執(zhí)行的次數(shù) 如何估算算法的時(shí)間復(fù)雜度？如何估算算法的時(shí)間復(fù)雜度？ 從算法中選取一種對(duì)所研究的問題來(lái)說(shuō)從算法中選取一種對(duì)所研究的問題來(lái)說(shuō)執(zhí)行最頻繁的執(zhí)行最頻繁的基本操作基本操作為原操作為原操作, 當(dāng)問題規(guī)當(dāng)問題規(guī)模模 n 相當(dāng)大時(shí)相當(dāng)大時(shí), 該原操作執(zhí)行時(shí)間占算法總該原操作執(zhí)行時(shí)間占算法總執(zhí)行時(shí)

19、間的絕大部分執(zhí)行時(shí)間的絕大部分, 所以所以, 把該原操作在把該原操作在算法中重復(fù)執(zhí)行的次數(shù)算法中重復(fù)執(zhí)行的次數(shù) (頻度頻度) 作為算法運(yùn)行作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則時(shí)間的衡量準(zhǔn)則。 可近似認(rèn)為：可近似認(rèn)為：算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作的頻度原操作的頻度 成正比成正比 估算時(shí)間復(fù)雜度時(shí)取頻度的階次估算時(shí)間復(fù)雜度時(shí)取頻度的階次時(shí)間復(fù)雜度時(shí)間復(fù)雜度 n 問題規(guī)模，一般為數(shù)據(jù)的輸入量 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 算法中各語(yǔ)句的頻度之和T(n) T(n)=O( f(n) ) 大O表示法時(shí)間復(fù)雜度時(shí)間復(fù)雜度 O的含義 存在正的常數(shù)c和n0，使得當(dāng)n n0時(shí)， 0 T(n) c* f(n

20、) 表示隨著問題規(guī)模表示隨著問題規(guī)模 n n 的增長(zhǎng)的增長(zhǎng), , 算法執(zhí)行時(shí)間算法執(zhí)行時(shí)間的增長(zhǎng)率和的增長(zhǎng)率和 f(n) f(n) 的增長(zhǎng)率相同的增長(zhǎng)率相同, , 稱稱 f(n) f(n) 為算為算法的法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度，漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度，即，即， 當(dāng)當(dāng)n n 時(shí)時(shí) T (n) /f(n)T (n) /f(n)常數(shù)常數(shù) 。 常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 算法中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有算法中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7 7種種: :O(1)O(1)常數(shù)型常數(shù)型 O(n)O(n)線性型線性型 O(nO(n2 2) )平方型平方型 O(nO(n3

21、3) )立方型立方型 O(2O(2n n) )指數(shù)型指數(shù)型 O(log2n)O(log2n)對(duì)數(shù)型對(duì)數(shù)型O(nlog2n)O(nlog2n)二維型二維型按時(shí)間復(fù)雜度由小到大排列的頻率表為：按時(shí)間復(fù)雜度由小到大排列的頻率表為：時(shí)間復(fù)雜度曲線時(shí)間復(fù)雜度曲線 O(1)O(log2n)O(n)O(nlog2n)(n2)O(n3)O(2n) 時(shí)間復(fù)雜度的求法時(shí)間復(fù)雜度的求法 計(jì)算T(n) 從T(n)中推斷f(n)影響算法時(shí)間復(fù)雜度的因素影響算法時(shí)間復(fù)雜度的因素 問題的規(guī)模 輸入實(shí)例的初態(tài)時(shí)間復(fù)雜度計(jì)算步驟時(shí)間復(fù)雜度計(jì)算步驟 最壞時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度 定義：定義： 算法在最壞情況下的時(shí)間復(fù)雜度算法在最

22、壞情況下的時(shí)間復(fù)雜度，即為分析估計(jì)算法在最壞情況下執(zhí)行，即為分析估計(jì)算法在最壞情況下執(zhí)行時(shí)間的上界。時(shí)間的上界。數(shù)據(jù)結(jié)構(gòu)-第1章 緒論43例例1 交換i和j的內(nèi)容 (1) temp=i; (2) i=j; (3) j=temp; 解：T(n)=3 記作T(n)= O(1)數(shù)據(jù)結(jié)構(gòu)-第1章 緒論44例例2 nn矩陣相乘的算法語(yǔ)句 for ( i=1; i=n; i+ ) n+1 for (j=1; j=n; j+) n(n+1) ci, j=0; n2 for (k=1; k=n; k+) n2(n+1) ci, j=ci, j+ai, k*bk, j; n3 解：語(yǔ)句頻度 T(n)=2 n3 +3 n2 +2n+1 當(dāng)nn0=1時(shí)，有T(n)8n3 ，即c=8，由此取f(n)= n3 則T(n)=O(n3) 算法中存在循環(huán)時(shí)，通常算法中存在循環(huán)時(shí)，通常由嵌套層數(shù)最深的循環(huán)語(yǔ)句的由嵌套層數(shù)最深的循環(huán)語(yǔ)句的最