常璐璐-數(shù)據(jù)結(jié)構(gòu)-第一章

1、數(shù)據(jù)結(jié)構(gòu)常璐璐 計(jì)算機(jī)科學(xué)技術(shù)系數(shù)據(jù)結(jié)構(gòu)課程地位數(shù)據(jù)結(jié)構(gòu)課程地位 教材內(nèi)容劃分：教材內(nèi)容劃分：l第一部分：第一部分：數(shù)據(jù)結(jié)構(gòu)的基本概念（第數(shù)據(jù)結(jié)構(gòu)的基本概念（第1章）章）l第二部分：第二部分：基本的數(shù)據(jù)結(jié)構(gòu)基本的數(shù)據(jù)結(jié)構(gòu) 包括：線性包括：線性結(jié)構(gòu)結(jié)構(gòu)線性表、棧和隊(duì)列、串、數(shù)組與廣義表線性表、棧和隊(duì)列、串、數(shù)組與廣義表 （第（第25章）章） 非線性結(jié)構(gòu)非線性結(jié)構(gòu)樹、圖（第樹、圖（第6、7章）章）l第三部分：第三部分：基本技術(shù)基本技術(shù) 包括：查找技術(shù)與排序包括：查找技術(shù)與排序技術(shù)（第技術(shù)（第8、9、10章）章）1.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2 基本概念基本概念1.3 算法和算法的

2、量度算法和算法的量度第一章第一章1.11.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇數(shù)據(jù)結(jié)構(gòu)討論的范疇尼克萊斯尼克萊斯沃思（沃思（NiklausWirth） ： Algorithm + Data Structures = Programs程序設(shè)計(jì)程序設(shè)計(jì): :算法算法: 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 為計(jì)算機(jī)處理問題編制 一組指令集 處理問題的策略處理問題的策略問題的數(shù)學(xué)模型問題的數(shù)學(xué)模型非數(shù)值計(jì)算的程序設(shè)計(jì)問題例一例一: 求一組(n個(gè))整數(shù)整數(shù)中的最大值算法: ? ?模型：？基本操作是“比較兩個(gè)數(shù)的大小比較兩個(gè)數(shù)的大小”取決于整數(shù)值的范圍整數(shù)值的范圍例二：例二：計(jì)算機(jī)對(duì)弈算法：?模型：?對(duì)弈的規(guī)則和策略棋盤及棋盤的格局例

3、三：例三：足協(xié)的數(shù)據(jù)庫管理算法：?模型：?需要管理的項(xiàng)目？如何管理？ 用戶界面？各種表格概括地說：概括地說： 數(shù)據(jù)結(jié)構(gòu)是一門討論數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型實(shí)世界實(shí)體的數(shù)學(xué)模型( (非數(shù)值計(jì)非數(shù)值計(jì)算算) )及其上的操作在計(jì)算機(jī)中如何及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)表示和實(shí)現(xiàn)”的學(xué)科。的學(xué)科。1.2 基本概念基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)處理的符號(hào)的集合。數(shù)據(jù)數(shù)據(jù): :是計(jì)算機(jī)操作的對(duì)象計(jì)算機(jī)操作的對(duì)象的總稱。

4、是計(jì)算機(jī)處理的信息的信息的某種特定的符號(hào)表示形式表示形式。是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體個(gè)體”數(shù)據(jù)元素?cái)?shù)據(jù)元素: :是數(shù)據(jù)結(jié)構(gòu)中討論的基本基本單位 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小最小單位一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是年年 月月 日日姓姓名名俱俱樂樂部部名名稱稱出出生生日日期期參參加加日日期期職職務(wù)務(wù)業(yè)業(yè)績績稱之為組合項(xiàng)稱之為組合項(xiàng)數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合假設(shè)用三個(gè)三個(gè) 4 位的十進(jìn)制數(shù)位的十進(jìn)制數(shù)表示一個(gè)含 12 位位數(shù)的十進(jìn)制數(shù)。數(shù)的十進(jìn)制數(shù)。3214,6587,9345 a1(3214),

5、a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序次序”關(guān)系關(guān)系 a1,a2 、 a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如例如: :又例，在2行3列的二維數(shù)組a1, a2, a3, a4, a5, a6中六個(gè)元素之間存在兩個(gè)關(guān)系: a1 a2 a3 a4 a5 a6行的次序關(guān)系行的次序關(guān)系:列的次序關(guān)系列的次序關(guān)系: :row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合再例，在一維數(shù)組 a1,

6、a2, a3, a4, a5, a6 的數(shù)據(jù)元素之間存在如下的次序關(guān)系次序關(guān)系:| i=1, 2, 3, 4, 5 或者說，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某相互之間存在著某種種邏輯關(guān)系邏輯關(guān)系的數(shù)據(jù)元素的集合的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合可見，不同的“關(guān)系關(guān)系”構(gòu)成不同的“結(jié)構(gòu)結(jié)構(gòu)”數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)可歸結(jié)為以下四類四類: :線性線性結(jié)構(gòu)樹形樹形結(jié)構(gòu)圖狀圖狀結(jié)構(gòu)集合集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 Data_Structures = (D, S)其中:D 是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是 D上關(guān)系

7、的有限集關(guān)系的有限集。例1 復(fù)數(shù)的二元組定義 復(fù)數(shù)由實(shí)部和虛部構(gòu)成（構(gòu)成元素），兩者之間存在著一種次序關(guān)系（邏輯關(guān)系）。 可以表示為： Complex=(C,R) 其中,C= c1,c2 R=說明:表示有序數(shù)對(duì),用圖示法表示時(shí)畫箭頭 ( )表示無序數(shù)對(duì),用圖示法表示時(shí)畫線段 例2 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為: B=(K,R) K=k1,k2,k3,k4,k5,k6,k7,k8,k9 R=,畫出這個(gè)結(jié)構(gòu)的圖示.k1k2k3k4k5k6k7k8k9網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)(有向圖有向圖)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu)在存儲(chǔ)器中的表示(映象映象) )“數(shù)據(jù)元素”的映象 ？“關(guān)系”的映象 ？數(shù)據(jù)元素的映象方法：數(shù)據(jù)

8、元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2關(guān)系的映象方法：關(guān)系的映象方法：（表示x, y的方法）順序映象順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如例如: :存儲(chǔ)復(fù)數(shù)存儲(chǔ)復(fù)數(shù) z=3.0-2.3i z=3.0-2.3i 用順序結(jié)構(gòu)，內(nèi)存存儲(chǔ)情況為:20012002200320043.0-2.3鏈?zhǔn)接诚箧準(zhǔn)接诚笠愿郊有畔⒁愿郊有畔? (指針指針) )表示后繼關(guān)系表示后繼關(guān)系20012002200320043.0203620362037-2.3在不同

9、的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。二、數(shù)據(jù)類型二、數(shù)據(jù)類型在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明明確說明它們所屬的數(shù)據(jù)類型數(shù)據(jù)類型。 不同類型的變量，其所能取的值的范圍值的范圍不同，所能進(jìn)行的操作進(jìn)行的操作不同。例如，C 語言中提供的基本數(shù)據(jù)類型基本數(shù)據(jù)類型有:整型整型 int浮點(diǎn)型浮點(diǎn)型 float字符型字符型 char空類型空類型 void雙精度型雙精度型 double實(shí)型（實(shí)型（ C+語言）語言）三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型 (Abstract Data Ty

10、pe 簡稱簡稱ADT)例如，例如，抽象數(shù)據(jù)類型復(fù)數(shù)復(fù)數(shù)的定義： 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分 | e2 是復(fù)數(shù)的虛數(shù)部分 ADT Complex 基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部 分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( &Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。 GetIm

11、ag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。 Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1, z2 的 和值。 ADT Complex假設(shè):z1和z2是上述定義的復(fù)數(shù)則 Add(z1, z2, z3) 操作的結(jié)果z3 = z1 + z2即為用戶企求的結(jié)果ADT 有兩個(gè)重要特征:數(shù)據(jù)抽象數(shù)據(jù)抽象 用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征本質(zhì)的特征、其所能完成的其所能完成的功能功能以及它和外部用戶的接口外部用戶的接口（即外界外界使用它的方法使用它的方法）。

12、數(shù)據(jù)封裝數(shù)據(jù)封裝 將實(shí)體的外部特性和其內(nèi)部外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。其中：D 是數(shù)據(jù)對(duì)象； S 是 D 上的關(guān)系集； P 是對(duì) D 的基本操作集。 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名基本操作名（參數(shù)表） 初始條件：初始條件：初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果

13、描述 賦值參數(shù)賦值參數(shù) 只為操作提供輸入值。引用參數(shù)引用參數(shù) 以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)固有數(shù)據(jù)類型類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)。typedef struct float realpart； float imagpart；complex；/ -存

14、儲(chǔ)結(jié)構(gòu)的定義存儲(chǔ)結(jié)構(gòu)的定義/ -基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明void Assign( complex &Z, float realval, float imagval )；/ 構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) / realval 和 imagval 的值float GetReal( cpmplex Z )； / 返回復(fù)數(shù) Z 的實(shí)部值float Getimag( cpmplex Z )； / 返回復(fù)數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2

15、 的和 / -基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 1.3 1.3 算法和算法的衡量算法和算法的衡量一、算法一、算法二、算法設(shè)計(jì)的原則二、算法設(shè)計(jì)的原則三、算法效率的衡量方法和準(zhǔn)則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求四、算法的存儲(chǔ)空間需求 算法算法是為了解決某類

16、問題而規(guī)定的一個(gè)有限長的操作序列操作序列。一個(gè)算法必須滿足以下五五個(gè)重要特性特性：1 1有窮性有窮性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出一、算法一、算法1 1有窮性有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間有限時(shí)間內(nèi)完成。 2 2確定性確定性 對(duì)于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且并且在任何條件下，算法都只有一在任何條件下，算法都只有一條執(zhí)行路徑。條執(zhí)行路徑。3 3可行性可行性 算法中的所有操作都必須足夠基本，都

17、可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4 4有輸入有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。 5 5有輸出有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。二、算法設(shè)計(jì)的原則二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求1 1正確性正確性 首先，首先，算法應(yīng)當(dāng)滿足滿足以特定的“規(guī)格說明規(guī)格說明”方式給出的需求需求。其次，其次，對(duì)算

18、法是否“正確正確”的的理解可以有以下四個(gè)層次四個(gè)層次：a a程序中不含語法錯(cuò)誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械蟪绦驅(qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；2. . 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易易于于人的理解理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3健壯性健壯性 當(dāng)輸入的數(shù)據(jù)非法非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處

19、理進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出處理出錯(cuò)的方法錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4.高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。三、算法效率的衡量方法和準(zhǔn)則三、算法效率的衡量方法和準(zhǔn)則通常有兩種兩種衡量算法效率的方法: 事后統(tǒng)計(jì)法事后統(tǒng)計(jì)法事前分析估算法事前分析估算法缺點(diǎn)：缺點(diǎn)：1必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì)和算法執(zhí)行時(shí)間時(shí)間相關(guān)的因素因素：1 1算法算法選用的策略的策略2

20、2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言語言4 4編譯編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量的質(zhì)量5 5計(jì)算機(jī)計(jì)算機(jī)執(zhí)行指令的速度的速度 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度l算法中包含簡單操作的次數(shù)，在計(jì)算機(jī)上所運(yùn)行的時(shí)間算法中包含簡單操作的次數(shù)，在計(jì)算機(jī)上所運(yùn)行的時(shí)間l語句頻度：語句重復(fù)執(zhí)行的次數(shù)語句頻度：語句重復(fù)執(zhí)行的次數(shù) 所有語句頻度之和記做所有語句頻度之和記做T (n)，它是該算法所求解的問，它是該算法所求解的問題規(guī)模題規(guī)模n的函數(shù)。的函數(shù)。當(dāng)當(dāng)n- 時(shí)時(shí)，T(n)的數(shù)量級(jí)稱為漸近時(shí)的數(shù)量級(jí)稱為漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。記做：間復(fù)雜度，簡稱時(shí)間復(fù)雜度。記做：T(n)=O(f(n) 我們總是

21、考慮在最壞情況下的時(shí)間復(fù)雜度，以保證算我們總是考慮在最壞情況下的時(shí)間復(fù)雜度，以保證算法的運(yùn)行時(shí)間不會(huì)比它更長（最壞情況下估算算法執(zhí)行時(shí)法的運(yùn)行時(shí)間不會(huì)比它更長（最壞情況下估算算法執(zhí)行時(shí)間的一個(gè)上界）間的一個(gè)上界） 一個(gè)特定算法的一個(gè)特定算法的“運(yùn)行工作量運(yùn)行工作量”的大小，只依賴于的大小，只依賴于問問題的規(guī)模題的規(guī)模（通常用整數(shù)量（通常用整數(shù)量n表示），或者說，它是表示），或者說，它是問題規(guī)問題規(guī)模的函數(shù)模的函數(shù)。與待處理數(shù)據(jù)的初態(tài)無關(guān)。與待處理數(shù)據(jù)的初態(tài)無關(guān)。 一個(gè)特定算法的算法的“運(yùn)行工作量運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)是問題規(guī)模的函數(shù)。 假如，隨著問題規(guī)模 n 的增長，算法執(zhí)行時(shí)間的增長率和算法執(zhí)行時(shí)間的增長率和 f(n) 的增長的增長率相同率相同，則可記作：T (n) = O(f(n)稱稱T (n) 為算法的為算法的(漸近)