數(shù)據(jù)結(jié)構(gòu)教程與題解

數(shù)據(jù)結(jié)構(gòu)教程與題解第1頁，課件共38頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)一、概論二、順序表單鏈表其它鏈表，練習(xí)三、棧.隊(duì)列.串四、數(shù)組.廣義表鏈表綜合實(shí)驗(yàn)五、二叉樹性質(zhì).遍歷遞歸遍歷舉例.生成遞歸消除.線索二叉樹樹.森林.哈夫曼樹階段練習(xí)六、矩陣.鄰接表.遍歷生成樹.最小生成樹拓?fù)?關(guān)鍵.練習(xí)七、直插.希爾.冒泡.快速直選.堆.歸并.分配八、靜態(tài)查找二叉排序樹,B.B+樹排序綜合實(shí)驗(yàn)散列表總復(fù)習(xí)少學(xué)時(shí)參考：40(理論)+8(實(shí)驗(yàn))第2頁，課件共38頁，創(chuàng)作于2023年2月1.1引言1.2數(shù)據(jù)結(jié)構(gòu)的概念1.3算法分析第1章概論不論計(jì)算機(jī)作何用途，每一項(xiàng)應(yīng)用總是某個(gè)程序的運(yùn)行，用計(jì)算機(jī)解決任何問題都離不開程序設(shè)計(jì)。程序設(shè)計(jì)的實(shí)質(zhì)就是數(shù)據(jù)的表示和數(shù)據(jù)的處理。數(shù)據(jù)結(jié)構(gòu)就是研究這兩個(gè)方面的一些基本問題的，包括如何組織數(shù)據(jù)、數(shù)據(jù)元素之間是什么關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中如何表示以及如何對(duì)數(shù)據(jù)進(jìn)行操作等。第3頁，課件共38頁，創(chuàng)作于2023年2月數(shù)值型

非數(shù)值型

整數(shù)實(shí)數(shù)…

程序原始數(shù)據(jù)1.1引言數(shù)據(jù)的加工處理數(shù)據(jù)表示、數(shù)據(jù)處理程序程序設(shè)計(jì)的實(shí)質(zhì)字符字符串文字圖形圖象聲音…結(jié)果數(shù)據(jù)第4頁，課件共38頁，創(chuàng)作于2023年2月(1)數(shù)值問題求面積、體積S=a×bV=a×b×c◆建模型◆設(shè)計(jì)解法◆編程數(shù)據(jù)對(duì)象比較簡(jiǎn)單，如整型、實(shí)型或布爾型等，數(shù)據(jù)結(jié)構(gòu)的問題不突出，程序設(shè)計(jì)的主要精力集中在程序設(shè)計(jì)的技巧上，解決問題的關(guān)鍵是數(shù)值計(jì)算方法(算法)，程序以算法為中心。

也要用到數(shù)據(jù)結(jié)構(gòu)知識(shí)方程求根f(x)=a2x2＋a1x＋a0=0變量名？零系數(shù)？前后順序？快慢？?jī)?nèi)存？數(shù)組壓縮線性效率評(píng)價(jià)f(x)=anxn＋an?1xn?1＋…＋a1x＋a0=0第5頁，課件共38頁，創(chuàng)作于2023年2月賽程安排AEDBFC(2)非數(shù)值問題JIACBDHGFE族譜（血緣關(guān)系）學(xué)號(hào)姓名性別出生日期籍貫入學(xué)成績(jī)所在班級(jí)00201楊潤生男82/06/01廣州56100計(jì)算機(jī)2

00102石磊男83/12/21汕頭51200計(jì)算機(jī)1

……………檔案管理數(shù)據(jù)對(duì)象非數(shù)值型，數(shù)據(jù)間關(guān)系復(fù)雜、處理復(fù)雜（不能用數(shù)學(xué)公式表示），如何有效表示關(guān)系、如何有效處理數(shù)據(jù)，成為問題的關(guān)鍵。選擇合適的數(shù)據(jù)結(jié)構(gòu)表示問題，再寫出算法

程序＝數(shù)據(jù)結(jié)構(gòu)＋算法有序索引線性第6頁，課件共38頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)的研究問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲(chǔ)，如何處理。第7頁，課件共38頁，創(chuàng)作于2023年2月1.2數(shù)據(jù)結(jié)構(gòu)的概念1.2.1數(shù)據(jù)1.2.2數(shù)據(jù)類型1.2.3邏輯結(jié)構(gòu)1.2.4存儲(chǔ)結(jié)構(gòu)1.2.5運(yùn)算1.2.6算法1.2.7數(shù)據(jù)結(jié)構(gòu)第8頁，課件共38頁，創(chuàng)作于2023年2月1.2.1數(shù)據(jù)數(shù)據(jù)(Data)：凡能被計(jì)算機(jī)存儲(chǔ)、加工處理的對(duì)象。是計(jì)算機(jī)程序加工處理的對(duì)象和原料。數(shù)值型、非數(shù)值型，含有某種信息，信息的載體。信息：加工處理后的數(shù)據(jù)，數(shù)據(jù)的內(nèi)涵，信息通過數(shù)據(jù)表示。數(shù)據(jù)元素(DataElement)：數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理，常具有完整確定的實(shí)際意義。有時(shí)稱元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)項(xiàng)(DataItem)：數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位，有獨(dú)立含義，但常不具完整確定的實(shí)際意義，或不被當(dāng)作一整體看待有時(shí)稱字段、域。第9頁，課件共38頁，創(chuàng)作于2023年2月學(xué)號(hào)姓名性別出生日期籍貫入學(xué)成績(jī)所在班級(jí)00201楊潤生男82/06/01廣州56100計(jì)算機(jī)200102石磊男83/12/21汕頭51200計(jì)算機(jī)1

……………例學(xué)生信息表數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)反映了數(shù)據(jù)組織的三個(gè)層次，數(shù)據(jù)可由若干數(shù)據(jù)元素組成，數(shù)據(jù)元素又可由若干數(shù)據(jù)項(xiàng)組成。第10頁，課件共38頁，創(chuàng)作于2023年2月1.2.2數(shù)據(jù)類型數(shù)據(jù)類型(DataType)是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個(gè)數(shù)據(jù)集合上的一組操作的總稱，它顯式或隱式地規(guī)定了數(shù)據(jù)的取值范圍和操作特性。

原子類型：值不可分解，一般由程序語言直接提供，int、char…結(jié)構(gòu)類型：值可分解為若干成分(分量)，一般用戶定義(借助語言有關(guān)數(shù)據(jù)組織功能，數(shù)組、結(jié)構(gòu)…)抽象數(shù)據(jù)類型(AbstractDataType或ADT)是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作的總稱。“抽象”的含義是指其邏輯特征與具體的軟硬件實(shí)現(xiàn)(即計(jì)算機(jī)內(nèi)部的表示和實(shí)現(xiàn))無關(guān)。第11頁，課件共38頁，創(chuàng)作于2023年2月－使用與實(shí)現(xiàn)分離，－封裝和信息隱藏。在C++中通過類來描述。ADT

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

isData:<數(shù)據(jù)描述>Operations:<操作聲明>end

<抽象數(shù)據(jù)類型名>抽象數(shù)據(jù)類型一般由用戶定義：將一組數(shù)據(jù)和施加于這些數(shù)據(jù)上的一組操作封裝在一起，用戶程序只能通過在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實(shí)現(xiàn)了信息的隱藏。

struct學(xué)生{intheight;}class學(xué)生{intheight;public:intget_height();voidstudy();}學(xué)生a;x=a.height;struct學(xué)生a;x=a.height;×第12頁，課件共38頁，創(chuàng)作于2023年2月1.2.3邏輯結(jié)構(gòu)數(shù)據(jù)元素對(duì)應(yīng)客觀世界中的實(shí)體，其間必然存在各種各樣的關(guān)系數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。其中，數(shù)據(jù)元素之間的關(guān)聯(lián)方式(或稱鄰接關(guān)系)稱作數(shù)據(jù)的邏輯關(guān)系，數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為邏輯結(jié)構(gòu)(LogicalStructure)直接前趨(ImmediatePredecessor)：與之相鄰且在其前的結(jié)點(diǎn)直接后繼(ImmediateSuccessor)：與之相鄰且在其后的結(jié)點(diǎn)。圓圈表示數(shù)據(jù)，連線表示邏輯關(guān)系第13頁，課件共38頁，創(chuàng)作于2023年2月(1)集合：任兩點(diǎn)之間不考慮鄰接關(guān)系或沒有鄰接關(guān)系，或稱沒有關(guān)系的關(guān)系。數(shù)據(jù)組織形式松散，元素之間“平等”，除了“同屬于一個(gè)集合”的關(guān)系外，別無其它關(guān)系。(2)線性結(jié)構(gòu)：有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，任何結(jié)點(diǎn)最多一個(gè)直接前趨和一個(gè)直接后繼。開始結(jié)點(diǎn)沒有前趨，終端結(jié)點(diǎn)沒有后繼。元素之間存在1：1的關(guān)系。(3)樹形結(jié)構(gòu)：除一個(gè)特殊元素(根)外，每個(gè)元素只有一個(gè)直接前趨，但可有多個(gè)直接后繼，結(jié)點(diǎn)之間具有分支、層次特性。元素之間存在1：n的關(guān)系。(4)圖狀結(jié)構(gòu)：任何兩點(diǎn)之間都可能鄰接，結(jié)點(diǎn)之間形成網(wǎng)狀結(jié)構(gòu)。任一元素可有多個(gè)直接前趨和多個(gè)直接后繼，元素之間存在m：n的關(guān)系。圖狀結(jié)構(gòu)集合線性結(jié)構(gòu)樹形結(jié)構(gòu)第14頁，課件共38頁，創(chuàng)作于2023年2月(1)邏輯結(jié)構(gòu)與數(shù)據(jù)本身的形式、內(nèi)容無關(guān)。(2)邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無關(guān)。(3)邏輯結(jié)構(gòu)與所含結(jié)點(diǎn)的個(gè)數(shù)無關(guān)。一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)，邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種“本質(zhì)性”的東西。事實(shí)上，邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。第15頁，課件共38頁，創(chuàng)作于2023年2月1.2.4存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))存儲(chǔ)結(jié)構(gòu)(StorageStructure)、物理結(jié)構(gòu)：數(shù)據(jù)的機(jī)內(nèi)表示(存儲(chǔ)實(shí)現(xiàn))。數(shù)據(jù)元素的機(jī)內(nèi)表示＋邏輯結(jié)構(gòu)的機(jī)內(nèi)表示(1)內(nèi)容存儲(chǔ)：存儲(chǔ)各數(shù)據(jù)元素的內(nèi)容(值)，每個(gè)數(shù)據(jù)元素占據(jù)獨(dú)立的可訪問的存儲(chǔ)區(qū)。(2)關(guān)系存儲(chǔ)：直接或間接地(顯式或隱式地)存儲(chǔ)各數(shù)據(jù)元素間的邏輯關(guān)系。(3)附加存儲(chǔ)：一般是為便于運(yùn)算實(shí)現(xiàn)而設(shè)置的輔助結(jié)點(diǎn)。前兩部分必須，第三部分根據(jù)需要設(shè)置。元素內(nèi)部組織形式一般較簡(jiǎn)單，內(nèi)容存儲(chǔ)就較簡(jiǎn)單，邏輯關(guān)系的表示是存儲(chǔ)結(jié)構(gòu)的主要內(nèi)容。元素存儲(chǔ)后，邏輯關(guān)系由存儲(chǔ)結(jié)點(diǎn)間的關(guān)聯(lián)方式間接表示。第16頁，課件共38頁，創(chuàng)作于2023年2月(1)順序存儲(chǔ)：所有結(jié)點(diǎn)相繼存放到一片連續(xù)的存儲(chǔ)區(qū)中，元素之間的邏輯關(guān)系通過物理位置關(guān)系間接表示。(2)鏈接存儲(chǔ)：結(jié)點(diǎn)之間的物理位置不一定連續(xù)，它們之間的邏輯關(guān)系通過附加的指針來表示。(3)索引存儲(chǔ)：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。(4)散列存儲(chǔ)：以結(jié)點(diǎn)的關(guān)鍵字值為自變量，通過某個(gè)函數(shù)計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)位置(或位置區(qū)間端點(diǎn))。順序存儲(chǔ)方式和鏈接存儲(chǔ)方式是最基本的。四種存儲(chǔ)方法，既可單獨(dú)使用，也可組合使用。有時(shí)同一種邏輯結(jié)構(gòu)可采用不同的存儲(chǔ)結(jié)構(gòu)。第17頁，課件共38頁，創(chuàng)作于2023年2月1.2.5運(yùn)算運(yùn)算：在邏輯結(jié)構(gòu)上施加的操作，即對(duì)邏輯結(jié)構(gòu)的加工。如：查找、插入、刪除等。加工型：改變?cè)壿嫿Y(jié)構(gòu)的“值”，如結(jié)點(diǎn)數(shù)、結(jié)點(diǎn)內(nèi)容等。引用型：不改變?cè)壿嫿Y(jié)構(gòu)，只從中提取某些信息。運(yùn)算與邏輯結(jié)構(gòu)緊密相連，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。運(yùn)算的種類很多，隨不同的應(yīng)用而不同。第18頁，課件共38頁，創(chuàng)作于2023年2月基本運(yùn)算：其實(shí)現(xiàn)不能利用其它運(yùn)算，而其它運(yùn)算可以或需要利用該運(yùn)算。如更新不是基本運(yùn)算，可先用查找，找到該該點(diǎn)后再修改有關(guān)內(nèi)容；而查找是基本運(yùn)算，它不能利用其它運(yùn)算。每種邏輯結(jié)構(gòu)都有自己的基本運(yùn)算集，邏輯結(jié)構(gòu)不同，基本運(yùn)算集一般也不同。一般地，先將較復(fù)雜的運(yùn)算分解為若干較簡(jiǎn)單的運(yùn)算，有利于降低程序設(shè)計(jì)的難度，同時(shí)也有利于提高程序設(shè)計(jì)的效率。在簡(jiǎn)單運(yùn)算中，再分解出一些基本運(yùn)算，當(dāng)基本運(yùn)算實(shí)現(xiàn)后，其它運(yùn)算就可通過調(diào)用基本運(yùn)算來實(shí)現(xiàn)，進(jìn)而完成整個(gè)程序。第19頁，課件共38頁，創(chuàng)作于2023年2月1.2.6算法算法(Algorithm)：解決問題的方法和步驟；規(guī)則的有窮集合，這些規(guī)則規(guī)定了一個(gè)指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。求3個(gè)數(shù)a，b,c中的最大值例運(yùn)算定義在邏輯結(jié)構(gòu)上，只指出“做什么(功能)”，而不考慮“怎么做(細(xì)節(jié))”。運(yùn)算實(shí)現(xiàn)的這個(gè)細(xì)節(jié)問題就是算法。(1)若a>b則max=a,否則max=b(2)若c>max則max=c有些步驟可重復(fù)多次執(zhí)行，但整個(gè)步驟總數(shù)應(yīng)有限，整個(gè)過程可終止。－可執(zhí)行－可終止第20頁，課件共38頁，創(chuàng)作于2023年2月

算法的基本特征：(1)輸入：0個(gè)或多個(gè)輸入；(2)輸出：1個(gè)或多個(gè)輸出；(3)有窮性：在有限步內(nèi)結(jié)束；(4)確定性：每步清晰無二義性。(5)可行性：每步可執(zhí)行，并且執(zhí)行時(shí)間是有限的。算法＝程序？程序不一定滿足有窮性，即不一定是算法。如操作系統(tǒng)。程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令雖要求可執(zhí)行，但不一定是“機(jī)器可執(zhí)行”。第21頁，課件共38頁，創(chuàng)作于2023年2月算法描述圖形描述：如流程圖、N?S圖自然語言：非形式算法，可結(jié)合其它語言

不嚴(yán)格，易二義性

偽語言：偽語言算法程序設(shè)計(jì)語言：運(yùn)行終止的程序可執(zhí)行部分

嚴(yán)格

語言描述原則上說，任何算法都可用任一種程序設(shè)計(jì)語言來實(shí)現(xiàn)，但顯然具體實(shí)現(xiàn)的難易程度和效果會(huì)有所不同。Y=a+b?中國的煤都是＿＿?第22頁，課件共38頁，創(chuàng)作于2023年2月C語句C++語句#include<stdio.h>…scanf(”%d%c”,&i,&ch);printf(”%d%c\n”,i,ch);#include<iostream.h>…cin>>i>>ch;cout<<i<<ch<<endl;#definemaxsize100constintmaxsize=100;for(i=0;i<n;i++)s=s+a[i];/*元素求和*/for(i=0;i<n;i++)s=s+a[i];

//數(shù)組元素求和int*p,*q;p=malloc(10*sizeof(int));q=malloc(sizeof(int));…free(p);free(q);int*p,*q;p=newint[10];//動(dòng)態(tài)分配10個(gè)整數(shù)空間(數(shù)組)q=newint;//動(dòng)態(tài)分配1個(gè)整數(shù)空間…delete[]p;//釋放數(shù)組空間deleteq;第23頁，課件共38頁，創(chuàng)作于2023年2月1.2.7數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)是指相互間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合，它們按照某種邏輯關(guān)系組織起來，并用計(jì)算機(jī)語言，按一定的存儲(chǔ)方式存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，同時(shí)在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。由一個(gè)邏輯結(jié)構(gòu)S、一個(gè)定義在S上的基本運(yùn)算集Δ和S的一個(gè)存儲(chǔ)實(shí)現(xiàn)D所構(gòu)成的整體(S,Δ,D)由一個(gè)邏輯結(jié)構(gòu)S和定義在S上的一個(gè)基本運(yùn)算集Δ構(gòu)成的整體(S,Δ)簡(jiǎn)單地說，一個(gè)數(shù)據(jù)結(jié)構(gòu)就是一類數(shù)據(jù)的表示及其相關(guān)操作，它一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算。不混淆時(shí)，常將邏輯結(jié)構(gòu)簡(jiǎn)稱數(shù)據(jù)結(jié)構(gòu)。第24頁，課件共38頁，創(chuàng)作于2023年2月邏輯結(jié)構(gòu)是數(shù)據(jù)本身所固有的，與計(jì)算機(jī)無關(guān)。每種邏輯結(jié)構(gòu)都有自己的一組基本運(yùn)算，它規(guī)定了數(shù)據(jù)的基本操作方式。由一種邏輯結(jié)構(gòu)和一組基本運(yùn)算構(gòu)成的整體，與數(shù)據(jù)的存儲(chǔ)無關(guān)，獨(dú)立于計(jì)算機(jī)，可看成具體問題抽象出來的數(shù)學(xué)模型。將數(shù)據(jù)和數(shù)據(jù)間邏輯關(guān)系存儲(chǔ)起來，就得到存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算定義在邏輯結(jié)構(gòu)上，只指出“做什么”，而不考慮“怎么做”，當(dāng)確定了存儲(chǔ)結(jié)構(gòu)后，才能考慮如何將運(yùn)算具體實(shí)現(xiàn)，即“怎么做”，這就是算法問題。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的實(shí)現(xiàn)，算法是運(yùn)算的實(shí)現(xiàn)，故可認(rèn)為數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)就是數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)第25頁，課件共38頁，創(chuàng)作于2023年2月對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，將其三個(gè)方面的內(nèi)容搞清楚了，也就搞清楚了這個(gè)數(shù)據(jù)結(jié)構(gòu)。另外，這三方面中即使只有某一個(gè)不同，我們也將其稱作不同的數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)不同：集合、線性表、樹、圖。邏輯結(jié)構(gòu)相同，存儲(chǔ)結(jié)構(gòu)不同：順序表、鏈表。邏輯結(jié)構(gòu)相同，運(yùn)算不同：棧、隊(duì)列。邏輯結(jié)構(gòu)相同，存儲(chǔ)結(jié)構(gòu)相同，運(yùn)算不同：順序棧、順序隊(duì)列；鏈棧、鏈隊(duì)列。第26頁，課件共38頁，創(chuàng)作于2023年2月用頂點(diǎn)和邊構(gòu)成的圖形表示數(shù)據(jù)結(jié)構(gòu)，其中頂點(diǎn)表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；學(xué)生基本情況表家族樹(1)圖形表示JIACBDHGFE0104060508070203第27頁，課件共38頁，創(chuàng)作于2023年2月用一個(gè)二元組(D,S)表示數(shù)據(jù)結(jié)構(gòu)，其中D是數(shù)據(jù)元素集合，S是D上關(guān)系的集合。D={01，02，03，04，05，06，07，08}S={R}R={<01,02>,<02,03>,<03,04>,<04,05>,<05,06>,<06,07>,<07,08>}D={A,B,C,D,E,F,G,H,I,J}

S={R}

R={(A,B),(A,C),(A,D),(B,E),(B,F),(C,G),(D,H),(D,I),(D,J)}

家族樹的二元組表示(D,S)JIACBDHGFE學(xué)生基本情況表的二元組表示(D,S)

(2)二元組表示0104060508070203第28頁，課件共38頁，創(chuàng)作于2023年2月1.3算法分析正確性：正確實(shí)現(xiàn)預(yù)定功能（處理要求）。易讀性：被理解的難易程度，便于交流、修改、查錯(cuò)健壯性：對(duì)非法輸入的抵抗能力，不產(chǎn)生不需要結(jié)果高效率：較好的時(shí)空性能。算法評(píng)價(jià)算法分析：確定一個(gè)算法時(shí)空性能的工作?？臻g復(fù)雜性/度(SpaceComplexity)：算法的空間耗費(fèi)，即需要的存儲(chǔ)量時(shí)間復(fù)雜性/度(TimeComplexity)：算法的時(shí)間耗費(fèi)，即包含的計(jì)算量第29頁，課件共38頁，創(chuàng)作于2023年2月(1)時(shí)間復(fù)雜度時(shí)間耗費(fèi)＝所有語句執(zhí)行時(shí)間之和。各語句執(zhí)行時(shí)間是其執(zhí)行次數(shù)(即頻度，F(xiàn)requencyCount)與每次執(zhí)行時(shí)間的乘積。即語句執(zhí)行時(shí)間與軟、硬件有關(guān)，難以給出絕對(duì)時(shí)間，并且環(huán)境不同絕對(duì)時(shí)間也不同。為突出算法本身性態(tài)而排除之外其它因素，假定語句抽象運(yùn)行，不依賴具體軟硬件環(huán)境；進(jìn)一步假定各語句每次執(zhí)行時(shí)間均是單位時(shí)間。于是，時(shí)間耗費(fèi)就是算法中所有語句頻度之和有時(shí)取占主導(dǎo)、關(guān)鍵作用的“標(biāo)準(zhǔn)操作”分析。注：“語句”指描述算法的基本語句，它的執(zhí)行，在語法意義上不可再分割。如循環(huán)語句的整體、函數(shù)調(diào)用語句等不算基本語句，因?yàn)樗鼈冞€包括由多個(gè)語句組成的循環(huán)體或函數(shù)體。第30頁，課件共38頁，創(chuàng)作于2023年2月時(shí)間復(fù)雜度是規(guī)模的函數(shù)。兩個(gè)方陣相乘Cn×n=An×n×Bn×n

for(i=0;i<n;i++) //n+1

for(j=0;j<n;j++){

//n(n+1)

c[i][j]=0.;

//n2

for(k=0;k<n;k++)

//n2(n+1)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

//n3

}例例矩陣相乘T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1一般地，我們將問題輸入數(shù)據(jù)量(或初始數(shù)據(jù)量)的大小，或與之相關(guān)的某個(gè)量，稱為問題的規(guī)模(Size，大小)，并用一個(gè)整數(shù)表示。第31頁，課件共38頁，創(chuàng)作于2023年2月當(dāng)問題的規(guī)模n趨向無窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為算法的漸近時(shí)間復(fù)雜度(AsymptoticTimeComplexity)。時(shí)間復(fù)雜度的解析形式常常難求，或非常復(fù)雜。但問題規(guī)模較大時(shí)，復(fù)雜度表示式中實(shí)際上只有一些占主導(dǎo)地位的項(xiàng)有意義，其它低次項(xiàng)可忽略不計(jì)。所以通常用某些簡(jiǎn)單函數(shù)來近似表示其大致性能。T(n)=2n3+3n2+2n+1=O(n3)(1)若語句很少執(zhí)行，且與規(guī)模無關(guān)，則可忽略不計(jì)。(2)若所有語句都與規(guī)模無關(guān)，即使有上千條語句，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)，時(shí)間復(fù)雜度也只是O(n0)=O(1)。(3)一般可只考慮與程序規(guī)模有關(guān)的頻度最大的語句，如循環(huán)語句的循環(huán)體，多重循環(huán)的內(nèi)循環(huán)等。第32頁，課件共38頁，創(chuàng)作于2023年2月tmp=a;

a=b;

b=tmp;sum=0;

for(i=1;i<=n;i++)

sum+=i;sum=0;

for(i=1;i<=n;i*=2)

sum+=i;sum=0;

for(i=0;i<n;i++)

for(j=0;j<=i;j++)

A[i][j]=0;O(1)O(n)O(log2n)O(n2)sum=0;

for(i=1;i*i<=n;i++)

sum+=i;O(n1/2)sum=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

A[i][j]=0;O(n2)第33頁，課件共38頁，創(chuàng)作于2023年2月例例行列式計(jì)算設(shè)CPU

GHz，每時(shí)鐘計(jì)算1次行列式計(jì)算，設(shè)直接展開，有n!項(xiàng)，每項(xiàng)n個(gè)因子，乘法次數(shù)為：n!*(n-1)。體驗(yàn)O(n!)。100n＝25階，所需要時(shí)間：T＝25！100×1091365×24×3600＝4.92×106（年）≈500萬年！×n＝20階，所需時(shí)間：T=0.77年n＝15階，所需時(shí)間：T=13秒n＝10階，所需時(shí)間：T=3.63×10-5秒增長(zhǎng)太快，n稍大不可行實(shí)際行列式都是先化簡(jiǎn)再計(jì)算，并不直接展開。第34頁，課件共38