計算機數(shù)據(jù)結(jié)構(gòu)第一章緒言

計算機數(shù)據(jù)結(jié)構(gòu)第一章緒言第一頁，共五十八頁，編輯于2023年，星期一與相關(guān)課程聯(lián)系線性代數(shù)數(shù)據(jù)結(jié)構(gòu)離散數(shù)學程序設(shè)計概率論編譯原理操作系統(tǒng)算法設(shè)計與分析人工智能數(shù)據(jù)庫原理

……第二頁，共五十八頁，編輯于2023年，星期一學習目標及方法

了解數(shù)據(jù)的特性，學會數(shù)據(jù)的組織及其在計算機內(nèi)部的表示方法掌握基本的算法原理和設(shè)計

訓練基本的、良好的程序設(shè)計技能注重實踐，項目驅(qū)動學習繼續(xù)保持“研學小組”學習方式課程有一定難度，要重視第三頁，共五十八頁，編輯于2023年，星期一教材與參考書：嚴蔚敏，吳偉民編．《數(shù)據(jù)結(jié)構(gòu)》（C語言版）．北京：清華大學出版，2007年．吳艷等．《數(shù)據(jù)結(jié)構(gòu)與算法實驗教程》．北京：科學出版社，2006年．

嚴蔚敏吳偉民.數(shù)據(jù)結(jié)構(gòu)題集(C語言版),清華大學出版社第四頁，共五十八頁，編輯于2023年，星期一第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4算法和算法分析

1.4.1算法

1.4.2算法設(shè)計的要求

1.4.3算法效率的度量

1.4.4算法的存儲空間的需求第五頁，共五十八頁，編輯于2023年，星期一計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題：信息的表示信息的處理而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應用程序的規(guī)模很大，結(jié)構(gòu)又相當復雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。第六頁，共五十八頁，編輯于2023年，星期一

對于數(shù)值計算問題，其數(shù)學模型通常是數(shù)學方程；而對于更多的非數(shù)值計算問題，其數(shù)學模型通常無法用數(shù)學方程加以描述。數(shù)據(jù)結(jié)構(gòu)重點研究此類問題的處理。第七頁，共五十八頁，編輯于2023年，星期一過去我們知道：程序=算法+數(shù)據(jù)結(jié)構(gòu)本課程將深刻理解該問題。程序:計算機處理問題編制一組指令集.

算法:處理問題的策略.數(shù)據(jù)結(jié)構(gòu):問題的數(shù)學模型

.第八頁，共五十八頁，編輯于2023年，星期一1.1什么是數(shù)據(jù)結(jié)構(gòu)眾所周知，計算機的程序是對信息進行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個例子。

例1.1、電話號碼查詢系統(tǒng)設(shè)有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)

其中ai，bi(i=1，2…n)分別表示某人的名字和對應的電話號碼要求設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。第九頁，共五十八頁，編輯于2023年，星期一算法的設(shè)計，依賴于計算機如何存儲人的名字和對應的電話號碼，或者說依賴于名字和其電話號碼的結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題?？蓪⒚趾蛯碾娫捥柎a設(shè)計成：二維數(shù)組、表結(jié)構(gòu)、向量。假定名字和其電話號碼邏輯上已安排成N元向量的形式，它的每個元素是一個數(shù)對(ai，bi)，1≤i≤n

數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運算的算法。第十頁，共五十八頁，編輯于2023年，星期一例１.2圖書館書目檢索系統(tǒng)（表）（１）問題目標：自動檢索（２）操作對象：書目信息（登錄號、書名、作者名、分類號、出版單位、出版時間等）（３）對象關(guān)系：順序排列（４）數(shù)學模型：線形數(shù)據(jù)結(jié)構(gòu)類似問題有：查號系統(tǒng)、倉庫帳戶系統(tǒng)等第十一頁，共五十八頁，編輯于2023年，星期一001高等數(shù)學樊映川S01……002理論力學羅遠祥L01……003高等數(shù)學華羅庚S01……004線性代數(shù)欒汝書S02……..………………………………………高等數(shù)學001,003,…理論力學002,…線性代數(shù)004,…樊映川001,…華羅庚003,…欒汝書004,…L002,…S001,003,…圖1.1圖書目錄文件示例書名索引表作者索引表分類號索引表第十二頁，共五十八頁，編輯于2023年，星期一例1.3人機對弈問題

（１）問題目標：計算機不僅要會看格局，還能預測棋局發(fā)展，做出決策。（２）操作對象：格局（３）對象關(guān)系：一個格局可派生出多個格局（４）數(shù)學模型：樹形數(shù)據(jù)結(jié)構(gòu)第十三頁，共五十八頁，編輯于2023年，星期一例1.3計算機和人對弈問題（樹）○○××○××○××○××○××○×××××××○○○○○第十四頁，共五十八頁，編輯于2023年，星期一例1.4多叉路口交通燈的管理（１）問題目標：設(shè)計交通燈方案，使車輛相互不沖突，且流量最大CBAED第十五頁，共五十八頁，編輯于2023年，星期一（２）操作對象：頂點（表示通路，用兩個字母表示，前者為出發(fā)點，后者為到達點）（３）對象關(guān)系：連線（表示通路之間的沖突關(guān)系）（４）數(shù)學模型：圖第十六頁，共五十八頁，編輯于2023年，星期一例1.3多叉路口交通燈的管理問題（圖）EABCD(b)表示通路的圖11111112223344(a)五叉路口EDABACADBABCBDDADBDCEAEBEC第十七頁，共五十八頁，編輯于2023年，星期一

通過以上幾例可以直接地認為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應的運算，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。第十八頁，共五十八頁，編輯于2023年，星期一1.2基本概念和術(shù)語數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。第十九頁，共五十八頁，編輯于2023年，星期一數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(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)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。

第二十頁，共五十八頁，編輯于2023年，星期一

集合

線性樹

圖數(shù)據(jù)的邏輯結(jié)構(gòu)示例第二十一頁，共五十八頁，編輯于2023年，星期一數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：

Data-Structure=(D，R)

其中：D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。例復數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：

Complex=(C，R)

其中：C是含兩個實數(shù)的集合﹛C1，C2﹜，分別表示復數(shù)的實部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。第二十二頁，共五十八頁，編輯于2023年，星期一

數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機中有兩種不同的表示方法：順序表示和非順序表示由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)順序存儲結(jié)構(gòu):用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈式存儲結(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。第二十三頁，共五十八頁，編輯于2023年，星期一abcd例

線性表L=(D,R),D={a,b,c,d},R={(a,b),(b,c),(c,d)}順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)（單鏈表）Labcd^第二十四頁，共五十八頁，編輯于2023年，星期一指針項可以有多個,以指示多個后繼.例如,S=(D,R),D={a,b,c,d,e,f},R={(a,b),(a,c),(b,d),(b,e),(c,f)}abcfedd1d2d3d4d5d6ΛΛΛΛΛΛΛ第二十五頁，共五十八頁，編輯于2023年，星期一1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)

數(shù)據(jù)類型(DataType)一般的高級語言都提供了一些數(shù)據(jù)類型,如整數(shù)型,字符型等.數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱.用戶還可以定義自己的數(shù)據(jù)類型.數(shù)據(jù)類型可分為原子類型(不可分解的,如int,bool,char等)和結(jié)構(gòu)類型(由其他類型構(gòu)成)數(shù)據(jù)類型為程序員提供了極大的方便:它將數(shù)據(jù)集合及其上的操作與其實現(xiàn)細節(jié)分離開來,或者說將數(shù)據(jù)的邏輯表示和運算與它們的實現(xiàn)相分離。程序員只需要了解此集合由哪些值構(gòu)成,可以進行那些運算.第二十六頁，共五十八頁，編輯于2023年，星期一抽象數(shù)據(jù)類型

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

簡稱ADT)是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作.抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。用三元組描述如下：（Ｄ，R，Ｐ）

D

是數(shù)據(jù)對象(性質(zhì)相同的數(shù)據(jù)元素的有限集)。

R

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

P是對D的基本操作的有限集。

第二十七頁，共五十八頁，編輯于2023年，星期一抽象數(shù)據(jù)類型描述：ADT{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}

ADT

抽象數(shù)據(jù)類型名

其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為基本操作名（參數(shù)表）初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

第二十八頁，共五十八頁，編輯于2023年，星期一

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

“操作結(jié)果:說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應返回的結(jié)果。若初始條件為空，則省略之。第二十九頁，共五十八頁，編輯于2023年，星期一例1.4

定義一個抽象數(shù)據(jù)類型——三元組ADTTriplet{

數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3ElemSet}

數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T,v1,v2,v3)

操作結(jié)果：構(gòu)造了三元組T，元素e1,e2,e3分別被賦以參數(shù)v1,v2,v3的值。

DestroyTriplet(&T)

操作結(jié)果：三元組T被銷毀。

Get(T,i,&e)

初始條件：三元組T已存在，1i3

操作結(jié)果：用e返回T的第i元的值?！谌摚参迨隧?，編輯于2023年，星期一

抽象數(shù)據(jù)類型的表示與實現(xiàn)通常采用類語言（類程序設(shè)計語言，如類C，類PASCAL等）作為描述工具，和程序設(shè)計語言相比，類語言具有以下特點：1.抽象性

類語言抽象而簡潔，描述算法時可忽略許多細節(jié)問題。2.可讀性類語言算法忽略細節(jié)而突出了解題的思路和方法。3.適應性用類語言寫的算法可以方便地轉(zhuǎn)換為各種程序設(shè)計語言的程序。第三十一頁，共五十八頁，編輯于2023年，星期一類C語言簡介//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;(1)

預定義常量和類型：第三十二頁，共五十八頁，編輯于2023年，星期一(2)數(shù)據(jù)結(jié)構(gòu)的表示(即存儲結(jié)構(gòu))用類型定義(typedef)描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時自行定義。(3)基本操作的算法都用以下形式的函數(shù)描述:函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{

//算法說明語句序列

}//函數(shù)名第三十三頁，共五十八頁，編輯于2023年，星期一(3)．賦值語句簡單賦值：〈變量名〉=〈表達式〉，它表示將表達式的值賦給左邊的變量；〈變量〉++，它表示變量加1后賦值給變量；〈變量〉--，它表示變量減1后賦值給變量；第三十四頁，共五十八頁，編輯于2023年，星期一成組賦值：1.（〈變量1〉,〈變量2〉,〈變量3〉,…〈變量k〉）

=（〈表達式1〉，〈表達式2〉,〈表達式3〉,…〈表達式k〉）;2.〈數(shù)組名1〉[下標1…下標2]=〈數(shù)組名2〉[下標1…下標2]；第三十五頁，共五十八頁，編輯于2023年，星期一串聯(lián)賦值：〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達式〉；條件賦值：〈變量名〉=〈條件表達式〉？〈表達式1〉：〈表達式2〉；交換賦值：〈變量1〉←→〈變量2〉，表示變量1和變量2互換；第三十六頁，共五十八頁，編輯于2023年，星期一(5)．條件選擇語句if（〈表達式〉）語句；if（〈表達式〉）語句1；else語句2；情況語句

switch（〈表達式〉）{case判斷值1；語句組1；break；case判斷值2；語句組2；break；

……case判斷值n；語句組n；break；[default：語句組n+1；]}注意：switchcase語句是先計算表達式的值，然后用其值與判斷值相比較，若它們相一致時，就執(zhí)行相應的case下的語句組；若不一致，則執(zhí)行default下的語句組；其中的方括號代表可選項。第三十七頁，共五十八頁，編輯于2023年，星期一(7)．輸入、輸出語句輸入語句：用函數(shù)scanf實現(xiàn)，特別當數(shù)據(jù)為字符時，用getchar函數(shù)實現(xiàn)。輸出語句：用printf函數(shù)實現(xiàn)，特別當要輸出字符數(shù)據(jù)時，用putchar函數(shù)實現(xiàn)。(6)循環(huán)語句：for（賦初值表達式；條件；修改表達式序列）語句；while（條件）語句；do{語句序列}while（條件）；第三十八頁，共五十八頁，編輯于2023年，星期一(8)．其他一些語句（1）return表達式或return：用于函數(shù)結(jié)束。（2）break語句：可用在循環(huán)語句或case語句中結(jié)束循環(huán)過程或跳出情況語句。（3）exit語句：表示出現(xiàn)異常情況時，控制退出語句。(9)．注釋形式

可用/*字符串*/或者單行注釋或//文字序列。第三十九頁，共五十八頁，編輯于2023年，星期一(10)邏輯運算約定與運算&&

對于A&&B，當A的值為0時，不再對B求值。例：

inta[N];……i=0;while(i<N&&a[i]!=x)i++;

或運算||

對于A||B，當A的值為非0時，不再對B求值。

第四十頁，共五十八頁，編輯于2023年，星期一例1.4(續(xù)):

抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)//-----采用動態(tài)分配的順序存儲結(jié)構(gòu)typedefElemtype*Triplet;//-----基本操作的函數(shù)原型說明StatusInitTriplet(Triplet&T,Elemtypev1,Elemtypev2,Elemtypev3);//操作結(jié)果：構(gòu)造了三元組T，元素e1,e2,e3分別被

//賦以參數(shù)v1,v2,v3的值。StatusDestroyTriplet(Triplet&T);//操作結(jié)果：三元組T被銷毀。Status

Get(TripletT,inti,Elemtype&e)//初始條件：三元組T已存在，1i3

//操作結(jié)果：用e

返回T的第i元的值?！谒氖豁?，共五十八頁，編輯于2023年，星期一//-----基本操作的實現(xiàn)StatusInitTriplet(Triplet&T,Elemtypev1,Elemtypev2,Elemtypev3);{T=(Elemtype

*)malloc(3*sizeof(Elemtype));if(!T)exit(OVERFLOW);T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}//InitTripletStatusDestroyTriplet(Triplet&T);{free(T);T=NULL;returnOK;}//DestroyTriplet第四十二頁，共五十八頁，編輯于2023年，星期一Status

Get(TripletT,inti,Elemtype&e){//1i3,用e

返回T的第i元的值。

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}//GetStatus

Put(Triplet&T,inti,Elemtypee){//1i3,置T的第i元的值為e。

if(i<1||i>3)returnERROR;T[i-1]=e;returnOK;}//Put第四十三頁，共五十八頁，編輯于2023年，星期一1.4算法和算法分析1.4.1算法算法：是對特定問題求解步驟的一種描述。算法是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有以下五個特性：（1）有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。（2）確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。（3）可行性：一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。第四十四頁，共五十八頁，編輯于2023年，星期一(4)輸入:

一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。(5)輸出:

一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。1.4.2算法設(shè)計的要求評價一個好的算法有以下幾個標準:(1)正確性(Correctness)：算法應滿足具體問題的需求。(2)可讀性(Readability)：算法應該好讀。以有利于閱讀者對程序的理解。(3)健狀性(Robustness)：算法應具有容錯處理。當輸入非法數(shù)據(jù)時，算法應對其作出反應，而不是產(chǎn)年莫名其妙的輸出結(jié)果。第四十五頁，共五十八頁，編輯于2023年，星期一(4)效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。1.4.3算法效率的度量

對一個算法要作出全面的分析可分成兩用人才個階段進行，即事后測試和事先分析。事后測試

收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料。事先分析

求出該算法的一個時間界限函數(shù)第四十六頁，共五十八頁，編輯于2023年，星期一事后測試法缺點：1.必須編制程序且上機執(zhí)行；

2.其它因素可能掩蓋算法本身的質(zhì)量

算法的效率通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量，不同算法的程序可通過一組或若干組相同的測試數(shù)據(jù)以分辨優(yōu)劣。第四十七頁，共五十八頁，編輯于2023年，星期一事前分析法

從算法中選取一種對于所研究問題來說是基本操作的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法執(zhí)行時間的度量基準。原操作——

固有數(shù)據(jù)類型的操作

固有數(shù)據(jù)類型——

計算機系統(tǒng)中已定義并實現(xiàn)的數(shù)據(jù)類型,如高級語言中的整型、實型、字符型、布爾型、指針型等。第四十八頁，共五十八頁，編輯于2023年，星期一T(n)=O(f(n))其中：

n——

問題的規(guī)模，如：矩陣的階，線性表的長度，樹中的結(jié)點數(shù)，圖中的頂點數(shù)等。算法的時間復雜度:

f(n)——

n的某個函數(shù)，通常表示算法中基本操作的重復執(zhí)行次數(shù)。定義：如果存在兩個正常數(shù)c和n0，對于所有的n≧n0，有︱f(n)︳≦c｜g(n)，則記作f(n)=O(g(n))第四十九頁，共五十八頁，編輯于2023年，星期一O(1)O(n)O(n2)O(n3)常量階線性階平方階立方階指數(shù)階對數(shù)階O(2n)O(log2n)O(nlog2n)O(f(n)+g(n))=O(max(f(n),g(n)))O(cf(n))=O(f(n))運算法則：第五十頁，共五十八頁，編輯于2023年，星期一//計算n階矩陣的乘積c=a*b

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]=c[i][j]+a[i][k]*b[k][j];

}原操作基本操作的重復執(zhí)行次數(shù)：f(n)=n3例:矩陣相乘算法第五十一頁，共五十八頁，編輯于2023年，星期一矩陣相乘算法的時間量度記作：

T(n)=O(n3)稱O(n3)為該算法的(漸近)時間復雜度。

asymptotictimecomplexity它表示：當n較大時，T(n)與