1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版語言版) Data Structure數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（ C語言版）嚴(yán)蔚敏、吳偉民語言版）嚴(yán)蔚敏、吳偉民本課程的體系結(jié)構(gòu)本課程的體系結(jié)構(gòu) 第一章第一章 緒論緒論 介紹數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念。 第二章第二章 第七章第七章 基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu) 從抽象數(shù)據(jù)類型的角度， 分別討論線性表、棧和隊列、串、數(shù)組和廣義表、 樹、圖等基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用。 第八章第八章 動態(tài)存儲管理動態(tài)存儲管理 介紹操作系統(tǒng)和編譯程序中涉及的 動態(tài)存儲管理的基本技術(shù)。 第九章第九章 第十一章第十一章 查找和排序查找和排序 介紹了各種實現(xiàn)方法， 并著重從時間上進(jìn)行定性或定量的分析和比較

2、。 第十二章第十二章 文件結(jié)構(gòu)文件結(jié)構(gòu) 介紹數(shù)據(jù)庫系統(tǒng)中組織文件的常用方法。 數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念 算法的概念和描述算法的概念和描述 算法的簡單分析算法的簡單分析&為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？&什么是程序、軟件？什么是程序、軟件？ N.沃思（Niklaus Wirth)教授提出： 程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 以上公式說明了如下兩個問題： （1）數(shù)據(jù)上的算法決定如何構(gòu)造和組織數(shù)據(jù)（算法數(shù)據(jù)結(jié)構(gòu)）。 （2）算法的選擇依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)算法）。 軟件軟件=程序程序+文檔（軟件工程的觀點）文檔（軟件工程的觀點） -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&電子計算

3、機的主要用途：電子計算機的主要用途：早期：早期： 主要用于數(shù)值計算。 后來：后來： 處理逐漸擴大到非數(shù)值計算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)值計算解決問題的一般步驟：數(shù)值計算解決問題的一般步驟： 數(shù)學(xué)模型選擇計算機語言編出程序測試最終解答。 數(shù)值計算的關(guān)鍵是：數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？ 程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。&非數(shù)值計算問題：非數(shù)值計算問題： 數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念 例例1.1 電話號碼查詢問題：電話號碼查詢問題： （1）按順序存儲方式：須遍歷表 （2）

4、按姓氏索引方式：索引 要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲方式。 電話號碼表的結(jié)構(gòu)和存儲方式?jīng)Q定了查找（算法）的效率。 非數(shù)值計算問題：非數(shù)值計算問題： -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念 例例1.2 田徑賽的時間安排問題（無向田徑賽的時間安排問題（無向圖的著色問題）圖的著色問題） ：設(shè)有六個比賽項目，規(guī)定每個選手至多可設(shè)有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽參加三個項目，有五人報名參加比賽（如下表所示）設(shè)計比賽日程表，使得（如下表所示）設(shè)計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。在盡可能短的時間內(nèi)完成比賽。 非數(shù)值計算問題：非數(shù)值計算問題：姓 名 項目 1

5、 項目 2 項目 3 丁 一 跳高 跳 遠(yuǎn) 100 米 馬 二 標(biāo) 槍 鉛 球 張 三 標(biāo) 搶 100 米 200 米 李 四 鉛 球 200 米 跳 高 王 五 跳 遠(yuǎn) 200 米 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念 （1）設(shè)用如下六個不同的代號代表）設(shè)用如下六個不同的代號代表不同的項目：不同的項目： 跳高 跳遠(yuǎn) 標(biāo)槍 鉛球 100米 200米 A B C D E F （2）用頂點代表比賽項目）用頂點代表比賽項目 不能同時進(jìn)行比賽的項目之間連上一條邊。 （3）某選手比賽的項目必定有邊相）某選手比賽的項目必定有邊相連（不能同時比賽）。連（不能同時比賽）。 非數(shù)值計算問題非數(shù)值計算問題 -田徑賽的時

6、間安排問題解法田徑賽的時間安排問題解法 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念姓名項目1項目2項目3丁一 A B E馬二 C D 張三 C E F李四 D F A王五 B FAEBFDC比賽時間比賽項目1A，C2B，D3E4F 只需安排四個單位時間進(jìn)行比賽 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&求解非數(shù)值計算的問題：求解非數(shù)值計算的問題： 主要考慮的是設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。 即：首先要考慮對相關(guān)的各種信息如對相關(guān)的各種信息如何表示、組織和存儲？何表示、組織和存儲？ 因此，可以認(rèn)為：數(shù)據(jù)結(jié)構(gòu)是一門研數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們

7、之間的關(guān)系和機的操作對象以及它們之間的關(guān)系和操作的學(xué)科。操作的學(xué)科。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展：數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展： 形成階段：形成階段： 60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學(xué)計算機科學(xué)系的教學(xué)計劃。 發(fā)展階段：發(fā)展階段： 數(shù)據(jù)結(jié)構(gòu)的概念不斷擴充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。 70年代后期，我國高校陸續(xù)開設(shè)該課程。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)課程數(shù)據(jù)結(jié)構(gòu)課程所處的地位：所處的地位： -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&什么是數(shù)據(jù)結(jié)構(gòu)？什

8、么是數(shù)據(jù)結(jié)構(gòu)？&幾個概念：幾個概念：數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？&幾個概念：幾個概念：數(shù)據(jù)類型（Data Type)：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。例1、 在FORTRAN語言中，變

9、量的數(shù)據(jù)類型有整型、實型、和復(fù)數(shù)型 例2、在C語言中數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？&幾個概念：幾個概念：抽象數(shù)據(jù)類型(Abstract Data Type簡稱ADT）抽象數(shù)據(jù)類型是用戶在數(shù)據(jù)類型基礎(chǔ)上 新定義的數(shù)據(jù)類型抽象數(shù)據(jù)類型定義包括數(shù)據(jù)組成 和對數(shù)據(jù)的處理操作抽象數(shù)據(jù)類型是數(shù)據(jù)和數(shù)據(jù)的使用者的一個接口抽象數(shù)據(jù)類型的三元組表示 （D，S，P） D：數(shù)據(jù)對象 S：D上的關(guān)系集 P：對D的基本操作 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)

10、據(jù)結(jié)構(gòu)？&幾個概念：幾個概念：抽象數(shù)據(jù)類型的定義：包括數(shù)據(jù)對象定義、數(shù)據(jù)關(guān)系定義和基本操作定義，書寫格式為： ADT：抽象數(shù)據(jù)類型名：抽象數(shù)據(jù)類型名 數(shù)據(jù)對象數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：數(shù)據(jù)邏輯關(guān)系的定義 基本操作基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名 （P9 例 1-6） -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？&定義定義1-是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 Data_Structure = (D,S) D：數(shù)據(jù)對象 ，S：D上的關(guān)系集。定義定義2- 按某種邏輯關(guān)系按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合

11、）應(yīng)用計算機語言并按一定的存儲表示按一定的存儲表示 方式方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的在其上定義了一個運算的集合。集合。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義：&邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)- 數(shù)據(jù)元素間抽象化的相互關(guān)系（簡稱為數(shù)據(jù)結(jié)構(gòu)）。 與數(shù)據(jù)的存儲無關(guān)，獨立于計算機，它是從具體問題抽象出來的數(shù)學(xué)模型。&存儲結(jié)構(gòu)（物理結(jié)構(gòu)）存儲結(jié)構(gòu)（物理結(jié)構(gòu)）- 數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式。 是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計算機語言。&運算（算法）運算（算法） -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：

12、數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)-劃分方法一劃分方法一 （1）線性結(jié)構(gòu)- 有且僅有一個開始和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個后繼。 例如：線性表、棧、隊列、串 （2）非線性結(jié)構(gòu)- 一個結(jié)點可能有多個直接前趨和直接后繼。 例如：樹、圖、多維數(shù)組、廣義表等。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)-劃分方法二劃分方法二一、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。三、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。四、圖狀結(jié)構(gòu)或

13、網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&存儲結(jié)構(gòu)存儲結(jié)構(gòu) 存儲結(jié)構(gòu)兩方面的內(nèi)容：存儲結(jié)構(gòu)兩方面的內(nèi)容： （1）數(shù)據(jù)元素自身值的表示（數(shù)據(jù)域） （2）該結(jié)點與其它結(jié)點關(guān)系的域（鏈域） 四種基本的存儲方法：四種基本的存儲方法： （1）順序存儲方法（結(jié)構(gòu)） （2）鏈接存儲方法（鏈?zhǔn)酱鎯Y(jié)構(gòu)） （3）索引存儲方法 （4）散列存儲方法 同一種邏輯結(jié)構(gòu)可采用不同的存儲方法（以上四種之一或組合），這主要考慮的是運算方便及算法的時空要求。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三

14、個方面的含義之：&邏輯結(jié)構(gòu)存儲結(jié)構(gòu)小結(jié)：邏輯結(jié)構(gòu)存儲結(jié)構(gòu)小結(jié)：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算（算法）構(gòu)成了數(shù)據(jù)結(jié)構(gòu)三個方面的含義。（2）程序設(shè)計的實質(zhì)是對實際問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法。而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&算法的概念和描述：算法的概念和描述：&什么是算法？什么是算法？ 所謂算法（所謂算法（Algorithm)是描述計算機解決給定問題的操作過程（解題方法），即為解決某一特定問題而由若干條指令組成的有窮序列有窮序列。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的

15、概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&算法的概念和描述：算法的概念和描述： 一個算法必須滿足以下五個準(zhǔn)則：一個算法必須滿足以下五個準(zhǔn)則： （1）有窮性）有窮性-執(zhí)行了有限條指令后一定要終止。 例1.3、例1.4 （2）確定性）確定性（無二義）- 算法的每一步操作都必須有確切定義，不得有任何歧義性。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念 例1.3 一個不是算法的例子 (1)begin (2)n=0 (3)n=n+1 (4)repeat (3) (5)end 例1.4 一個不超過100次計數(shù)的算法 (1)begin (2)n=0 (3)n=n+1 (4)if n=100 do

16、(5) else repeat(3) (5)output n (6)end返回&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&一個算法必須滿足以下五個準(zhǔn)則：一個算法必須滿足以下五個準(zhǔn)則： （3）可（能）行性）可（能）行性- 算法的每一步操作都必須是可行的，即每步操作均能在有限時間內(nèi)完成。 （4）輸入數(shù)據(jù)）輸入數(shù)據(jù)- 一個算法有n（n=0)個初始數(shù)據(jù)的輸入。 （5）輸出數(shù)據(jù)）輸出數(shù)據(jù)- 一個算法有一個或多個的有效信息的輸出。 思考：算法與程序有何區(qū)別？思考：算法與程序有何區(qū)別？ -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&算法的描述和實現(xiàn)

17、算法的描述和實現(xiàn) 描述描述-可采用自然語言、數(shù)學(xué)語言或約定的符號語言。 實現(xiàn)實現(xiàn)-必須借助程序設(shè)計語言提供的數(shù)據(jù)類型及其運算。 本課的描述本課的描述-采用類C語言 （P9-13 1.3）。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&算法的簡單分析：算法的簡單分析：&算法設(shè)計的要求：算法設(shè)計的要求：正確性、可讀性、健壯性、高效率、低存儲量需求 算法的效率指算法的執(zhí)行時間，也稱作算法的算法的時間復(fù)雜度時間復(fù)雜度 算法的存儲量需求指算法執(zhí)行過程中所需的最大存儲空間，也稱作算法的空間復(fù)雜度算法的空間復(fù)雜度 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&算法的簡單分析：算法的簡單分析：&程序正確性的四個層面：程序正確性的四個層

18、面： （1）不含語法錯誤 （2）程序?qū)τ趎組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。 （3）程序?qū)τ诰倪x擇的典型、邊界性的n組輸入數(shù)據(jù)能得出滿足規(guī)格說明要求的結(jié)果。 （4）程序?qū)τ谝磺泻线m的輸入數(shù)據(jù)都能得出滿足規(guī)格說明要求的結(jié)果（窮舉）。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念返回&算法的簡單分析之：算法的簡單分析之： -算法效率的度量算法效率的度量&1.程序運行所耗費的時間程序運行所耗費的時間(由下列因素決定由下列因素決定)： 算法所選用的策略 問題的規(guī)模 書寫程序所采用的語言 編譯程序所產(chǎn)生的機器代碼的質(zhì)量 機器執(zhí)行指令的速度 一個算法耗費的時間一個算法耗費的時間=算法中每條語句的執(zhí)行時間算法中

19、每條語句的執(zhí)行時間之和。之和。 若不考慮機器硬、軟件因素，可以認(rèn)為算法若不考慮機器硬、軟件因素，可以認(rèn)為算法“運運行工作量行工作量”的大小是問題規(guī)模的函數(shù)的大小是問題規(guī)模的函數(shù)。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&算法的簡單分析之：算法的簡單分析之： -算法效率的度量算法效率的度量&2.問題的規(guī)模問題的規(guī)模（size)- 算法求解問題的輸入量（或初始數(shù)據(jù)量）。&3.不考慮機器軟硬件環(huán)境時算法的時間耗費：不考慮機器軟硬件環(huán)境時算法的時間耗費： 設(shè)：執(zhí)行每條語句所需時間為單位時間，則： 一個算法耗費的時間=所有語句的頻度之和。 時間復(fù)雜度時間復(fù)雜度T(n)- 即：時間耗費，它是算法求解問題n的函數(shù)。

20、 漸近時間復(fù)雜度漸近時間復(fù)雜度(Asymptotic Time Complexity)- 即當(dāng)問題的規(guī)模n時的時間復(fù)雜度T(n)的數(shù)量級（階），記作：T(n)=O(f(n) 評價一個算法的時間性能，主要標(biāo)準(zhǔn)是算法的漸近時評價一個算法的時間性能，主要標(biāo)準(zhǔn)是算法的漸近時間復(fù)雜度間復(fù)雜度 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念算法效率的度量：采用時間復(fù)雜度算法效率的度量：采用時間復(fù)雜度例1.5 分析以下程序段的時間復(fù)雜度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; /* 1 * /* 2 * /分析：分析：語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。一個算法中所有語句的頻度之和構(gòu)成了該算法的運行時間。語句1的頻度是：n-1語句2的頻度是：12) 12)(1(2nnnn則該程序段的時間復(fù)雜度：T(n)=)(2222nOn例1.6 分析以下程序段的時間復(fù)雜度i=1;while (i=n) i=i*2語句1的頻度是：1設(shè)語句2的頻度是f(n)，則有：即 ，取最大值則該程序段的時間復(fù)雜度為：/* 1 * /* 2 * /nnf)(2nnf2log)(nnf2log)()(loglog1)(1)(22nOnnfn