數(shù)據(jù)結構與算法-趙玉蘭 第1章 概述

1.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述11.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述21.1數(shù)據(jù)結構的發(fā)展數(shù)據(jù)結構的發(fā)展離不開計算機的發(fā)展。1946年，第一臺電子計算機（ENIAC）在美國問世，那時候計算機主要被用于數(shù)值計算（如：計算彈道軌跡、求解方程組等）。數(shù)據(jù)結構的發(fā)展經(jīng)歷三個階段：無結構階段結構化階段面向?qū)ο箅A段與程序設計的發(fā)展相對應3無結構階段20世紀40~60年代應用領域：科學計算（如：計算微積分等）處理的數(shù)據(jù)：數(shù)值型數(shù)據(jù)（如：整數(shù)、浮點數(shù)等）數(shù)據(jù)之間的關系：數(shù)學公式或函數(shù)1.1數(shù)據(jù)結構的發(fā)展4結構化階段20世紀60~80年代非數(shù)值計算猛增1.1數(shù)據(jù)結構的發(fā)展70’s80’s90’s5結構化階段20世紀60~80年代應用領域：科學計算與非數(shù)值處理處理的數(shù)據(jù)：數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)。數(shù)據(jù)之間的關系：產(chǎn)生了數(shù)據(jù)結構，提出了結構化程序設計，開始注重數(shù)據(jù)的表示和操作的結構化。70年代中期《數(shù)據(jù)結構》形成了一門課程。1.1數(shù)據(jù)結構的發(fā)展6結構化階段圖靈獎獲得者沃思給出了一個著名的公式：數(shù)據(jù)結構+算法=程序從這個公式可以看到，數(shù)據(jù)結構和算法是構成程序的兩個重要的組成部分；一個軟件系統(tǒng)通常是以一個或幾個關鍵數(shù)據(jù)結構為核心而組織的。1.1數(shù)據(jù)結構的發(fā)展7結構化階段結構化程序設計的缺點由于軟件系統(tǒng)的實現(xiàn)依賴于關鍵數(shù)據(jù)結構，如果這些關鍵數(shù)據(jù)結構中的一個或幾個有所改變，則將涉及到整個系統(tǒng)，可能導致整個系統(tǒng)徹底崩潰。1.1數(shù)據(jù)結構的發(fā)展8面向?qū)ο箅A段20世紀80年代至今應用領域：更多地應用于非數(shù)值處理處理的數(shù)據(jù)：更多地處理非數(shù)值型數(shù)據(jù)（如：文本、語音、視頻等）1.1數(shù)據(jù)結構的發(fā)展9面向?qū)ο箅A段數(shù)據(jù)之間的關系：數(shù)據(jù)結構發(fā)展到面向?qū)ο箅A段，類和數(shù)據(jù)結構之間的對應關系如下：類屬性方法數(shù)據(jù)結構數(shù)據(jù)之間的關系基本操作對應（數(shù)據(jù)結構+算法）=程序1.1數(shù)據(jù)結構的發(fā)展10面向?qū)ο箅A段在面向?qū)ο蟪绦蛟O計中，將數(shù)據(jù)（屬性）和操作（方法）定義為一個整體（類），一旦數(shù)據(jù)（結構）發(fā)生變化，只需要修改類內(nèi)的局部代碼，軟件系統(tǒng)的其余部分無需修改。1.1數(shù)據(jù)結構的發(fā)展111.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述12用計算機求解問題一般包含兩個步驟：Step1:抽象出問題的模型；Step2:求解該模型。對于數(shù)值問題抽象出的模型通常是數(shù)學方程，例如：圖形的面積與周長等；預報人口增長情況——函數(shù)；更多的非數(shù)值問題是難以用數(shù)學方程來描述的。下面請看三個例子。1.2數(shù)據(jù)結構的研究對象131.2數(shù)據(jù)結構的研究對象例1學籍管理問題——線性結構學號姓名性別出生日期政治面貌0001王軍男1983/09/02團員0002李明男1982/12/25黨員0003湯曉影女1984/03/26團員……………特點：每個學生的信息占據(jù)一行，所有學生的信息按學號順序依次排列構成一張表格；表中每個學生的信息依據(jù)學號的大小存在著一種前后關系，這就是線性結構；對它的操作通常包括：插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。141.2數(shù)據(jù)結構的研究對象例2人機對弈問題——樹型結構如何實現(xiàn)對弈？各棋局之間是什么關系？井字棋又稱三子連珠，由兩個人對弈，棋盤為3×3的方格，當一方的三個棋子占同一行、或同一列、或同一對角線時便為勝方?！?.……..………...……特點：在求解過程中，所處理的數(shù)據(jù)之間具有層次關系，這是樹形結構；對它的操作有：建立樹型結構，輸出最底層結點內(nèi)容等等。151.2數(shù)據(jù)結構的研究對象例3教學計劃編排問題——圖結構C1C2C3C4C6C5C7如何表示課程之間的先修關系？課程編號課程名稱先修課程c1高等數(shù)學無c2計算機科學導論無c3離散數(shù)學c1c4程序設計語言C++c1、c2c5數(shù)據(jù)結構c3、c4c6計算機原理c2、c4c7數(shù)據(jù)庫原理c4、c5、c6特點：結點之間的先后關系用圖結構描述；對它的操作有：創(chuàng)建圖結構，按要求將圖結構中的頂點進行線性排序等。16數(shù)值問題→數(shù)學方程非數(shù)值問題→數(shù)據(jù)結構數(shù)據(jù)結構是研究非數(shù)值問題中計算機的操作對象以及它們之間的關系和操作的學科。學習《數(shù)據(jù)結構》就是弄清楚這些操作對象的特點，它們之間的關系以及各個操作的具體實現(xiàn)手段。1.2數(shù)據(jù)結構的研究對象171.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述18涉及的基本概念包括：數(shù)據(jù)（data）數(shù)據(jù)元素（dataelement）數(shù)據(jù)項（dataitem）數(shù)據(jù)對象（dataobject）數(shù)據(jù)結構（datastructure）1.3數(shù)據(jù)結構的基本概念19數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。

數(shù)值性數(shù)據(jù)——整數(shù)、浮點數(shù)、復數(shù)等；

非數(shù)值性數(shù)據(jù)——文字、圖像、語言等數(shù)據(jù)。20數(shù)據(jù)元素

(dataelement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。例如：C/C++語言中定義的一個結構體。有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(dataitem)組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。例如：結構體中的一個元素。21例1.4學生信息結構體。一個數(shù)據(jù)元素。若干個數(shù)據(jù)項。structstudent{char*name;char*number;unsignedintsex;

intage;……};22數(shù)據(jù)對象

(dataobject)具有相同性質(zhì)的數(shù)據(jù)元素（dataelement）的集合。通常是數(shù)據(jù)（data）的一個子集，在數(shù)據(jù)結構中數(shù)據(jù)對象簡稱數(shù)據(jù)。23

例1.5學生信息登記表。每一行都是一個數(shù)據(jù)元素。姓名學號性別年齡民族系專業(yè)入學時間王小林060631男18漢族計算機計算機科學2006,9陳紅060632女20蒙古族計算機計算機應用2006,9劉建平060633男19回族計算機電子商務2006,9……..……..…….…….……………….每一列都是一個數(shù)據(jù)項。一個學生數(shù)據(jù)對象。24數(shù)據(jù)（對象）、數(shù)據(jù)元素、數(shù)據(jù)項之間的關系：包含關系：數(shù)據(jù)（對象）是由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項組成。數(shù)據(jù)元素是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項一般不予考慮。25什么是數(shù)據(jù)結構

數(shù)據(jù)結構是計算機組織和存儲數(shù)據(jù)的方式。

數(shù)據(jù)結構主要包括三方面內(nèi)容：數(shù)據(jù)的邏輯結構：數(shù)據(jù)元素間的邏輯關系；數(shù)據(jù)的存儲結構：數(shù)據(jù)元素及其邏輯結構在計算機中的表示；數(shù)據(jù)的運算：對數(shù)據(jù)元素施加的操作（插入、刪除、修改、檢索等）。26什么是數(shù)據(jù)結構定義:

由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)元素之間的關系組成。記為：

Data_Structure={D,R}

其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)元素之間的關系的有限集合。271.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述281.4數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構可分為兩大類(四種)：線性結構

線性表非線性結構層次結構：樹

群結構：集合、圖（或網(wǎng)絡）29線性結構(LinearStructure)LS=(D,R)D={d1,d2,…,dn}R={<di,di+1>|i=1,2,3,…,n-1}例1.4：DS=(D,R1)D={d1,d2,d3,d4,d5,d6}R1={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>,<d5,d6>}d1d2d3d4d5d6線性結構線性結構的特點：結構中的數(shù)據(jù)元素具有“一對一”的關系。30例1.5：DS=(D,R2)D={d1,d2,d3,d4,d5,d6}

R2={d1

D,d2

D,d3

D,d4

D,d5

D,d6

D}集合集合的特點：結構中的數(shù)據(jù)元素只具有“同屬于一個集合”的關系。d1d2d3d4d5d6集合31例1.6：DS=(D,R3)D={d1,d2,d3,d4,d5,d6,d7}R3={<d1,d2>,<d1,d3>,<d3,d7>,<d2,d4>,<d2,d5>,<d2,d6>}

樹型結構d4d1d2d3d5d6d7樹型結構32d4d1d2d3d5d6d7樹型結構根結點:無前驅(qū)的結點，如：d1葉結點:無后繼的結點，如：d4,d5,d6,d7樹型結構的特點：有且僅有一個根結點，其它結點有且僅有一個前驅(qū)結點，對于非根結點都存在從根到該結點的一條路徑。結構中的數(shù)據(jù)元素存在“一對多”的關系。33例1.7：DS=(D,R4)D={d1,d2,d3,d4,d5}R4={<d1,d2>,<d3,d1>,<d1,d4>,<d5,d1>,<d2,d3>,<d5,d4>,<d3,d5>}

圖型或網(wǎng)狀結構圖型結構的特點：結構中的數(shù)據(jù)元素存在“多對多”

的關系。d1d2d3d4d534線性結構樹型結構bindevetclibuser樹二叉樹二叉搜索樹1413121123456789103158710119987456623131135圖結構網(wǎng)絡結構12312543611331814665161921群結構：集合125643361.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述37

1.5數(shù)據(jù)的存儲結構(StoreStructure)d1d2d3d4..dn-1dn0123n-1存儲結構:是數(shù)據(jù)的邏輯結構在計算機中的具體實現(xiàn)。數(shù)據(jù)元素集合到存儲地址集合的映射。D={di|i=1,2,3,…n}M={0,1,2,3,…,n-1}R:DM38存儲結構可分為兩類：順序存儲結構鏈式存儲結構

1.5數(shù)據(jù)的存儲結構(StoreStructure)39順序存儲結構（SequentialStructure）例1.8：LS=(D,R)D={a,b,c,d,e}R={<a,b>,<b,c>,<c,d>,<d,e>}abcde順序存儲結構:邏輯結構上相鄰的兩個元素在物理結構上也相鄰，即：前驅(qū)的結束是后繼的開始。abcde10241025102610271028存儲空間連續(xù)保持了邏輯關系數(shù)據(jù)元素的存儲位置LS40鏈式存儲結構(LinkedStructure)：例1.9：LS=(D,R)D={a,b,c,d,e}R={<a,b>,<a,c>,<c,d>,<c,e>}LSe0b1040a1026d1024c1034102410261028103010321034103610381040存儲空間不連續(xù)保持了邏輯關系數(shù)據(jù)元素的存儲位置abcdeLS不考慮具體地址，抽象為：

abcde41數(shù)據(jù)的邏輯結構是面向問題的，反映了數(shù)據(jù)內(nèi)部的構成方式；數(shù)據(jù)的存儲結構是面向計算機的，反映了數(shù)據(jù)及其邏輯結構的具體實現(xiàn)。邏輯結構是數(shù)據(jù)的機外表示，存儲結構是數(shù)據(jù)的機內(nèi)表示。一種數(shù)據(jù)的邏輯結構可以用多種存儲結構來存儲，而不同的存儲結構，其數(shù)據(jù)處理的效率往往也是不同的。數(shù)據(jù)的基本操作是定義于邏輯結構，實現(xiàn)于存儲結構。為了區(qū)別于數(shù)據(jù)的存儲結構，常將數(shù)據(jù)的邏輯結構稱為數(shù)據(jù)結構。數(shù)據(jù)的邏輯結構與存儲結構的關系：421.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述43數(shù)據(jù)類型（DataType）：一組性質(zhì)相同的值的集合，以及定義于這個值集合上的一組操作的總稱。數(shù)據(jù)類型顯式或隱含地規(guī)定了該類型數(shù)據(jù)的取值范圍和對這些數(shù)據(jù)所能采取的操作。例如：C++中的整型，其取值范圍為[-2147483648,+2147483647]，整型數(shù)能夠進行“加、減、乘、除、取余”等操作。1.6抽象數(shù)據(jù)類型ADT44數(shù)據(jù)類型可以分為兩類：原子類型：不可分解的數(shù)據(jù)類型，也稱基本數(shù)據(jù)類型。例如，C++中的原子數(shù)據(jù)類型包括：

intfloatdoublecharvoid構造類型：由若干原子類型構造出來的新類型，是可分解的。例如，C++中的構造數(shù)據(jù)類型包括：

數(shù)組結構體類1.6抽象數(shù)據(jù)類型ADT45抽象數(shù)據(jù)類型(AbstractDataType，ADT)：是由用戶定義，用以表示應用問題的數(shù)據(jù)模型。ADT是指一種數(shù)據(jù)結構以及定義在該數(shù)據(jù)結構上的一組操作的總稱。(參照數(shù)據(jù)類型的定義)ADT是面向?qū)ο蠹夹g中的核心概念，它能夠?qū)?shù)據(jù)的描述（數(shù)據(jù)元素的定義和它們之間的關系的定義）和所支持的各種操作封裝到一起。1.6抽象數(shù)據(jù)類型ADT46抽象數(shù)據(jù)類型(AbstractDataType，ADT)：是由用戶定義，用以表示應用問題的數(shù)據(jù)模型。ADT的特點：實現(xiàn)了數(shù)據(jù)的隱蔽和封裝，并將它的定義與實現(xiàn)相分離。ADT類似于面向?qū)ο蟪绦蛟O計中的“類”，通常是一種偽代碼形式定義的“類”。1.6抽象數(shù)據(jù)類型ADT47ADT和數(shù)據(jù)類型的區(qū)別：數(shù)據(jù)類型=值的集合

+一組操作無法體現(xiàn)值之間的邏輯關系ADT=數(shù)據(jù)結構

+一組操作因為有數(shù)據(jù)結構，因此能夠反映數(shù)據(jù)間的邏輯關系1.6抽象數(shù)據(jù)類型ADT48一個ADT的定義不涉及它的實現(xiàn)細節(jié)，因此在形式上可繁可簡，但通常包含以下三方面內(nèi)容：抽象數(shù)據(jù)類型名；數(shù)據(jù)的邏輯結構的定義；每種基本操作的接口（操作的名稱和該操作的前置條件、輸入、功能、輸出、后置條件的定義）。1.6抽象數(shù)據(jù)類型ADT49抽象數(shù)據(jù)類型的描述（定義）如下：ADT

ADT-name

{Data//數(shù)學模型或數(shù)據(jù)的邏輯結構Operations //操作集Constructor //構造操作，初始化

Operation1；

Operation2；

……

Operationk;}//ADT-name1.6抽象數(shù)據(jù)類型ADT50抽象數(shù)據(jù)類型的描述（定義）如下：ADT

ADT-name

{Data//數(shù)學模型或數(shù)據(jù)的邏輯結構Operations //操作集

Constructor //構造操作，初始化

Operation1；

Operation2；

……

Operationk;}//ADT-name1.6抽象數(shù)據(jù)類型ADT初始化構造操作的格式：ConstructorInitialvalues:用于初始化的值。

Process:初始化。51抽象數(shù)據(jù)類型的描述（定義）如下：ADT

ADT-name

{Data//數(shù)學模型或數(shù)據(jù)的邏輯結構Operations //操作集Constructor //構造操作，初始化

Operation1；

Operation2；

……

Operationk;}//ADT-name1.6抽象數(shù)據(jù)類型ADT其他操作的描述格式：OperationiInput:輸入數(shù)據(jù)（參數(shù)）。

Preconditions:執(zhí)行操作前系統(tǒng)所處狀態(tài)。

Process:操作。

Output:輸出。

Postconditions:執(zhí)行本操作后系統(tǒng)所處狀態(tài)。是操作中必須有的52例、圓的ADT描述圓是平面上與圓心等距離的所有點的集合。如果圓形是需要顯示的，則圓的抽象數(shù)據(jù)類型至少應該包括圓心和半徑；如果只計算周長和面積，則圓的抽象數(shù)據(jù)類型只需要半徑即可。

面積周長1.6抽象數(shù)據(jù)類型ADT53圓的ADT描述為：ADTCircle

{

Data圓的半徑r（r為非負數(shù)）Operations

ConstructorInitialvalues:半徑值

Process:將半徑值賦給r

Area

Process:計算圓的面積Output:返回圓的面積

Circumference

Process:計算圓的周長Output:返回圓的周長}//Circle54由于本書采用類C++語言作為數(shù)據(jù)結構的描述語言。在類C++語言中，使用類（class）來表示ADT。在類C++語言中，類是由數(shù)據(jù)項和定義在數(shù)據(jù)項上的函數(shù)組成：數(shù)據(jù)成員成員函數(shù)1.6抽象數(shù)據(jù)類型ADT55class

class-name{Datastructuresdeclare;Constructor(parameter-list){….}return-typeoperation1(parameter-list){….}……return-typeoperationn(parameter-list){….}};//class-name1.6抽象數(shù)據(jù)類型ADT

類C++語言描述的ADT如下：56用類C++語言表示ADT圓的類為：class

Circle{floatr;Circle(floatr0){r=r0;}floatarea(){return(3.14159*r*r);}floatcircumference(){return(3.14159*2*r);}};//Circle1.6抽象數(shù)據(jù)類型ADT571.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述581.7ADT的表示與實現(xiàn)間的關系ADT·邏輯結構·操作集合數(shù)據(jù)結構

·存儲結構·算法設計類

·成員變量·成員函數(shù)使用角度(ADT的定義)設計角度(ADT的設計)實現(xiàn)角度(ADT的實現(xiàn))ADT提供了使用、設計和實現(xiàn)三種不同的角度，便于在軟件開發(fā)的不同階段的使用。591.7ADT的表示與實現(xiàn)間的關系ADTADTname數(shù)據(jù)模型操作1操作2…..操作kADTADTname數(shù)據(jù)邏輯結構算法1算法2…..算法kclassADTname數(shù)據(jù)存儲結構函數(shù)1函數(shù)2…..函數(shù)k1n1n1個數(shù)據(jù)模型可用多個不同的數(shù)據(jù)的邏輯結構來表示；數(shù)據(jù)的邏輯結構是對數(shù)據(jù)模型的實現(xiàn)。1個數(shù)據(jù)的邏輯結構可有多種不同的存儲結構；存儲結構是邏輯結構在計算機中的實現(xiàn)。601.1數(shù)據(jù)結構的發(fā)展1.2數(shù)據(jù)結構的研究對象1.3數(shù)據(jù)結構的基本概念1.4數(shù)據(jù)的邏輯結構1.5數(shù)據(jù)的存儲結構1.6抽象數(shù)據(jù)類型1.7ADT的表示與實現(xiàn)間的關系1.8算法與算法分析第一章概述61算法的定義定義：是求解特定問題的一系列步驟的集合。例如：已知n個整數(shù)，存放在一個數(shù)組中，求此數(shù)組中的最大數(shù)。求解步驟如下：①將數(shù)組中第一個元素a[0]賦值給變量max；②初始化下標變量i為1；③當i<n時，執(zhí)行以下語句：比較a[i]與max，若a[i]大于max，則將a[i]賦值給max;變量i自增1;④輸出max的值。1.8算法與算法分析62算法的定義定義：是求解特定問題的一系列步驟的集合。特性：輸入

有0個或多個輸入；輸出

有一個或多個輸出(處理結果)；確定性

每步的定義都是確切無歧義的；有窮性

算法應在執(zhí)行有窮步后結束；可行性（有效性）算法中的所有操作都是可以通過已經(jīng)實現(xiàn)的基本操作運算有限次來實現(xiàn)的。1.8算法與算法分析63算法與程序的關系：算法≠程序程序是使用某種程序設計語言對算法的具體實現(xiàn)，是對算法的精確描述，可在計算機上運行。程序可以是無窮的，而算法必須是有窮的。程序設計的核心是算法。1.8算法與算法分析64算法設計者在構思和設計了一個算法之后，必須清楚準確地將所設計的求解步驟記錄下來，即：算法描述。常用的算法描述方法有：自然語言流程圖程序設計語言偽代碼……1.8算法與算法分析65歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個自然數(shù)m和n（假設m>=n）的最大公約數(shù)。1.8算法與算法分析算法描述66①輸入m和n；②求m除以n的余數(shù)r；③若r等于0，則n為最大公約數(shù)，算法結束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。例：歐幾里德算法。自然語言用自然語言描述算法，最大的優(yōu)點是容易理解，缺點是容易出現(xiàn)二義性，并且算法通常都很冗長。1.8算法與算法分析算法描述67N開始輸入m和n

r=m%nr=0m=n；n=r

輸出n結束Y流程圖用流程圖描述算法，優(yōu)點是直觀易懂，缺點是靈活性不如自然語言。1.8算法與算法分析算法描述例：歐幾里德算法。68#include<iostream.h>int

CommonFactor(intm,intn){

intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){

cout<<CommonFactor(63,54)<<endl;}程序設計語言用程序設計語言描述的算法能由計算機直接執(zhí)行，缺點是抽象性差，而且有時算法的篇幅可能很長。1.8算法與算法分析算法描述例：歐幾里德算法。69

1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;偽代碼1.8算法與算法分析算法描述例：歐幾里德算法。偽代碼是介于自然語言和程序設計語言之間的描述方法，它將某一程序設計語言的基本語法與自然語言結合起來使用。本書采用類C++語言（偽代碼）來描述算法。70采用類C++語言描述算法的好處：可以忽略一些煩瑣的語法細節(jié)；用習慣方式書寫表達式；個別時候使用少量的自然語言。1.8算法與算法分析算法描述71算法分析的目的：對不同的算法做出客觀的評價，使得設計或者挑選出來的算法盡可能是“好的”。評價算法“好壞”的幾個標準：正確性可讀性健壯性效率1.8算法與算法分析算法分析72算法分析的目的：對不同的算法做出客觀的評價，使得設計或者挑選出來的算法盡可能是“好的”。評價算法“好壞”的幾個標準：正確性：對任一個合法的輸入，算法結束后都能得到正確的結果。1.8算法與算法分析算法分析73算法分析的目的：對不同的算法做出客觀的評價，使得設計或者挑選出來的算法盡可能是“好的”。評價算法“好壞”的幾個標準：可讀性：要求算法的邏輯必須清晰、簡單，易于理解和交流。1.8算法與算法分析算法分析74算法分析的目的：對不同的算法做出客觀的評價，使得設計或者挑選出來的算法盡可能是“好的”。評價算法“好壞”的幾個標準：健壯性：算法應能對各種非法輸入做出響應并給出相應提示或處理，不至產(chǎn)生錯誤輸出或處于不確定狀態(tài)。1.8算法與算法分析算法分析75算法分析的目的：對不同的算法做出客觀的評價，使得設計或者挑選出來的算法盡可能是“好的”。評價算法“好壞”的幾個標準：效率：是指算法執(zhí)行時所消耗的計算機資源，包括時間上的開銷和空間上的開銷。1.8算法與算法分析算法分析76算法分析的目的：對不同的算法做出客觀的評價，使得設計或者挑選出來的算法盡可能是“好的”。評價算法“好壞”的幾個標準：正確性可讀性健壯性效率1.8算法與算法分析算法分析

算法評價的原則是在保證算法滿足“正確性”、“可讀性”和“健壯性”的前提下，算法的效率越高表示算法越好。771.8算法與算法分析算法分析度量算法效率的兩種方法：事后統(tǒng)計法：將算法實現(xiàn)，測算其運行的時間和空間開銷。缺點：編寫程序?qū)崿F(xiàn)算法將花費較多的時間；所得實驗結果依賴于計算機的軟硬件環(huán)境，可能掩蓋算法本身的優(yōu)劣。事前估算法：對算法所消耗資源的一種事先估算——一種普遍采用的評價算法效率的方法。781.8算法與算法分析算法分析算法的事前估算法：算法的時間復雜度：算法的執(zhí)行時間。（算法時間上的開銷）算法的空間復雜度：算法執(zhí)行過程中所需的存儲空間。（算法空間上的開銷）791.8算法與算法分析時間復雜度算法的執(zhí)行時間＝每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間單位時間

(與硬件相關)每條語句執(zhí)行次數(shù)之和基本操作的執(zhí)行次數(shù)對于不同的問題，基本操作不盡相同。801.8算法與算法分析時間復雜度元素比較兩實數(shù)矩陣相乘 排序 求多項式P(x)的值

循環(huán) 加、乘元素比較，移動加、乘循環(huán)體在數(shù)組中查找元素X問題 基本操作811.8算法與算法分析時間復雜度for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本操作：x++這段算法的時間復雜度是：n*n821.8算法與算法分析時間復雜度對于相同問題，同一個算法的時間復雜度可能會因輸入的狀態(tài)不同而產(chǎn)生巨大的差別。例如：從一個由n元素組成的一維數(shù)組中找出一個給定的k值，順序查找是從第一個元素開始，依次檢查每個元素，直至找到k為或無k為止。最好情況：數(shù)組中第一個元素就是k。最壞情況:數(shù)組中最后一個元素是k或無k。平均情況：查找到數(shù)組一半時找到k。831.8算法與算法分析時間復雜度因此，為了合理的描述一個算法的時間復雜度，一般需要分別計算最壞情況下的時間復雜度和平均情況下的時間復雜度。最壞情況下的時間復雜度平均情況下的時間復雜度84最壞情況下時間復雜度（Worst-caseComplexity）:設Dn是輸入規(guī)模為n的集合，I是Dn中的元素，t(I)是算法對輸入元素I所做工作量。用W(n)=max{t(I)|I屬于Dn}，表示最壞情況下時間復雜度。1.8算法與算法分析時間復雜度85算法思想：K依次和a0,a1,…,an-1比較，直到找到K或全部比較完。算法：int

seqSearch(intA[],intn,intK){ans=-1;for(i=0;i<n;i++) if(K==A[i]){

ans=i;break}returnans;}//endofseqSearch()例1.12

在n個數(shù)a0,a1,…,an-1中找K。基本操作：兩元素的比較.最壞情況分析：K在最末尾或無K.

W(n)=n最壞情況下的時間復雜度86平均情況下時間復雜度（AverageComplexity）:設Pr(I)是輸入元素I出現(xiàn)的概率，t(I)是算法對輸入I所做工作量，則：A(n)表示平均情況下時間復雜度。1.8算法與算法分析時間復雜度87平均情況下時間復雜度例1.12查找算法。設K在數(shù)組A中出現(xiàn)的概率是p，則K不在A中出現(xiàn)的概率是1-p，設K在任一位置出現(xiàn)的概率是相等的（K在A中時）是：

Pr(Ii)=p/n

//k在第i個位置上出現(xiàn)的概率顯然t(Ii)=i+1//k在第i個位置上時比較的次數(shù)所以：當p=1時88例1.13求兩個n階方陣的乘積C=A

Bvoid

MatrixMultiply(

int

A[n][n],int

B[n][n],

int

C[n][n]){for(

int

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

int

j=0;j<n;j++){…n(n+1)

C[i][j]=0;…n2for(

int

k=0;k<n;k++)…n2(n+1)

C[i][j]=C[i][j]+A[i][k]*B[k][j];

…n3}}2n3+3n2+2n+1時間復雜度：當與輸入無關時89算法中所有語句的頻度之和是矩陣階數(shù)n的函數(shù)

T(n)=

2n3+3n2+2n+1一般地，稱n是問題的規(guī)模。則時間復雜度T(n)是問題規(guī)模n的函數(shù)。當n趨于無窮大時，把時間復雜度的數(shù)量級（階）稱為算法的漸進時間復雜度：

T(n)=O(n3)----大O表示法（Big-oh）90加法規(guī)則針對并列程序段

T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))乘法規(guī)則針對嵌套程序段

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))91當T(n)為對數(shù)函數(shù)(log2n)，冪函數(shù)(n2,n3…)或它們的乘積(nlog2n)時，算法的運行時間是可以接受的，我們稱這些算法為有效的算法。當T(n)為指數(shù)函數(shù)(2n)或階乘函數(shù)(n!)時，算法的運行時間隨n而迅速增大，是不可接受的。我們稱這些算法是“壞”的算法或無效的算法。各種函數(shù)的增長趨勢的排序：

c<log2n<n<nlog2n<n2<n3<2n<3n<n!92變量計數(shù)x=0;y=0