1、第1章 緒論,第1章 緒論,背景：1946年世界上第一臺(tái)計(jì)算機(jī)誕生，至今已有60多年的歷史。在這期間，計(jì)算機(jī)的發(fā)展和應(yīng)用已經(jīng)滲透到了人類社會(huì)的各個(gè)領(lǐng)域，計(jì)算機(jī)加工和處理的對(duì)象也從純粹的數(shù)值發(fā)展到了字符、圖像、聲音等各種具有一定結(jié)構(gòu)的數(shù)據(jù)。為了更好地設(shè)計(jì)程序，以提高計(jì)算機(jī)在解決復(fù)雜問(wèn)題時(shí)的處理效率，研究數(shù)據(jù)的特性和數(shù)據(jù)之間存在的關(guān)系就顯得至關(guān)重要?！皵?shù)據(jù)結(jié)構(gòu)”作為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中的一門專業(yè)基礎(chǔ)課，它專門研究數(shù)據(jù)的特性和數(shù)據(jù)之間存在的關(guān)系，以及如何在計(jì)算機(jī)中有效地存取數(shù)據(jù)和處理數(shù)據(jù)。因此，“數(shù)據(jù)結(jié)構(gòu)”是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)和大型應(yīng)用程序的重要基礎(chǔ)，它也是介于數(shù)學(xué)、計(jì)算機(jī)硬

2、件和計(jì)算機(jī)軟件之間的一門核心課程，并將隨著人類社會(huì)的各個(gè)領(lǐng)域中計(jì)算問(wèn)題的不斷深入研究而繼續(xù)發(fā)展。,1.1 什么是數(shù)據(jù)結(jié)構(gòu),在計(jì)算機(jī)發(fā)展的初期，人們使用計(jì)算機(jī)主要用于科學(xué)計(jì)算所涉及的數(shù)據(jù)對(duì)象比較單純，程序設(shè)計(jì)以算法為中心，而無(wú)需重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，非數(shù)值計(jì)算問(wèn)題顯得越來(lái)越重要。這類問(wèn)題涉及的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，無(wú)法用數(shù)學(xué)方程加以描述。為了編寫出一個(gè)好的程序，必須分析待處理的對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系，以便設(shè)計(jì)出合理的數(shù)據(jù)結(jié)構(gòu)。,當(dāng)我們需要查找某個(gè)學(xué)生的有關(guān)情況的時(shí)候，或者想查詢某個(gè)專業(yè)或年級(jí)的學(xué)生的有關(guān)情況的時(shí)候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某

3、種算法編寫了相關(guān)程序，就可以實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)檢索。由此，可以在學(xué)生信息檢索系統(tǒng)中建立一張按學(xué)號(hào)順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級(jí)順序排列的索引表，如圖1.1所示。由這4張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型。,例11 學(xué)生信息檢索自動(dòng)化問(wèn)題。,圖1.1 數(shù)學(xué)模型- - -線性表,在一個(gè)棋盤上放置4個(gè)皇后，使得任意兩個(gè)皇后在行、列和斜方向上都不在一條線上。在四皇后問(wèn)題中，處理過(guò)程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開(kāi)始，一步步地進(jìn)行試探，每試探一步就形成一個(gè)新的狀態(tài)，整個(gè)試探過(guò)程形成了一棵隱含的

4、狀態(tài)樹(shù)，如圖1.2所示 。,例12 四皇后問(wèn)題,圖1.2 四皇后問(wèn)題的狀態(tài)樹(shù),例1-3 教學(xué)計(jì)劃編排問(wèn)題,一個(gè)教學(xué)計(jì)劃包含許多課程，在這些課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒(méi)有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個(gè)課程之間的次序關(guān)系可用一個(gè)稱作圖的數(shù)據(jù)結(jié)構(gòu)表示，如圖1.3所示。有向圖中的每個(gè)頂點(diǎn)表示一門課程，如果從頂點(diǎn)vi到vj之間存在有向邊 ，則表示課程i必須先于課程j進(jìn)行。,C1,C9,C4,C2,C12,C10,C11,C5,C3,C6,C7,C8,圖1.3 教學(xué)計(jì)劃圖,由上述例子可見(jiàn)，描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而

5、是諸如表、樹(shù)和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，簡(jiǎn)單來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的課程。,1.2 基本概念,基本概念 （1）數(shù)據(jù)：信息的載體，是客觀事物的符號(hào)表示。數(shù)據(jù)能夠被計(jì)算機(jī)識(shí)別、存取和處理，數(shù)據(jù)也是計(jì)算機(jī)程序加工和處理的“原料”。例如，實(shí)數(shù)、字符串、圖像和聲音等。 （2）數(shù)據(jù)項(xiàng)：具有獨(dú)立的含義的最小標(biāo)識(shí)單位。例如，字段、域、屬性等。 （3）數(shù)據(jù)元素：數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。例11學(xué)生信息表中的學(xué)生信息為一個(gè)數(shù)據(jù)元素，而學(xué)生信息中的每一項(xiàng)（如姓名、專業(yè)等）為一個(gè)數(shù)據(jù)項(xiàng)。,（4）數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合

6、，是數(shù)據(jù)的一個(gè)子集。例如，26個(gè)英文字母構(gòu)成的字符集合，一個(gè)學(xué)校全體學(xué)生或教師構(gòu)成的學(xué)生集合或教師集合等。 （5）數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。 數(shù)據(jù)結(jié)構(gòu)的形式化定義通常用一個(gè)二元組Data_Structure=(D, R)來(lái)表示，其中，D是數(shù)據(jù)元素的有限集（也即數(shù)據(jù)對(duì)象），R是D上關(guān)系的有限集。,1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu): 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素以及它們相互之間的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有4類邏輯結(jié)構(gòu)： 集合，集合的邏輯結(jié)構(gòu)中所有數(shù)據(jù)元素都屬于同一個(gè)集合，所有數(shù)據(jù)元素雜

7、亂無(wú)章地聚集在一起，各個(gè)數(shù)據(jù)元素之間無(wú)任何聯(lián)系； 線性結(jié)構(gòu)，邏輯結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一一對(duì)應(yīng)的關(guān)系，各個(gè)數(shù)據(jù)元素之間通常有嚴(yán)格的先后次序關(guān)系； 樹(shù)狀結(jié)構(gòu)，邏輯結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系，各個(gè)數(shù)據(jù)元素之間通常有嚴(yán)格的層次關(guān)系； 圖狀結(jié)構(gòu)，邏輯結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，各個(gè)數(shù)據(jù)元素之間均可能存在相互聯(lián)系。,4類基本邏輯結(jié)構(gòu)示意圖,圖1.4 4類基本邏輯結(jié)構(gòu)的示意圖,（c）樹(shù)狀結(jié)構(gòu),（a）集合結(jié)構(gòu),（b）線性結(jié)構(gòu),（d）圖狀結(jié)構(gòu),根據(jù)數(shù)據(jù)元素（結(jié)點(diǎn)）之間的相鄰關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)還可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類： 線性結(jié)構(gòu)的邏輯特征是，若結(jié)構(gòu)是非空集，則有且僅有一個(gè)

8、開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前驅(qū)結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。 線性表是一個(gè)典型的線性結(jié)構(gòu)，棧、隊(duì)列和串等都是線性結(jié)構(gòu)； 非線性結(jié)構(gòu)的邏輯特征是，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。 樹(shù)和圖都是非線性結(jié)構(gòu)。,圖示法表示數(shù)據(jù)的邏輯結(jié)構(gòu),對(duì)數(shù)據(jù)元素之間關(guān)系的描述是數(shù)據(jù)的邏輯結(jié)構(gòu)，它可形式地用一個(gè)二元組表示為K=(D, R)，其中，D是由有限個(gè)結(jié)點(diǎn)所構(gòu)成的集合，R是由有限個(gè)關(guān)系所構(gòu)成的集合。有時(shí)為了直觀起見(jiàn)，也用圖示法來(lái)表示數(shù)據(jù)的邏輯結(jié)構(gòu)。 邏輯結(jié)構(gòu)與使用的計(jì)算機(jī)無(wú)關(guān)。例如，一批數(shù)據(jù)的邏輯結(jié)構(gòu)K=(D, R)，其中，D=d1, d2, , d9，R=,，則該批數(shù)據(jù)的邏輯

9、結(jié)構(gòu)如圖1.5所示。對(duì)于R中包含多種關(guān)系的情況，也可用類似的方法描述。,圖1.5 數(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)可以看作是從具體問(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í)（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲(chǔ)結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。,1.2.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）是指數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示，它包括數(shù)據(jù)元素的表示和

10、關(guān)系的表示。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有以下4種。 順序存儲(chǔ)。該存儲(chǔ)方法把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。該方法通常借助于高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)描述。 鏈?zhǔn)酱鎯?chǔ)。該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)之間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該方法通常借助于高級(jí)程序設(shè)計(jì)語(yǔ)言中的指針類型來(lái)描述。 索引存儲(chǔ)。該方法通常在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還要建立附加的索引表。 散列存儲(chǔ)。該方法根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。,數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）是密

11、切相關(guān)的兩個(gè)方面，任何算法的設(shè)計(jì)都取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實(shí)現(xiàn)則依賴于所采用的存儲(chǔ)結(jié)構(gòu)。 1.2.3 數(shù)據(jù)的運(yùn)算 數(shù)據(jù)的運(yùn)算是對(duì)數(shù)據(jù)施加的操作。數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。在數(shù)據(jù)結(jié)構(gòu)中，運(yùn)算不僅是加、減、乘、除等運(yùn)算，大多數(shù)的運(yùn)算都涉及算法的實(shí)現(xiàn)問(wèn)題。算法的實(shí)現(xiàn)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的。,1.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型,數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值的集合上的一組操作的總稱，通常它可看作是高級(jí)程序設(shè)計(jì)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 在高級(jí)程序設(shè)計(jì)語(yǔ)言中，數(shù)據(jù)類型可分為兩類： 1、原子類型。原子類型的值是不可分解的。比如，C語(yǔ)言中的整型、

12、字符型、浮點(diǎn)型、雙精度型等基本類型，分別用保留字int、char、float、double標(biāo)識(shí)。 2、結(jié)構(gòu)類型是由若干成分按某種結(jié)構(gòu)組成的，是可分解的，并且它的成分既可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。,抽象數(shù)據(jù)類型（abstract data type，ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)，也即，不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不會(huì)影響其外部的使用。 抽象數(shù)據(jù)類型可表示為一個(gè)三元組（D, R, P），其中，D是數(shù)據(jù)對(duì)象，R是D上的關(guān)系集，P是對(duì)D的基本操作集。本書采用以下格式定義抽象

13、數(shù)據(jù)類型： ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)集合： 數(shù)據(jù)關(guān)系： 數(shù)據(jù)操作： ADT 抽象數(shù)據(jù)類型名 其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為： 數(shù)據(jù)操作名(參數(shù)表) 輸入： 返回結(jié)果：,1.4 算法和算法分析,算法（algorithm）：為了解決某一類問(wèn)題而設(shè)計(jì)的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下5個(gè)重要特性。 有窮性。算法對(duì)于合法的任意輸入值，在執(zhí)行有限步之后一定能結(jié)束。 確定性。算法中的每一個(gè)操作必須有確切的含義，無(wú)二義性，并在任何條件下，算法都只有一條執(zhí)行路徑。 可行性。算法中的所有操作都可通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算有限次地實(shí)現(xiàn)。 輸入。算法具有0或多個(gè)輸入，這些輸

14、入為一組特定的數(shù)據(jù)對(duì)象集合。 輸出。算法具有一個(gè)或多個(gè)輸出，它是一組與“輸入”有確定關(guān)系的量值。,1.4.1 算法的描述,算法可以使用各種不同的方法來(lái)描述： 最簡(jiǎn)單的方法是使用自然語(yǔ)言。用自然語(yǔ)言來(lái)描述算法的優(yōu)點(diǎn)是簡(jiǎn)單且便于人們對(duì)算法的閱讀。缺點(diǎn)是不夠嚴(yán)謹(jǐn)。 可以使用程序流程圖、NS圖等算法描述工具。其特點(diǎn)是描述過(guò)程簡(jiǎn)潔、明了。用以上兩種方法描述的算法不能直接在計(jì)算機(jī)上執(zhí)行，若要將它轉(zhuǎn)換成可執(zhí)行的程序，還有一個(gè)編程的問(wèn)題。 可以直接使用某種程序設(shè)計(jì)語(yǔ)言來(lái)描述算法，不過(guò)直接使用程序設(shè)計(jì)語(yǔ)言并不容易，而且不太直觀，常常需要借助于注釋才能使人看明白。 為了解決理解與執(zhí)行這兩者之間的矛盾，人們常常使用

15、一種稱為偽碼語(yǔ)言的描述方法來(lái)進(jìn)行算法描述。,用流程圖表示算法,流程圖是用一些圖框來(lái)表示各種操作 用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點(diǎn),注釋框,m被2整除,是,否,開(kāi)始,判斷一個(gè)數(shù)是否偶數(shù)的算法,輸入m的值,輸出m是偶數(shù),輸出m不是偶數(shù),結(jié)束,用N-S流程圖表示算法,N-S流程圖用以下的流程圖符號(hào)：,順序結(jié)構(gòu),選擇結(jié)構(gòu),循環(huán)結(jié)構(gòu),判斷一個(gè)數(shù)是否偶數(shù)的算法,1.4.2 算法設(shè)計(jì)的要求,正確性（correctness）。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的4個(gè)要求：1）程序不含語(yǔ)法錯(cuò)誤；2）程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；3）程序?qū)τ?/p>

16、精心選擇的典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能得出滿足規(guī)格說(shuō)明要求的結(jié)果；4）程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說(shuō)明要求的結(jié)果。 可讀性（readability）。算法應(yīng)有助于人們閱讀、理解和調(diào)試，晦澀難懂的算法可能隱藏較多的錯(cuò)誤，難以調(diào)試和修改。 穩(wěn)健性（robustness）。當(dāng)輸入不合法的數(shù)據(jù)時(shí)，算法能夠做出適當(dāng)?shù)姆磻?yīng)或處理，不至于產(chǎn)生莫名其妙的結(jié)果。同時(shí)，處理出錯(cuò)的方法應(yīng)該是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，并終止程序的執(zhí)行，以便在更高的抽象層次上進(jìn)行處理。 時(shí)空效率（efficiency）。要求算法執(zhí)行的時(shí)間應(yīng)該盡可能短、算法執(zhí)行過(guò)程中占用的存儲(chǔ)空間應(yīng)該盡可能少。時(shí)空要求與求

17、解問(wèn)題的規(guī)模有關(guān)，兩者通常相互矛盾，因此，應(yīng)在它們之間進(jìn)行平衡。,1.4.3算法分析,算法分析的兩個(gè)主要方面是分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度，主要考察算法的時(shí)間效率和空間效率，以便比較和改進(jìn)算法。通常，在算法的運(yùn)算空間較為充裕的情況下，更多地關(guān)注算法的時(shí)間復(fù)雜度。 1、時(shí)間復(fù)雜度 算法執(zhí)行的時(shí)間可通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上從開(kāi)始運(yùn)行到結(jié)束運(yùn)行所消耗的時(shí)間來(lái)度量，也就是算法中每條語(yǔ)句的執(zhí)行時(shí)間之和。 估算運(yùn)行時(shí)間有兩種可行的辦法。 第一種是操作計(jì)數(shù)法，首先選擇一種或多種基本操作，然后確定這些操作分別執(zhí)行了多少次。一般情況下，操作的執(zhí)行次數(shù)和包含它的語(yǔ)句的頻度相同。語(yǔ)句的頻度指的是該語(yǔ)句

18、重復(fù)執(zhí)行的次數(shù)。 第二種是步驟計(jì)數(shù)法，確定算法總的執(zhí)行步數(shù)，要統(tǒng)計(jì)算法或函數(shù)中的所有時(shí)間開(kāi)銷。,算法的時(shí)間復(fù)雜度分析,我們選用操作計(jì)數(shù)法，這種方法是否成功取決于識(shí)別基本操作的能力。 算法中基本操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的函數(shù)T(n)。 許多時(shí)候要精確地計(jì)算T(n)是困難的，我們引入漸近時(shí)間復(fù)雜度在數(shù)量上估計(jì)算法的執(zhí)行時(shí)間。一般而言，算法中基本操作的頻度是問(wèn)題規(guī)模n（如算法所處理的矩陣的階數(shù)，線性表的長(zhǎng)度）的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作T(n)=O(f(n)，它表示隨問(wèn)題規(guī)模n的增大，算法的執(zhí)行時(shí)間增長(zhǎng)率與f(n)的增長(zhǎng)率相同，稱為算法的漸近時(shí)間復(fù)雜度（asymptotic time c

19、omplexity），簡(jiǎn)稱時(shí)間復(fù)雜度。 一般定義為：當(dāng)且僅當(dāng)存在正整數(shù)c和n0，使得T(n) c f(n)對(duì)所有的n n0成立，則稱該算法的漸近時(shí)間復(fù)雜度為T(n)=O(f(n)。,例1-4 分析算法時(shí)間復(fù)雜度,下面是一個(gè)nn階矩陣A自乘得到B=AA的算法，試分析其時(shí)間復(fù)雜度。 int Ann； /全局?jǐn)?shù)組 void mtxmlt( ) int Bnn； /語(yǔ)句頻度 for (int i=0；in；i+) /n+1 for(int j=0；jn；j+) /n*(n+1) Bij=0； /n*n for(int k=0；kn；k+) /n*n*(n+1) Bij=Bij+Aik*Akj；/n*n*n ,時(shí)間復(fù)雜度T(n)=n+1+n(n+1)+nn+n2(n+1)+nnn=2n3+3n2+2n+1。當(dāng)n時(shí)，T(n) n3，故算法時(shí)間復(fù)雜度的數(shù)量級(jí)為O(n3)。 在需要大O表示的任何分析中，低階項(xiàng)