數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第一頁(yè)，共三十九頁(yè)，2022年，8月28日《數(shù)據(jù)結(jié)構(gòu)》課程是本科計(jì)算機(jī)專(zhuān)業(yè)的一門(mén)專(zhuān)業(yè)基礎(chǔ)課。它涉及在計(jì)算機(jī)中如何有效地表示數(shù)據(jù)，如何合理地組織數(shù)據(jù)和處理數(shù)據(jù)。還涉及初步的算法設(shè)計(jì)和算法性能分析技術(shù)。學(xué)好數(shù)據(jù)結(jié)構(gòu)課程，將為后續(xù)的專(zhuān)業(yè)課程，如數(shù)據(jù)庫(kù)系統(tǒng)、操作系統(tǒng)、編譯原理等，打下良好的知識(shí)基礎(chǔ)，而且還為軟件開(kāi)發(fā)和程序設(shè)計(jì)提供了必要的技能訓(xùn)練。課程概況第二頁(yè)，共三十九頁(yè)，2022年，8月28日課程教材和參考資料教材:數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）作者:嚴(yán)蔚敏吳偉民出版社:清華大學(xué)出版社參考書(shū)目：數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）作者:嚴(yán)蔚敏吳偉民清華大學(xué)出版社

數(shù)據(jù)結(jié)構(gòu)與算法分析,CliffordA.Shaffer著，張銘，劉曉丹譯。電子工業(yè)出版社。數(shù)據(jù)結(jié)構(gòu)（C++）殷人昆清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)（C++）劉大有數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與典型題解朱站立等西安電子交大數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析李春葆清華大學(xué)出版社必須熟練地掌握C語(yǔ)言程序設(shè)計(jì)與調(diào)試!第三頁(yè)，共三十九頁(yè)，2022年，8月28日第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)1.4算法和算法分析1.4.1算法1.4.2算法設(shè)計(jì)的要求1.4.3算法效率的度量1.4.4算法的存儲(chǔ)空間需求第四頁(yè)，共三十九頁(yè)，2022年，8月28日學(xué)習(xí)提要掌握本課程所涉及到的基本名詞、術(shù)語(yǔ)和概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系及性質(zhì)。了解抽象數(shù)據(jù)類(lèi)型的定義、表示和實(shí)現(xiàn)方法。理解算法設(shè)計(jì)的五個(gè)要素和基本要求；掌握算法效率的度量方法，著重學(xué)習(xí)算法的時(shí)間復(fù)雜度分析。掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。第五頁(yè)，共三十九頁(yè)，2022年，8月28日第1章緒論

目前，計(jì)算機(jī)已深入到社會(huì)生活的各個(gè)領(lǐng)域，其應(yīng)用已不再僅僅局限于科學(xué)計(jì)算，而更多的是用于控制，管理及數(shù)據(jù)處理等非數(shù)值計(jì)算領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。

這里面涉及到兩個(gè)問(wèn)題：信息的表示，信息的處理。信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著應(yīng)用問(wèn)題的不斷復(fù)雜，導(dǎo)致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問(wèn)題中的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門(mén)課所要研究的問(wèn)題。第六頁(yè)，共三十九頁(yè)，2022年，8月28日編寫(xiě)解決實(shí)際問(wèn)題的程序的一般過(guò)程：

如何用數(shù)據(jù)形式描述問(wèn)題?即由問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型;

問(wèn)題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系;

如何在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系?

處理問(wèn)題時(shí)需要對(duì)數(shù)據(jù)作何種運(yùn)算?

所編寫(xiě)的程序的性能是否良好?上面所列舉的問(wèn)題基本上由數(shù)據(jù)結(jié)構(gòu)這門(mén)課程來(lái)回答。計(jì)算機(jī)求解問(wèn)題的一般步驟第七頁(yè)，共三十九頁(yè)，2022年，8月28日1.1

數(shù)據(jù)結(jié)構(gòu)

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)中的一門(mén)綜合性專(zhuān)業(yè)基礎(chǔ)課。是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三者之間的一門(mén)核心課程，不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。第八頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)結(jié)構(gòu)的例子姓名電話號(hào)碼陳四…例1：電話號(hào)碼查詢(xún)系統(tǒng)

設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分別表示某人的名字和電話號(hào)碼。本問(wèn)題是一種典型的表格問(wèn)題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡(jiǎn)單的一對(duì)一的線性關(guān)系。表1-1

線性表結(jié)構(gòu)第九頁(yè)，共三十九頁(yè)，2022年，8月28日例2：磁盤(pán)目錄文件系統(tǒng)

磁盤(pán)根目錄下有很多子目錄及文件，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件，但每個(gè)子目錄只有一個(gè)父目錄，依此類(lèi)推：本問(wèn)題是一種典型的樹(shù)型結(jié)構(gòu)問(wèn)題，如圖1-1

，數(shù)據(jù)與數(shù)據(jù)成一對(duì)多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)—樹(shù)形結(jié)構(gòu)。圖1-1

樹(shù)形結(jié)構(gòu)第十頁(yè)，共三十九頁(yè)，2022年，8月28日例3：交通網(wǎng)絡(luò)圖

從一個(gè)地方到另外一個(gè)地方可以有多條路徑。本問(wèn)題是一種典型的網(wǎng)狀結(jié)構(gòu)問(wèn)題，數(shù)據(jù)與數(shù)據(jù)成多對(duì)多的關(guān)系，是一種非線性關(guān)系結(jié)構(gòu)。佛山惠州廣州中山東莞深圳珠海圖1-2

網(wǎng)狀結(jié)構(gòu)第十一頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)(Data)

：是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。

數(shù)據(jù)元素(DataElement)

：是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。

數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符集合C={‘A’,’B’,’C’,…}。1.2

基本概念和術(shù)語(yǔ)第十二頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱(chēng)為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類(lèi)型，如圖1-5所示。①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒(méi)有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。第十三頁(yè)，共三十九頁(yè)，2022年，8月28日③樹(shù)型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。圖1-5

四類(lèi)基本結(jié)構(gòu)圖第十四頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)結(jié)構(gòu)的形式定義是一個(gè)二元組：

Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例2：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)B=（K，R）

K={k1,k2,…,k9}R={<k1,k3>，<k1,k8>，<k2,k3>，<k2,k4>，<k2,k5>，<k3,k9>，<k5,k6>，<k8,k9>，<k9,k7>，<k4,k7>，<k4,k6>}

畫(huà)出這邏輯結(jié)構(gòu)的圖示，并確定那些是起點(diǎn)，那些是終點(diǎn)

數(shù)據(jù)結(jié)構(gòu)的形式定義第十五頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問(wèn)題方便而人為定義的關(guān)系，這種自然或人為定義的

“關(guān)系”稱(chēng)為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱(chēng)為邏輯結(jié)構(gòu)。第十六頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的表示。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針(pointer)，用該指針來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。第十七頁(yè)，共三十九頁(yè)，2022年，8月28日例：設(shè)有數(shù)據(jù)集合A={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲(chǔ)結(jié)構(gòu)。順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；

鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu)。在C語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類(lèi)型表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第十八頁(yè)，共三十九頁(yè)，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述

D_S=（D，S）存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算。1第十九頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)類(lèi)型(DataType)：指的是一個(gè)值的集合和定義在該值集上的一組操作的總稱(chēng)。數(shù)據(jù)類(lèi)型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念。在C語(yǔ)言中數(shù)據(jù)類(lèi)型有：基本類(lèi)型和構(gòu)造類(lèi)型。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類(lèi)型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類(lèi)型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。

數(shù)據(jù)類(lèi)型第二十頁(yè)，共三十九頁(yè)，2022年，8月28日

數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括：⑴建立(Create)一個(gè)數(shù)據(jù)結(jié)構(gòu)；⑵銷(xiāo)毀(Destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu)；⑶從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個(gè)數(shù)據(jù)元素；⑷把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中；⑸對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)(Access)；⑹對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改(Modify)；⑺對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(Sort)；⑻對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(Search)。

數(shù)據(jù)結(jié)構(gòu)的運(yùn)算第二十一頁(yè)，共三十九頁(yè)，2022年，8月28日

抽象數(shù)據(jù)類(lèi)型(AbstractDataType

，簡(jiǎn)稱(chēng)ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。

ADT的定義僅是一組邏輯特性描述，與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無(wú)關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。

ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。1.3

抽象數(shù)據(jù)類(lèi)型第二十二頁(yè)，共三十九頁(yè)，2022年，8月28日抽象數(shù)據(jù)類(lèi)型由基本的數(shù)據(jù)模型及定義在該模型上一組相關(guān)操作組成的。是邏輯特性的表示，與在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)細(xì)節(jié)無(wú)關(guān)。抽象數(shù)據(jù)類(lèi)型的基本特征：

(1)表示與實(shí)現(xiàn)分離是抽象數(shù)據(jù)類(lèi)型的第一個(gè)特征。使設(shè)計(jì)者在問(wèn)題分析時(shí)先抓住反映問(wèn)題本質(zhì)的東西，而避免陷入非本質(zhì)的細(xì)節(jié)。

(2)對(duì)數(shù)據(jù)和操作封裝是抽象數(shù)據(jù)類(lèi)型的第二個(gè)特征。對(duì)于兩個(gè)數(shù)據(jù)成員完全相同的數(shù)據(jù)類(lèi)型，如果它們具有不同的操作，那么它們可形成不同的抽象數(shù)據(jù)類(lèi)型。第二十三頁(yè)，共三十九頁(yè)，2022年，8月28日ADT的一般定義形式是：ADT抽象數(shù)據(jù)類(lèi)型名

{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類(lèi)型名

其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述。基本操作的定義是：<基本操作名>(<參數(shù)表>)初始條件：

<初始條件描述>操作結(jié)果：<操作結(jié)果描述>第二十四頁(yè)，共三十九頁(yè)，2022年，8月28日

初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件;若不滿足，則操作失敗，返回相應(yīng)的出錯(cuò)信息。

操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。課后仔細(xì)閱讀1.3節(jié)，并記住類(lèi)C語(yǔ)言的書(shū)寫(xiě)規(guī)范。第二十五頁(yè)，共三十九頁(yè)，2022年，8月28日

算法算法(Algorithm)：是對(duì)特定問(wèn)題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性①有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。②

確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。③可行性：一個(gè)算法是能行的。即算法描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。1.4

算法分析初步第二十六頁(yè)，共三十九頁(yè)，2022年，8月28日④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。一個(gè)算法可以用多種方法描述，主要有：使用自然語(yǔ)言描述；使用形式語(yǔ)言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述。

算法和程序是兩個(gè)不同的概念。一個(gè)計(jì)算機(jī)程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。算法必須可終止意味著不是所有的計(jì)算機(jī)程序都是算法。在本門(mén)課程的學(xué)習(xí)、作業(yè)練習(xí)、上機(jī)實(shí)踐等環(huán)節(jié)，算法都用類(lèi)C語(yǔ)言來(lái)描述。在上機(jī)實(shí)踐時(shí)，為了檢查算法是否正確，應(yīng)編寫(xiě)成完整的C語(yǔ)言程序。第二十七頁(yè)，共三十九頁(yè)，2022年，8月28日評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)①

正確性：算法應(yīng)滿足具體問(wèn)題的需求。②

可讀性：算法應(yīng)容易供人閱讀和交流。可讀性好的算法有助于對(duì)算法的理解和修改。③

健壯性：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。④效率與存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般地，這兩者與問(wèn)題的規(guī)模有關(guān)。

算法設(shè)計(jì)的要求第二十八頁(yè)，共三十九頁(yè)，2022年，8月28日

算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來(lái)度量。其方法通常有兩種：事后統(tǒng)計(jì)：計(jì)算機(jī)內(nèi)部進(jìn)行執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)。問(wèn)題：必須先運(yùn)行依據(jù)算法編制的程序；依賴(lài)軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒(méi)有實(shí)際價(jià)值。事前分析：求出該算法的一個(gè)時(shí)間界限函數(shù)。1.4.3

算法效率的度量第二十九頁(yè)，共三十九頁(yè)，2022年，8月28日與此相關(guān)的因素有：依據(jù)算法選用何種策略；問(wèn)題的規(guī)模；程序設(shè)計(jì)的語(yǔ)言；編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；機(jī)器執(zhí)行指令的速度；撇開(kāi)軟硬件等有關(guān)因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴(lài)于問(wèn)題的規(guī)模（通常用n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。第三十頁(yè)，共三十九頁(yè)，2022年，8月28日算法分析應(yīng)用舉例

算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作T(n)=O(f(n))，稱(chēng)作算法的漸近時(shí)間復(fù)雜度(AsymptoticTimecomplexity)，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。一般地，常用最深層循環(huán)內(nèi)的語(yǔ)句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來(lái)表示。“O”的定義：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則O(f(n))表示

C≥0，使得當(dāng)n≥n0時(shí)，|f(n)|≤C

|f(n0)|。表示時(shí)間復(fù)雜度的階有：

O(1)

：常量時(shí)間階O(n)：線性時(shí)間階

O(㏒n)

：對(duì)數(shù)時(shí)間階O(n㏒n)

：線性對(duì)數(shù)時(shí)間階第三十一頁(yè)，共三十九頁(yè)，2022年，8月28日

O(nk)：k≥2，k次方時(shí)間階例１兩個(gè)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(mén)(n)=O(n3)例２{++x;s=0;}

將x自增看成是基本操作，則語(yǔ)句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)。第三十二頁(yè)，共三十九頁(yè)，2022年，8月28日如果將s=0也看成是基本操作，則語(yǔ)句頻度為２，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階。例３for(i=1;i<=n;++i){++x;s+=x;}語(yǔ)句頻度為：2n，其時(shí)間復(fù)雜度為：O(n)，即為線性階。例４for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}

語(yǔ)句頻度為：2n2，其時(shí)間復(fù)雜度為：O(n2)，即為平方階。第三十三頁(yè)，共三十九頁(yè)，2022年，8月28日定理：若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)/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)限界。第三十四頁(yè)，共三十九頁(yè)，2022年，8月28日

以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指數(shù)時(shí)間的關(guān)系為：

O(2n)<O(n!)<O(nn)

當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。第三十五頁(yè)，共三十九頁(yè)，2022年，8月28日例6：素?cái)?shù)的判斷算法。Voidprime(intn)/*n是一個(gè)正整數(shù)*/