數(shù)據(jù)結(jié)構(gòu)-緒論課件

數(shù)據(jù)結(jié)構(gòu)緒論課件數(shù)據(jù)結(jié)構(gòu)教材及參考書目：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏等編清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語(yǔ)言版）嚴(yán)蔚敏等編清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)C++語(yǔ)言描述劉衛(wèi)東等譯清華大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)預(yù)備知識(shí)：C語(yǔ)言程序設(shè)計(jì)的基本技術(shù)離散數(shù)學(xué)概率論3數(shù)據(jù)結(jié)構(gòu)要求：上課認(rèn)真聽課作業(yè)按時(shí)完成上機(jī)實(shí)習(xí)認(rèn)真，按質(zhì)按量完成4數(shù)據(jù)結(jié)構(gòu)第一章緒論第六章樹與二叉樹第二章線性表第七章圖第三章棧和隊(duì)列第八章動(dòng)態(tài)存儲(chǔ)管理第四章串

第九章查找第五章數(shù)組與廣義表第十章內(nèi)部排序5第一章緒論目的：了解數(shù)據(jù)結(jié)構(gòu)的背景掌握一些基本概念和術(shù)語(yǔ)掌握抽象數(shù)據(jù)類型的定義、表示與實(shí)現(xiàn)描述算法的類C語(yǔ)言掌握算法分析的一些基本方法6第一章緒論重點(diǎn)：有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)掌握抽象數(shù)據(jù)類型ADT的定義、表示與實(shí)現(xiàn)熟悉類C語(yǔ)言的書寫規(guī)范理解算法五個(gè)要素的確切含義掌握估算時(shí)間復(fù)雜度的方法，了解空間復(fù)雜度的度量方法7第一章緒論難點(diǎn)：抽象數(shù)據(jù)類型ADT的表示與實(shí)現(xiàn)算法復(fù)雜度的分析方法8第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析1.4.1算法1.4.2算法設(shè)計(jì)的要求1.4.3算法效率的度量1.4.4算法的存儲(chǔ)空間的需求9一、數(shù)據(jù)結(jié)構(gòu)形成和發(fā)展背景計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)兩個(gè)問題：

1）信息的表示和組織：直接關(guān)系到處理信息的程序的效率；

2）信息的處理：面向系統(tǒng)程序和應(yīng)用程序的大規(guī)模和復(fù)雜結(jié)構(gòu)1.1什么是數(shù)據(jù)結(jié)構(gòu)10一、數(shù)據(jù)結(jié)構(gòu)形成和發(fā)展背景計(jì)算機(jī)的飛速發(fā)展及其應(yīng)用范圍的迅速擴(kuò)展計(jì)算機(jī)處理的對(duì)象由純粹的數(shù)值發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)編制“好”的程序要求分析待處理的對(duì)象以及各處理對(duì)象之間存在的關(guān)系1.1什么是數(shù)據(jù)結(jié)構(gòu)11二、數(shù)據(jù)結(jié)構(gòu)1、用計(jì)算機(jī)解決問題的步驟：具體問題—建立數(shù)學(xué)模型—設(shè)計(jì)算法—編制程序—測(cè)試和調(diào)整—最終答案建立數(shù)學(xué)模型（關(guān)鍵）：分析問題、提取操作對(duì)象、找出對(duì)象間關(guān)系，對(duì)此用數(shù)學(xué)語(yǔ)言加以描述算法設(shè)計(jì)：利用建立的數(shù)學(xué)模型，根據(jù)具體問題，設(shè)計(jì)出解決問題的方法1.1什么是數(shù)據(jù)結(jié)構(gòu)12二、數(shù)據(jù)結(jié)構(gòu)從數(shù)學(xué)模型上分：數(shù)值問題（數(shù)學(xué)方程），如：橋梁結(jié)構(gòu)的應(yīng)力分析模型——線性方程組人口增長(zhǎng)模型——微分方程全球天氣預(yù)報(bào)——環(huán)流模式方程非數(shù)值問題（集合、線性表、樹、圖等）無法用數(shù)學(xué)方程加以描述1.1什么是數(shù)據(jù)結(jié)構(gòu)13二、數(shù)據(jù)結(jié)構(gòu)2、數(shù)據(jù)結(jié)構(gòu)主要關(guān)心的：結(jié)構(gòu)中各元素之間邏輯關(guān)系（數(shù)學(xué)模型）

線性結(jié)構(gòu)：如圖書館的書目索引

樹形結(jié)構(gòu)：見后面例子

圖形結(jié)構(gòu)：見后面例子結(jié)構(gòu)中各元素的存儲(chǔ)方式結(jié)構(gòu)具有的行為特征（其上的操作）在計(jì)算機(jī)中的表示和實(shí)現(xiàn)

1.1什么是數(shù)據(jù)結(jié)構(gòu)14例1.圖書館的書目檢索系統(tǒng)自動(dòng)化問題（線性結(jié)構(gòu)）圖書館的一本圖書由書名、作者、出版社等數(shù)據(jù)來描述，根據(jù)需要我們選擇其中的若干項(xiàng)組成一個(gè)數(shù)據(jù)元素來對(duì)應(yīng)一本書圖書館的編目表反映了書與書之間的關(guān)系，是數(shù)據(jù)元素之間的結(jié)構(gòu)。當(dāng)然我們還應(yīng)注意到書是具體地放在某個(gè)書架上的，它是編目表的物理實(shí)現(xiàn)圖書館從兩方面管理圖書：物理的藏書和邏輯的編目表。這就是圖書館的結(jié)構(gòu)。和圖書館一樣計(jì)算機(jī)管理數(shù)據(jù)，也有兩個(gè)方面：即物理的存儲(chǔ)和邏輯的關(guān)系1.1什么是數(shù)據(jù)結(jié)構(gòu)151.1什么是數(shù)據(jù)結(jié)構(gòu)16例2：下棋問題1.1什么是數(shù)據(jù)結(jié)構(gòu)17例3.多叉路口交通燈的管理（圖結(jié)構(gòu)）11112223344111.1什么是數(shù)據(jù)結(jié)構(gòu)18問題模型信息管理——二維數(shù)據(jù)表下棋——樹型結(jié)構(gòu)城市路徑——圖型結(jié)構(gòu)1.1什么是數(shù)據(jù)結(jié)構(gòu)19數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間相互關(guān)系和操作等的學(xué)科對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型1.1什么是數(shù)據(jù)結(jié)構(gòu)20二、數(shù)據(jù)結(jié)構(gòu)

NiklausWirth：

Algorithms+DataStructures=Programs

程序設(shè)計(jì):為計(jì)算機(jī)處理問題編制一組指令集算法：處理問題的策略數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型1.1什么是數(shù)據(jù)結(jié)構(gòu)21“數(shù)據(jù)結(jié)構(gòu)”所處的地位221.2基本概念和術(shù)語(yǔ)數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合數(shù)值性數(shù)據(jù)/非數(shù)值性數(shù)據(jù)數(shù)據(jù)元素：數(shù)據(jù)基本單位，通常作為一個(gè)整體來考慮，如：“樹”中的一個(gè)棋盤格局；學(xué)生信息表，一個(gè)數(shù)據(jù)元素（記錄）含若干個(gè)數(shù)據(jù)項(xiàng)等數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位231.2基本概念和術(shù)語(yǔ)數(shù)據(jù)對(duì)象：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。數(shù)據(jù)對(duì)象可以是有限的，也可以是無限的整數(shù)數(shù)據(jù)對(duì)象:N={0,1,2,…}英文字符類型的數(shù)據(jù)對(duì)象:{A，B，C，D，E，F(xiàn)，…}

學(xué)生數(shù)據(jù)對(duì)象：數(shù)據(jù)表數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)對(duì)象之間的關(guān)系：

數(shù)據(jù)

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

數(shù)據(jù)項(xiàng)24集合元素間為松散的關(guān)系

線性結(jié)構(gòu)元素間為嚴(yán)格的一對(duì)一關(guān)系樹形結(jié)構(gòu)元素間為嚴(yán)格的一對(duì)多關(guān)系

圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）元素間為多對(duì)多關(guān)系

示例特征1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu):相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

251.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)對(duì)象之間的區(qū)別和聯(lián)系？數(shù)據(jù)對(duì)象僅僅是數(shù)據(jù)元素的集合，不涉及這些元素之間的關(guān)系描述數(shù)據(jù)結(jié)構(gòu)不僅要描述數(shù)據(jù)對(duì)象，而且要描述元素彼此之間的關(guān)系261.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)描述

Data-Structure=(D,S)

D——數(shù)據(jù)集；S——關(guān)系集例：復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：

Complex=(C，R)

其中：C是含兩個(gè)實(shí)數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實(shí)部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}271.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)描述

Data-Structure=(D,S)D——數(shù)據(jù)集；S——關(guān)系集例：學(xué)科研究課題小組

Group=(P,R)

其中：P={T,G1,G2,…Gn,S11,S12,…Snm}R={R1,R2}R1={<T,Gi>|i=1,2,3}R2={<Gi,Sij>|i=1,2,3,j=1,2}281.2基本概念和術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)描述的元素間的邏輯“關(guān)系”，獨(dú)立于計(jì)算機(jī)按集合的觀點(diǎn)，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素，二是關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)按關(guān)系分為線性結(jié)構(gòu)（關(guān)系是線性的）和非線性結(jié)構(gòu)（關(guān)系是非線性的）29301.2基本概念和術(shù)語(yǔ)數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系在存儲(chǔ)器中的存儲(chǔ)方法（表現(xiàn)和實(shí)現(xiàn)）物理結(jié)構(gòu)中的基本定義：

1）位：二進(jìn)制中的一位；信息表示的最小單位

2）元素（結(jié)點(diǎn)）：由若干位組合起來形成的一個(gè)位串，可看成是數(shù)據(jù)元素在計(jì)算機(jī)中的映象

3）數(shù)據(jù)域：當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串311.2基本概念和術(shù)語(yǔ)按照物理結(jié)構(gòu)的不同分為：1）順序存儲(chǔ)結(jié)構(gòu)：利用在存儲(chǔ)器中的物理關(guān)系來表示邏輯關(guān)系。邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相毗鄰的存儲(chǔ)單元里，元素的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：數(shù)據(jù)元素可以在計(jì)算機(jī)內(nèi)任意位置上存放（它不要求邏輯上相鄰的元素在物理位置上也相鄰)，用在存儲(chǔ)器中附加指針的方式來表示邏輯關(guān)系。將數(shù)據(jù)元素存放的存儲(chǔ)單元分為兩個(gè)部分，分別存放數(shù)據(jù)和指針，稱為數(shù)據(jù)域和指針域321.2基本概念和術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系：邏輯結(jié)構(gòu)只抽象地描述數(shù)據(jù)元素邏輯關(guān)系（簡(jiǎn)稱數(shù)據(jù)結(jié)構(gòu)）物理結(jié)構(gòu)是一個(gè)邏輯結(jié)構(gòu)映像到計(jì)算機(jī)中所得到的存儲(chǔ)表示算法的設(shè)計(jì)：取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)算法的實(shí)現(xiàn)：依賴于采用的存儲(chǔ)結(jié)構(gòu)331.2基本概念和術(shù)語(yǔ)數(shù)據(jù)類型用以刻畫（程序）操作對(duì)象的特性。一個(gè)值的集合（整型變量）+該集合上定義的一組操作(不體現(xiàn)值間關(guān)系)（加、減等操作）類型明顯或隱含地規(guī)定了：在程序執(zhí)行期間變量或表達(dá)式所有可能的取值范圍以及在這些值上允許進(jìn)行的操作341.2基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型：數(shù)據(jù)結(jié)構(gòu)+定義在此結(jié)構(gòu)上的一組操作（和其在計(jì)算機(jī)上的表示和實(shí)現(xiàn)無關(guān)）。不再局限于前述各處理器中已定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶自定義的數(shù)據(jù)類型351.2基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型1）一個(gè)含抽象數(shù)據(jù)類型的軟件模塊包含：定義、表示和實(shí)現(xiàn)2）三元組表示（D,S,P）

D：數(shù)據(jù)對(duì)象，S：D上的關(guān)系集，P：D上的基本操作集361.2基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型定義：

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

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系定義>

基本操作：<基本操作定義>}ADT抽象數(shù)據(jù)類型名其中：1）數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼表示；371.2基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型定義：2）基本操作的定義：基本操作名（參數(shù)表）初始條件：（初始條件描述）操作結(jié)果：（操作結(jié)果描述）基本操作有兩種參數(shù)：

賦值參數(shù)：為操作提供輸入值

引用參數(shù)：以&打頭，除提供輸入值外，還將返回操作結(jié)果381.2基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型定義：2）基本操作的定義：

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

操作結(jié)果：說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之391.2基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型三元組的定義:（P9，例1-6）ADTTriplet{

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

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

基本操作：

InitTriplet(&T)

DestroyTriplet(&T) Get(T,i,&e) Put(&T,i,e) …}ADTTriplet401.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)可以通過固有數(shù)據(jù)類型表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作利用類C語(yǔ)言（C語(yǔ)言的一個(gè)核心子集）作為描述工具類C語(yǔ)言描述：P10-13

typedef

數(shù)據(jù)類型定義

ElemType

數(shù)據(jù)元素類型

Status函數(shù)結(jié)果狀態(tài)的整數(shù)描述與運(yùn)算&&,或運(yùn)算||41類C語(yǔ)言描述：P10-13

內(nèi)存的動(dòng)態(tài)分配與釋放指針變量=new數(shù)據(jù)類型

delete指針變量基本操作的算法：函數(shù)描述函數(shù)結(jié)果主要狀態(tài)代碼：

TURE,OK=1FALSE,ERROR=0OVERFLOW=-21.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)42類C語(yǔ)言描述：P10-13

幾組特殊的賦值形式：交換賦值，數(shù)組賦值，條件賦值選擇語(yǔ)句：條件語(yǔ)句，開關(guān)語(yǔ)句循環(huán)語(yǔ)句：for,while,do-while

輸入和輸出語(yǔ)句：三種結(jié)束語(yǔ)句return,break,exit

注釋：基本函數(shù)：max,min,abs,eof,eoln1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)43例1-7抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)（P11-13）基本操作的函數(shù)原型：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3);//操作結(jié)果：構(gòu)造了三元組T，e1,e2和e3被賦以參數(shù)v1,v2,v3的值

StatusDestroyTriplet(Triplet&T)；

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

StatusGet(TripletT,inti,ElemType&e);//初始條件：三元組T已存在，1i3//操作結(jié)果：用e返回T的第i元的值。1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)44例1-7抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)（P11-13）基本操作的實(shí)現(xiàn)：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//構(gòu)造三元組T，依此置T的三個(gè)元素的初值為v1,v2,v3 T=(ElemType*)malloc(3*sizeof(ElemType));if(!T)exit(OVERFLOW);T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)45例1-7抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)（P11-13）基本操作的實(shí)現(xiàn)：

StatusDestroyTriplet(Triplet&T){//銷毀三元組T free(T);T=null;returnOK;}StatusGet(TripletT,inti,ElemType&e){//1i3,用e返回T的第i元的值。

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)46例：復(fù)數(shù)抽象數(shù)據(jù)類型示例ADTComplex{ 數(shù)據(jù)對(duì)象：D={c1,c2|c1,c2R(R為實(shí)數(shù)集）} 數(shù)據(jù)關(guān)系：S={<c1,c2>（c1為實(shí)部，c2為虛部）} 基本操作： voidAssign(&A,c1,c2） voidAdd(&A,B) voidMinus(&A,B) voidMultiply(&A,B) voidDivide(&A,B) ...}ADTComplex1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)471.4算法和算法分析算法：對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作算法的五個(gè)重要特性：

1）有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成

2）確定性：算法中每一條指令必須有確切的含義，不存在二義性。且算法只有一個(gè)入口和一個(gè)出口481.4算法和算法分析算法的五個(gè)重要特性：

3）可行性：一個(gè)算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的

4）輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合

5）輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量491.4算法和算法分析算法設(shè)計(jì)的要求：

1）正確性：算法應(yīng)滿足具體問題的需求

a）程序不含語(yǔ)法錯(cuò)誤；b）程序?qū)τ谝话爿斎霐?shù)據(jù)的正確性；c）程序?qū)τ诳量?、刁難輸入數(shù)據(jù)的正確性；d）程序?qū)τ谝磺泻戏ㄝ斎霐?shù)據(jù)的正確性

2）可讀性：算法應(yīng)該好讀。以有利于人對(duì)程序的理解

3）健壯性：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果501.4算法和算法分析算法設(shè)計(jì)的要求：

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

效率：算法執(zhí)行時(shí)間

存儲(chǔ)量需求：算法執(zhí)行過程中所需要的最大存儲(chǔ)空間

一般，這兩者與問題的規(guī)模有關(guān)511.4算法和算法分析算法效率的度量算法執(zhí)行時(shí)間的度量方法：1）事后統(tǒng)計(jì)的方法：收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料缺陷：a）必須先運(yùn)行依據(jù)算法編制的程序；b）依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素2）事前分析估算的方法：求出該算法的一個(gè)時(shí)間界限函數(shù)算法運(yùn)行所消耗的時(shí)間取決于：a）依據(jù)的算法選用何種策略；b）問題的規(guī)模；c）書寫程序的語(yǔ)言；d）編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；e）機(jī)器執(zhí)行指令的速度521.4算法和算法分析算法的時(shí)間度量1）原操作：基本操作2）算法的時(shí)間度量：原操作重復(fù)執(zhí)行的次數(shù)3）算法的漸近時(shí)間復(fù)雜度：原操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)T(n)=O(f(n))4）頻度：原操作重復(fù)執(zhí)行的次數(shù)531.4算法和算法分析算法的時(shí)間度量常見的時(shí)間復(fù)雜度：

1）O(1)常量階2）O(n)線性階

3）O(n2)平方階4）O(n3)立方階

5）O(logn)對(duì)數(shù)階6）O(2n)指數(shù)階541.4算法和算法分析算法的時(shí)間度量六種常用計(jì)算算法時(shí)間的多項(xiàng)式的關(guān)系為：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時(shí)間的關(guān)系為：

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

當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，若能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就551.4算法和算法分析算法的時(shí)間度量例1.{++x;s=0;}將x自增看成是基本操作，則語(yǔ)句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)如果將s=0也看成是基本操作，則語(yǔ)句頻度為1，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階例2.for(i=1;i<=n;++i){++x;s+=x;}

語(yǔ)句頻度為：n

其時(shí)間復(fù)雜度為：O(n)

即時(shí)間復(fù)雜度為線性階561.4算法和算法分析算法的時(shí)間度量例3.for(i=1;i<=n;++i)

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

語(yǔ)句頻度為：n2

其時(shí)間復(fù)雜度為：O(n2)

即時(shí)間復(fù)雜度為平方階。571.4算法和算法分析算法的時(shí)間度量例4.兩個(gè)N*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]; /*原操作*/ }問題規(guī)模：n原操作：c[i][j]+=a[i][k]*b[k][j];基本操作重復(fù)執(zhí)行的次數(shù)：f(n)=n3該算法時(shí)間度量記作T(n)=O(f(n))=O(n3)時(shí)間復(fù)雜度：O(n3)581.4算法和算法分析算法的時(shí)間度量在難以精確計(jì)算基本操作執(zhí)行次數(shù)的情況下，只需求出它關(guān)于n的增長(zhǎng)率或階即可。例

for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}591.4算法和算法分析算法的時(shí)間度量當(dāng)基本操作執(zhí)行次數(shù)隨問題的輸入數(shù)據(jù)集變化時(shí)，計(jì)算平均時(shí)間復(fù)雜度或最壞情況下的上界。例有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集的不同而不同（冒泡排序法）voidBubble_Sort(inta[],intn){for(i=n-1,change=TRUE;i>=1&&change;--i) {change=FALSE; for(j=