數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的標(biāo)識(shí)課件

1課程介紹教材：

《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版）

嚴(yán)蔚敏、吳偉民編清華大學(xué)出版社

學(xué)時(shí)：48學(xué)時(shí)上機(jī)：48學(xué)時(shí)

學(xué)習(xí)方法：多思考、多練習(xí)課外2課程性質(zhì)及學(xué)習(xí)方法課程性質(zhì)：專(zhuān)業(yè)基礎(chǔ)課核心課程學(xué)習(xí)方法多思考、多練習(xí)多寫(xiě)程序多讀程序多上機(jī)少背書(shū)3第一章緒論1.1數(shù)據(jù)結(jié)構(gòu)的概念1.2抽象數(shù)據(jù)類(lèi)型1.3算法和算法分析

1.3.1算法

1.3.2算法描述

1.3.3算法性能分析與度量4

第一章緒論計(jì)算機(jī)科學(xué)是一門(mén)研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問(wèn)題：信息的表示信息的處理而信息的表示和處理又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫(xiě)出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門(mén)課所要研究的問(wèn)題。51.1數(shù)據(jù)結(jié)構(gòu)的概念1.1.1

為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

眾所周知，計(jì)算機(jī)的程序是對(duì)信息進(jìn)行加工處理。在大多數(shù)情況下，這些信息并不是沒(méi)有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個(gè)例子。例1、電話號(hào)碼查詢系統(tǒng)設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒(méi)有這個(gè)人，則該算法也能夠給出報(bào)告沒(méi)有這個(gè)人的標(biāo)志。6

算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)應(yīng)的電話號(hào)碼，或者說(shuō)依賴于名字和其電話號(hào)碼的結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。上述的問(wèn)題是一種數(shù)據(jù)結(jié)構(gòu)問(wèn)題?？蓪⒚趾蛯?duì)應(yīng)的電話號(hào)碼設(shè)計(jì)成：二維數(shù)組、表結(jié)構(gòu)、向量。假定名字和其電話號(hào)碼邏輯上已安排成N元向量的形式，它的每個(gè)元素是一個(gè)數(shù)對(duì)(ai，bi)，1≤i≤n

數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類(lèi)型所定義的各種運(yùn)算的算法。7除電話號(hào)碼自動(dòng)查號(hào)系統(tǒng)外，還有許多諸如此類(lèi)的問(wèn)題，如：學(xué)生信息檢索系統(tǒng)

、考試查分系統(tǒng)、倉(cāng)庫(kù)庫(kù)存管理系統(tǒng)等。在這類(lèi)文檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種簡(jiǎn)單的線性關(guān)系，這類(lèi)數(shù)學(xué)模型可稱(chēng)為線性的數(shù)據(jù)結(jié)構(gòu)。

學(xué)生信息檢索系統(tǒng)：當(dāng)我們需要查找某個(gè)學(xué)生的有關(guān)情況的時(shí)候；或者想查詢某個(gè)專(zhuān)業(yè)或年級(jí)的學(xué)生的有關(guān)情況的時(shí)候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫(xiě)了相關(guān)程序，就可以實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)檢索。由此，可以在學(xué)生信息檢索系統(tǒng)中建立一張按學(xué)號(hào)順序排列的學(xué)生信息表和分別按姓名、專(zhuān)業(yè)、年級(jí)順序排列的索引表，如圖1.1所示。由這四張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主要操作便是按照某個(gè)特定要求（如給定姓名）對(duì)學(xué)生信息文件進(jìn)行查詢。8學(xué)生信息檢索系統(tǒng)：

學(xué)號(hào)

姓名性別專(zhuān)業(yè)年級(jí)980001吳承志

男計(jì)算機(jī)科學(xué)與技術(shù)

98級(jí)

980002李淑芳

女信息與計(jì)算科學(xué)

98級(jí)

990301劉

麗

女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)

99級(jí)

990302張會(huì)友

男信息與計(jì)算科學(xué)99級(jí)

990303石寶國(guó)

男計(jì)算機(jī)科學(xué)與技術(shù)99級(jí)

000801何文穎

女計(jì)算機(jī)科學(xué)與技術(shù)2000級(jí)

000802趙勝利

男數(shù)學(xué)與應(yīng)用數(shù)學(xué)

2000級(jí)

000803崔文靖

男信息與計(jì)算科學(xué)

2000級(jí)

010601劉

麗

女計(jì)算機(jī)科學(xué)與技術(shù)2001級(jí)

010602魏永鳴

男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級(jí)

（a）學(xué)生信息表

9崔文靖

8何文穎

6李淑芳

2劉

麗

3，9石寶國(guó)

5魏永鳴

10吳承志

1趙勝利

7張會(huì)有

4（b）姓名索引表

計(jì)算機(jī)科學(xué)與技術(shù)

1，5，6，9信息與計(jì)算科學(xué)

2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)

3，7，102000級(jí)

6，7，82001級(jí)

9，1098級(jí)

1，2，399級(jí)

4，5

（c）專(zhuān)業(yè)索引表

（d）年級(jí)索引表

線形結(jié)構(gòu)10例2、八皇后問(wèn)題。

在八皇后問(wèn)題中，處理過(guò)程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開(kāi)始，一步步地進(jìn)行試探，每試探一步形成一個(gè)新的狀態(tài)，整個(gè)試探過(guò)程形成了一棵隱含的狀態(tài)樹(shù)。如圖1.2所示（為了描述方便，將八皇后問(wèn)題簡(jiǎn)化為四皇后問(wèn)題）?；厮莘ㄇ蠼膺^(guò)程實(shí)質(zhì)上就是一個(gè)遍歷狀態(tài)樹(shù)的過(guò)程。在這個(gè)問(wèn)題中所出現(xiàn)的樹(shù)也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計(jì)算的問(wèn)題中。

11圖1.2四皇后問(wèn)題中隱含的狀態(tài)樹(shù)

樹(shù)型結(jié)構(gòu)12例3教學(xué)計(jì)劃編排問(wèn)題一個(gè)教學(xué)計(jì)劃包含許多課程，在教學(xué)計(jì)劃包含的許多課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒(méi)有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個(gè)課程之間的次序關(guān)系可用一個(gè)稱(chēng)作圖的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，如圖1.3所示。有向圖中的每個(gè)頂點(diǎn)表示一門(mén)課程，如果從頂點(diǎn)vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先于課程j進(jìn)行。

13

（a）計(jì)算機(jī)專(zhuān)業(yè)的課程設(shè)置

14圖1.3教學(xué)計(jì)劃編排問(wèn)題的數(shù)據(jù)結(jié)構(gòu)圖型結(jié)構(gòu)

（b）表示課程之間優(yōu)先關(guān)系的有向圖

15

由以上幾個(gè)例子可以直接地認(rèn)為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的類(lèi)型。

由以上幾個(gè)例子可見(jiàn)，描述這類(lèi)非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)、圖之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。因此，可以說(shuō)數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計(jì)算機(jī)處理對(duì)象的特性，將實(shí)際問(wèn)題中所涉及的處理對(duì)象在計(jì)算機(jī)中表示出來(lái)并對(duì)它們進(jìn)行處理。與此同時(shí)，通過(guò)算法訓(xùn)練來(lái)提高思維能力，通過(guò)程序設(shè)計(jì)的技能訓(xùn)練來(lái)促進(jìn)綜合應(yīng)用能力和素質(zhì)的提高。

161.1.2有關(guān)概念和術(shù)語(yǔ)

數(shù)據(jù)（Data）：是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。計(jì)算機(jī)科學(xué)中，所謂數(shù)據(jù)就是計(jì)算機(jī)加工處理的對(duì)象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。

數(shù)據(jù)元素（DataElement）：是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱(chēng)為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。

數(shù)據(jù)對(duì)象（DataObject）或數(shù)據(jù)元素類(lèi)（DataElementClass）：是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個(gè)具體問(wèn)題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對(duì)象（數(shù)據(jù)元素類(lèi)），數(shù)據(jù)元素是數(shù)據(jù)元素類(lèi)的一個(gè)實(shí)例。例、整數(shù)的數(shù)據(jù)對(duì)象是{…-3，-2，-1，0，1，2，3，…}數(shù)據(jù)結(jié)構(gòu)（DataStructure）：指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問(wèn)題中，數(shù)據(jù)元素之間都不會(huì)是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱(chēng)為結(jié)構(gòu)。

17據(jù)數(shù)據(jù)元素間關(guān)系不同特性，通常有下列四類(lèi)基本結(jié)構(gòu)：

集合結(jié)構(gòu)

線形結(jié)構(gòu)樹(shù)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通?？梢圆捎靡粋€(gè)二元組來(lái)表示。

18數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：Data_Structure＝（D，R）其中：D是數(shù)據(jù)元素的有限集

R是D上關(guān)系的有限集

19數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。我們研究數(shù)據(jù)結(jié)構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的操作，為此還需要研究如何在計(jì)算機(jī)中表示一個(gè)數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的標(biāo)識(shí)（又稱(chēng)映像）稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)，或稱(chēng)存儲(chǔ)結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)方法:是用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。

鏈?zhǔn)酱鎯?chǔ)方法:在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針，用此指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針類(lèi)型來(lái)實(shí)現(xiàn)。

除了通常采用的順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法外，有時(shí)為了查找的方便還采用索引存儲(chǔ)方法和散列存儲(chǔ)方法。

201.1.3：數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容

方面層次數(shù)據(jù)表示數(shù)據(jù)處理抽象

邏輯結(jié)構(gòu)

基本運(yùn)算實(shí)現(xiàn)

存儲(chǔ)結(jié)構(gòu)

算法評(píng)價(jià)

不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析211.2抽象數(shù)據(jù)類(lèi)型

1.2.1數(shù)據(jù)類(lèi)型:在一種程序設(shè)計(jì)語(yǔ)言中，變量所具有的數(shù)據(jù)種類(lèi)。

類(lèi)型顯式地或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能的取值范圍，以及在這些值上允許進(jìn)行的操作。數(shù)據(jù)類(lèi)型（DataType）是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱(chēng)。例1、在FORTRAN語(yǔ)言中：變量的數(shù)據(jù)類(lèi)型有整型、實(shí)型、和復(fù)數(shù)型例2、在C語(yǔ)言中，數(shù)據(jù)類(lèi)型：基本類(lèi)型和構(gòu)造類(lèi)型基本類(lèi)型：整型、浮點(diǎn)型、字符型構(gòu)造類(lèi)型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義221.2.2抽象數(shù)據(jù)類(lèi)型

是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類(lèi)型一般可以由元素、關(guān)系及操作三種要素來(lái)定義。

抽象數(shù)據(jù)類(lèi)型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。用三元組描述如下：（Ｄ，Ｓ，Ｐ）抽象數(shù)據(jù)類(lèi)型的特征是使用與實(shí)現(xiàn)相分離，實(shí)行封裝和信息隱蔽。就是說(shuō)，在抽象數(shù)據(jù)類(lèi)型設(shè)計(jì)時(shí)，把類(lèi)型的定義與其實(shí)現(xiàn)分離開(kāi)來(lái)。

231.3算法和算法分析

1.3.1算法特性

算法（Algorithm）是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。算法的五個(gè)特征：有窮性。一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。確定性。算法的每一步必須有確切的定義，無(wú)二義性。算法的執(zhí)行對(duì)應(yīng)著的相同的輸入僅有唯一的一條路經(jīng)。可行性（有效性）。算法中的每一步都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次執(zhí)行得以實(shí)現(xiàn)。輸入。一個(gè)算法具有零個(gè)或多個(gè)輸入，這些輸入取自特定的數(shù)據(jù)對(duì)象集合。輸出。一個(gè)算法具有一個(gè)或多個(gè)輸出，這些輸出是同輸入之間存在某種特定的關(guān)系的量。

24算法設(shè)計(jì)的要求

評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn):

(1)

正確性(Correctness)

算法應(yīng)滿足具體問(wèn)題的需求，預(yù)先規(guī)定的功能和性能要求。

(2)

可讀性(Readability)

算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。

(3)

健狀性(Robustness)

算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。

(4)效率與存儲(chǔ)量需求

效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般，這兩者與問(wèn)題的規(guī)模有關(guān)。251.3.3算法性能分析與度量

可以從一個(gè)算法的時(shí)間復(fù)雜度與空間復(fù)雜度來(lái)評(píng)價(jià)算法的優(yōu)劣。

將一個(gè)算法轉(zhuǎn)換成程序并在計(jì)算機(jī)上執(zhí)行時(shí)，其運(yùn)行所需要的時(shí)間取決于下列因素：硬件的速度

書(shū)寫(xiě)程序的語(yǔ)言

編譯程序所生成目標(biāo)代碼的質(zhì)量

問(wèn)題的規(guī)模

26⒈時(shí)間復(fù)雜度

一個(gè)算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行時(shí)間取決于兩者的綜合效果。為了便于比較同一問(wèn)題的不同的算法，通常的做法是：從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)。

定義（大Ο記號(hào)）：如果存在兩個(gè)正常數(shù)c和n0，使得對(duì)所有的n，n≥n0，有：f(n)≤cg(n)則有：f(n)＝

Ο(g(n))指程序運(yùn)行從開(kāi)始到結(jié)束所需要的時(shí)間。

例:一個(gè)程序的實(shí)際執(zhí)行時(shí)間為T(mén)(n)＝2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。

使用大Ο記號(hào)表示的算法的時(shí)間復(fù)雜度，稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度（AsymptoticComplexity）。

27一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，算法的時(shí)間量度記作：T(n)=O(f(n))例１、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];}由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為:n×n×n=n3時(shí)間復(fù)雜度為：T(n)=O(n3)頻度：是指語(yǔ)句重復(fù)執(zhí)行的次數(shù)28例２{++x;s=0;}分析：將x自增看成是基本操作，則語(yǔ)句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)；如果將s=0也看成是基本操作，則語(yǔ)句頻度為２，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階。例３、for(I=1;I<=n;++I){++x;s+=x;}語(yǔ)句頻度為：2n其時(shí)間復(fù)雜度為：O(n)即時(shí)間復(fù)雜度為線性階例４、for(I=1;I<=n;++I)

for(j=1;j<=n;++j){++x;s+=x;}語(yǔ)句頻度為：2n2其時(shí)間復(fù)雜度為：O(n2)，即時(shí)間復(fù)雜度為平方階。29定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)證略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}語(yǔ)句頻度為：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴時(shí)間復(fù)雜度為O(n2)即此算法的時(shí)間復(fù)雜度為平方階.一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來(lái)限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)二次多項(xiàng)式來(lái)限界。30通常用Ο(1)表示常數(shù)計(jì)算時(shí)間。常見(jiàn)的漸進(jìn)時(shí)間復(fù)雜度有:Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)這幾種計(jì)算算法時(shí)間的多項(xiàng)式是