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

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

主講人：譚定英“算法＋數(shù)據(jù)結(jié)構(gòu)＝程序〞程序就是在數(shù)據(jù)的某些特定的結(jié)構(gòu)和表示的根底上對于算法的描述。算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計中相輔相成、不可分割的兩個方面。抽象數(shù)據(jù)類型有一定行為〔操作〕的抽象〔數(shù)學(xué)〕類型。抽象出數(shù)據(jù)類型的使用要求，而把它的具體表示方式和運(yùn)算的實現(xiàn)細(xì)節(jié)都隱藏起來。支持?jǐn)?shù)據(jù)類型的實現(xiàn)與使用別離的原那么，是一種十分有效的對問題進(jìn)行抽象與分解的思維工具。是面向?qū)ο蠹夹g(shù)與方法的主要理論根底。數(shù)據(jù)結(jié)構(gòu)“數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類型的物理實現(xiàn)〞。解決：1〕如何具體表示抽象數(shù)據(jù)類型中的數(shù)學(xué)模型；2〕如何具體實現(xiàn)抽象數(shù)據(jù)類型中操作。學(xué)習(xí)目的理解數(shù)據(jù)結(jié)構(gòu)和算法的概念；掌握設(shè)計數(shù)據(jù)結(jié)構(gòu)與算法的主要原理和方法；比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。提高學(xué)生使用計算機(jī)解決問題的能力。第一章緒論

本章重點(diǎn)：理解從問題到程序的主要過程；體會抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和算法在問題求解過程中的作用；了解數(shù)據(jù)結(jié)構(gòu)的主要概念和分類；了解算法的概念和主要設(shè)計、分析方法。

1.1從問題到程序

用計算機(jī)解決〔一種〕實際問題，就是在計算機(jī)中建立一個解決問題的模型。程序是使用程序設(shè)計語言精確描述的實現(xiàn)模型，它是問題求解的一個可以在計算機(jī)上運(yùn)行的模型。程序中描述的數(shù)據(jù)用來表示問題中涉及的對象，程序中描述的過程表示了對于數(shù)據(jù)的處理算法；通過接受〔具體〕實際問題的輸入，經(jīng)過程序的運(yùn)行，便可以得到實際問題的一個解。問題求解〔1〕分析階段。

弄清用戶的需求是什么，設(shè)計者根據(jù)它進(jìn)行深入分析，使用標(biāo)準(zhǔn)說明語言〔或數(shù)學(xué)語言等工具〕給出系統(tǒng)的需求模型〔或數(shù)學(xué)模型〕。

問題求解〔2〕設(shè)計階段〔本課討論的重點(diǎn)〕。建立求解系統(tǒng)的實現(xiàn)模型，重點(diǎn)是算法的設(shè)計和數(shù)據(jù)結(jié)構(gòu)的設(shè)計。對于大型的復(fù)雜的系統(tǒng)，還包括抽象數(shù)據(jù)類型或者模塊的設(shè)計。一般而言，設(shè)計過程需要從粗到細(xì)，經(jīng)過屢次精化才能完成。

問題求解〔3〕編碼階段。

根據(jù)設(shè)計的要求，采用適當(dāng)?shù)某绦蛟O(shè)計語言〔C語言、C++語言或Java語言〕，編寫出可執(zhí)行的程序。

問題求解〔4〕測試和維護(hù)。發(fā)現(xiàn)和排除在前幾個階段中產(chǎn)生的錯誤，經(jīng)測試通過的程序便可投入運(yùn)行，在運(yùn)行過程中還可能發(fā)現(xiàn)隱含的錯誤和問題，因此還必須在使用中不斷維護(hù)和完善。

1.1.1問題分析與抽象

為了能正確地解決問題，必須首先深刻地理解需要解決的問題。只有在深刻地認(rèn)識了這個問題以后，才能著手確定這個問題的解決方法。

信號燈問題：為這個路口設(shè)計一個平安有效的交通信號燈的管理系統(tǒng)。信號燈問題－分析

分析所有車輛的行駛路線的沖突問題。這個問題可以歸結(jié)為對車輛的可能行駛方向作某種分組，對分組的要求：使任一個組中各個方向行駛的車輛可以同時平安行駛而不發(fā)生碰撞。信號燈問題－分析可以確定13個可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。

交叉路口行駛沖突的抽象〔不能同時行駛的用線連接〕信號燈問題－抽象要求將圖1.2中的結(jié)點(diǎn)分組，使有線相連(互相沖突)的結(jié)點(diǎn)不在同一個組里。

這個問題的解有許多“可行解〞。我們希望能夠設(shè)計一個最正確〔分組數(shù)最少〕的方案。稱作“最優(yōu)解〞。

著色問題－經(jīng)典問題把上圖中的一個結(jié)點(diǎn)理解為一個國家，結(jié)點(diǎn)之間的連線看作兩國有共同邊界，上述問題就變成著名的“著色問題〞：即求出〔最少〕要幾種顏色可將圖中所有國家著色，使得任意兩個相鄰的國家顏色都不相同。

1.1.2程序的設(shè)計與實現(xiàn)

一個問題的解決可以有許多方法，由于使用的工具是計算機(jī)，所以在選擇方法時必須充分考慮到計算機(jī)的特點(diǎn)和條件，才能找到比較巧妙的方法，比較快而且準(zhǔn)確地計算出需要的結(jié)果。選擇算法－窮舉法具體做法：從分為1、2、3…組開始考察，逐個列舉出所有可能的著色方案，檢查這樣的分組方案是否滿足要求。首先滿足要求的分組，自然是問題的最優(yōu)解。

窮舉法的分析這類窮舉法對結(jié)點(diǎn)少的問題(稱為“規(guī)模小的〞問題)還可以用；對規(guī)模大的問題，由于求解時間會隨著實際問題規(guī)模的增長而指數(shù)性上升，使計算機(jī)無法承受。

貪心法先用一種顏色給盡可能多的結(jié)點(diǎn)上色；然后用另一種顏色在未著色結(jié)點(diǎn)中給盡可能多的結(jié)點(diǎn)上色；如此反復(fù)直到所有結(jié)點(diǎn)都著色為止。

貪心法的一個解(1)紅色：ABACADBADCED

(2)藍(lán)色：BCBDEA

(3)綠色：DADB

(4)白色：EBEC

抽象數(shù)據(jù)類型的選擇為了便于給出上述算法的實現(xiàn)，可以按照抽象數(shù)據(jù)類型的觀點(diǎn)，先把被處理的對象加以抽象。在著色問題中具體解決：使用什么抽象數(shù)據(jù)類型來表示地圖，以及使用什么樣的抽象數(shù)據(jù)類型表示一組國家等。

抽象數(shù)據(jù)類型的選擇使用一個圖〔圖是圖論研究的對象，也是一種重要的抽象數(shù)據(jù)類型?！潮硎镜貓D。使用國名〔圖中結(jié)點(diǎn)名〕的集合表示國家的分組。假設(shè)需要著色的圖是G，G中所有結(jié)點(diǎn)的集合記為G.V，集合V1存放圖中所有未被著色的結(jié)點(diǎn)，集合NEW存放可以用某顏色著色的所有結(jié)點(diǎn)。貪心法的描述

從V1中找出可用新顏色著色的結(jié)點(diǎn)集的工作可以用下面的偽碼描述：

置NEW為空集合;

for每個vV1do

ifv與NEW中所有結(jié)點(diǎn)間都沒有邊

從V1中去掉v;將v參加NEW;這個偽碼如果能執(zhí)行，集合NEW中就得到一組可以用新顏色著色的結(jié)點(diǎn)。著色程序可以反復(fù)調(diào)用這段偽碼，直到V1為空，每次調(diào)用選擇一種新顏色，這段偽碼執(zhí)行的次數(shù)就是需要的不同顏色個數(shù)。

假設(shè)〔ADT〕集合和圖支持下面行為：判斷元素v是否屬于集合V1表示為v

V1；從集合V1中去掉一個元素v表示為remove(V1,v)；向集合NEW里增加一個元素v用add(NEW,v)表示，判斷集合V1是否空集合表示為isEmpty(V1)

檢查結(jié)點(diǎn)v與結(jié)點(diǎn)集合NEW中各結(jié)點(diǎn)之間在圖G中是否有邊連接，用函數(shù)notAdjacentWith(NEW,v,G)表示。

抽象的著色算法intcolorUp(GraphG){ intcolor=0;//記錄使用的顏色數(shù) setV1=G.V;//V1初始化為圖G的結(jié)點(diǎn)集V setNEW; while(!isEmpty(V1)) { NEW={}; while(v

V1.notAdjacentWith(NEW,v,G)) { add(NEW,v);remove(V1,v); } ++color; } returncolor;//返回使用的顏色數(shù)}數(shù)據(jù)結(jié)構(gòu)的設(shè)計如果集合和圖是程序設(shè)計語言中預(yù)定義的類型，那么colorUp中用到的remove(V1,v)和add(NEW,v)等就應(yīng)該是語言中預(yù)定義的內(nèi)部函數(shù)，該程序就幾乎可以直接上機(jī)運(yùn)行。否那么程序員需要自己用語言所提供的〔類型〕機(jī)制實現(xiàn)這些抽象數(shù)據(jù)類型〔集合、圖等〕，這些正是數(shù)據(jù)結(jié)構(gòu)設(shè)計要討論的內(nèi)容。算法的精化在數(shù)據(jù)結(jié)構(gòu)確定以后，算法的描述可以進(jìn)一步根據(jù)設(shè)計的數(shù)據(jù)結(jié)構(gòu)進(jìn)行精化。如果這個問題仍然是個比較復(fù)雜的問題，就還需要選擇算法，也可能存在需要新抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)。經(jīng)過這種反復(fù)的精化過程，最后將算法中所有局部都細(xì)化為能用程序設(shè)計語言描述的成分，得到的就是我們希望的程序。1.2抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型的概念最早出現(xiàn)在20世紀(jì)70年代，它是面向?qū)ο蠓椒ǖ闹匾碚摳?。本書在?nèi)容的組織中僅僅使用了抽象數(shù)據(jù)類型的概念，而沒有嚴(yán)格采用面向?qū)ο蟮某绦蛟O(shè)計語言的描述機(jī)制〔例如class〕。根本概念－類型類型〔type〕是一組值〔或者對象〕的集合。例如：布爾作為一種類型是由真〔true〕和假〔false〕兩個值組成的集合；布爾向量也可以作為一種類型，它的每個值是一個由true或false構(gòu)成的向量。根本概念－數(shù)據(jù)類型數(shù)據(jù)類型〔datatype〕通常是指在計算機(jī)〔語言〕中可以使用的一個類型，它不但包括這個類型的值的集合，還包括定義在這個類型上的一組操作。例如：整數(shù)作為一個數(shù)據(jù)類型是指在計算機(jī)上所能表示的〔不是數(shù)學(xué)意義上任意大小的〕所有整數(shù)和語言中定義的對于這些整數(shù)的全部操作〔整數(shù)的加、減、乘、除、取余等〕。根本概念－抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型〔AbstractDataType簡稱為ADT〕可以定義作具有一定行為(操作)的抽象〔數(shù)學(xué)〕類型。它不關(guān)心類型中值的具體表示方式和數(shù)據(jù)類型中定義的各種操作的具體實現(xiàn)方法，是所有可能的值的具體表示和各種操作的具體實現(xiàn)的抽象。意義和作用〔1〕抽象數(shù)據(jù)類型的實質(zhì)是抽象出了數(shù)據(jù)類型的使用要求，而把它的具體表示方式和運(yùn)算的實現(xiàn)細(xì)節(jié)都隱藏起來。抽象數(shù)據(jù)類型僅僅規(guī)定了數(shù)據(jù)類型應(yīng)該具有的行為〔操作〕。一旦抽象數(shù)據(jù)類型被正確實現(xiàn)，就好似程序設(shè)計語言中所提供的數(shù)據(jù)類型那樣，可以被自由使用。意義和作用〔2〕抽象數(shù)據(jù)類型支持?jǐn)?shù)據(jù)類型的實現(xiàn)與使用別離的原那么，允許獨(dú)立地考慮數(shù)據(jù)類型的外部接口和內(nèi)部的實現(xiàn)。這使應(yīng)用程序只要按抽象數(shù)據(jù)類型的接口統(tǒng)一其使用界面；可以不管其是否已經(jīng)實現(xiàn)，也不管它是如何實現(xiàn)的。對于系統(tǒng)的分解、設(shè)計、維護(hù)和修改均十分有利。

例1－抽象數(shù)據(jù)類型圓

ADTCircleis

operations area 計算圓的面積 circumference 計算圓的周長 getRadius 獲取圓的半徑 setRadius 設(shè)置圓的半徑endADTCircle例2－集合抽象數(shù)據(jù)類型ADTSetis

Operations isEmpty 判斷集合是否是空集合 add 給集合增加一個元素 remove 刪除集合中的一個元素 isIn 判斷一個元素是否在當(dāng)前集合中end

ADTSet1.3數(shù)據(jù)結(jié)構(gòu)關(guān)于數(shù)據(jù)結(jié)構(gòu)的研究，可以追溯到1972年C.A.R.Hoare奠基性的論文《數(shù)據(jù)結(jié)構(gòu)筆記》；而現(xiàn)代計算機(jī)所大量采用的根本數(shù)據(jù)結(jié)構(gòu)，最早的系統(tǒng)論述應(yīng)歸功于1973年D.E.Knuth的名著《計算機(jī)程序設(shè)計技巧》的問世。為了學(xué)習(xí)和研究的方便，計算機(jī)科學(xué)家把常用的數(shù)據(jù)進(jìn)行分類，總結(jié)出許多典型的數(shù)據(jù)結(jié)構(gòu)。什么是數(shù)據(jù)結(jié)構(gòu)〔通?！晨梢园褦?shù)據(jù)結(jié)構(gòu)理解為：計算機(jī)中表示〔存儲〕的、具有一定〔邏輯〕關(guān)系和行為的一組數(shù)據(jù)。其中的每個數(shù)據(jù)(元素)稱為這個結(jié)構(gòu)的一個結(jié)點(diǎn)?！哺鶕?jù)面向?qū)ο蟮挠^點(diǎn)〕可以把數(shù)據(jù)結(jié)構(gòu)理解成為抽象數(shù)據(jù)類型的物理實現(xiàn)。主要解決兩個問題：如何具體表示抽象數(shù)據(jù)類型中的數(shù)學(xué)模型；如何給出抽象數(shù)據(jù)類型中需要操作的實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)三要素：邏輯結(jié)構(gòu):指數(shù)學(xué)模型中的根本元素〔結(jié)點(diǎn)〕和元素之間的相互關(guān)系。存儲結(jié)構(gòu):指數(shù)學(xué)模型的具體表示方式，包括結(jié)點(diǎn)的表示和關(guān)系的表示。操作:指抽象數(shù)據(jù)類型關(guān)心的各種行為在存儲結(jié)構(gòu)上的具體實現(xiàn)〔算法〕。例子－集合從集合抽象數(shù)據(jù)類型的定義出發(fā)，將討論它的實現(xiàn)——集合數(shù)據(jù)結(jié)構(gòu)：根據(jù)數(shù)學(xué)的概念，集合中的元素是各不相同而且無序的〔邏輯結(jié)構(gòu)〕；將介紹使用順序表、單鏈表、散列表等等許多不同的集合表示方法〔存儲結(jié)構(gòu)〕；并且在這些不同的表示根底上，給出各自的行為實現(xiàn)算法〔操作〕。1.3.2數(shù)據(jù)結(jié)構(gòu)的分類主要根據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)進(jìn)行分類

邏輯結(jié)構(gòu)B=<K，R>K是結(jié)點(diǎn)的有窮集合，R是K上的一個關(guān)系。K上的一個關(guān)系就是K上的一些二元組組成的集合K上的二元組是K中元素的有序?qū)?假設(shè)k,k’K,<k,k’>R，那么稱k為k’的前驅(qū)，k’為k的后繼。沒有前驅(qū)的結(jié)點(diǎn)稱為開始結(jié)點(diǎn)，沒有后繼的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)。

K上不同的二元組集合構(gòu)成不同的關(guān)系。邏輯結(jié)構(gòu)的概念按邏輯結(jié)構(gòu)分類

根據(jù)R的特點(diǎn)可以將數(shù)據(jù)結(jié)構(gòu)分為以下三類：線性結(jié)構(gòu)：K中每個結(jié)點(diǎn)最多只有一個前驅(qū)和一個后繼的結(jié)構(gòu)。樹形結(jié)構(gòu)：K中每個結(jié)點(diǎn)最多只有一個前驅(qū)，但可有多個后繼的結(jié)構(gòu)。復(fù)雜結(jié)構(gòu)：K中結(jié)點(diǎn)的前驅(qū)、后繼結(jié)點(diǎn)個數(shù)都不作限制的結(jié)構(gòu)。*集合：它可以看成R為空的情況，即結(jié)點(diǎn)之間沒有任何關(guān)系。

按邏輯結(jié)構(gòu)分類舉例

線性結(jié)構(gòu)舉例樹形結(jié)構(gòu)舉例

復(fù)雜結(jié)構(gòu)舉例

存儲結(jié)構(gòu)的概念存儲結(jié)構(gòu):數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲(表示)。通常包括結(jié)點(diǎn)的表示和關(guān)系的表示。同一種邏輯結(jié)構(gòu)，可以采用不同的表示方式。例如，線性表既可以用順序〔一維數(shù)組〕的方式來表示〔順序表〕，也可以用鏈接的方式〔使用指針〕來表示〔單鏈表或雙鏈表〕。存儲結(jié)構(gòu)的設(shè)計目標(biāo)，是使用比較少的空間記錄邏輯結(jié)構(gòu)的必要信息，還能夠有效實現(xiàn)(抽象數(shù)據(jù)類型中)要求的操作。根據(jù)存儲結(jié)構(gòu)分類：順序表示：用一個連續(xù)的空間，順序存放數(shù)據(jù)結(jié)構(gòu)中的各個結(jié)點(diǎn)?！步Y(jié)點(diǎn)的關(guān)系需要另外存儲或者隱含其中〕鏈接表示：結(jié)點(diǎn)的存放位置是任意的，結(jié)點(diǎn)之間的關(guān)系通過與結(jié)點(diǎn)關(guān)聯(lián)的指針〔或者引用〕方式顯式表達(dá)出來。散列表示：又稱為關(guān)鍵碼——地址轉(zhuǎn)換法。即選擇適當(dāng)?shù)纳⒘小搽s湊〕函數(shù)，根據(jù)關(guān)鍵碼的值將結(jié)點(diǎn)映射到給定的存儲空間〔散列表〕中。索引表示：索引與散列一樣，都給出一種從關(guān)鍵碼到存儲地址的映射方法。不同的是，散列法的映射是通過函數(shù)定義；而索引法是通過建立輔助的索引結(jié)構(gòu)解決。1.3.3結(jié)點(diǎn)與結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)的討論中重點(diǎn)研究的是“結(jié)構(gòu)〞，而把組成結(jié)構(gòu)的那些元素抽象成一個“結(jié)點(diǎn)〞。結(jié)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)中的根本單位，在實際應(yīng)用中一個結(jié)點(diǎn)可以是一個字符、一個整數(shù)〔初等類型〕，也可以是一個結(jié)構(gòu)〔組合類型〕。1.3.4外存數(shù)據(jù)的組織

簡單介紹常用的外存設(shè)備及其特點(diǎn)，討論文件的結(jié)構(gòu)和處理。掌握這些知識，對于理解涉及到外存上的數(shù)據(jù)結(jié)構(gòu)〔例如B/B+樹〕與算法〔例如歸并排序〕會有幫助.根本概念文件是邏輯記錄的集合。邏輯記錄〔簡稱記錄〕是應(yīng)用程序需要進(jìn)行內(nèi)外存交換的邏輯單位。每個記錄可以包含假設(shè)干數(shù)據(jù)項，其中能夠唯一標(biāo)識該記錄的數(shù)據(jù)項稱為關(guān)鍵碼。對外存的數(shù)據(jù)必須按頁塊存取。頁塊又稱物理記錄，是內(nèi)存與外存進(jìn)行交換的物理單位。外存設(shè)備目前廣泛使用的外存儲器有磁帶、磁盤、光盤和優(yōu)盤等。其中以磁帶和磁盤最具代表性。

外存的存取外存儲器上的邏輯記錄的地址由兩局部表示：邏輯記錄所在物理記錄的地址；邏輯記錄在物理記錄內(nèi)的相對位置。節(jié)省外存的存取時間的關(guān)鍵在于減少訪外的次數(shù)。由于緩沖區(qū)的大小受到內(nèi)存容量的限制，所以減少訪外次數(shù)的有效方法是精心設(shè)計文件的結(jié)構(gòu)，使外存中存放的記錄，相互關(guān)聯(lián)，以便于處理。1.4算法本課是以數(shù)據(jù)結(jié)構(gòu)為主線，算法為輔線組織內(nèi)容。因為每種數(shù)據(jù)結(jié)構(gòu)上的操作，都需要一定算法。對于不同存儲結(jié)構(gòu)的選擇與評價，算法的好壞起著決定的因素。所有算法的實現(xiàn)也都需要數(shù)據(jù)結(jié)構(gòu)的支持。算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計的兩大支柱。它們相輔相成，互相依賴。

什么是算法算法是由有窮規(guī)那么構(gòu)成〔為解決某一類問題〕的運(yùn)算序列。算法可以有假設(shè)干輸入(初始值或條件)；算法通常又有假設(shè)干個輸出(計算結(jié)果〕。算法應(yīng)該具有有窮性。一個算法必須在執(zhí)行了有窮步之后結(jié)束。算法應(yīng)該具有確定性。算法的每一步，必須有確切的定義。算法應(yīng)該具有可行性。算法中的每個動作，原那么上都是能夠由機(jī)器或人準(zhǔn)確完成的。算法的正確性如果一個算法以一組滿足初始條件的輸入開始，那么該算法的執(zhí)行一定終止，并且在終止時得到滿足要求的〔輸出〕結(jié)果。算法設(shè)計的方法貪心法分治法回溯法動態(tài)規(guī)劃法分枝界限法貪心法根本思想是：當(dāng)追求的目標(biāo)是一個問題的最優(yōu)解時，設(shè)法把對整個問題的求解工作分成假設(shè)干步驟來完成。在其中的每一個階段都選擇從局部看是最優(yōu)的方案，以期望通過各階段的局部最優(yōu)選擇到達(dá)整體的最優(yōu)。算法1.1解著色問題時就是采用的貪心法。貪心法實際上不能保證都成功地產(chǎn)生一個全局性最優(yōu)解，但是通?？梢缘玫揭粋€可行的較優(yōu)解?！才e例〕分治法根本思想是:把一個規(guī)模較大的問題分成兩個或多個較小的與原問題相似的子問題。首先對子問題進(jìn)行求解，然后設(shè)法把子問題的解合并起來，得出整個問題的解，即對問題分而治之。如果一個子問題的規(guī)模仍然比較大，不能很容易地求得解，就可以對這個子問題重復(fù)地應(yīng)用分治策略。二分法檢索就是用分治策略的典型例子?；厮莘ǜ舅枷胧?有一些問題，需要通過徹底搜索所有可能情況尋找一個滿足某些預(yù)定條件的最優(yōu)解。由于徹底搜索的運(yùn)算量通常非常大，所以采取一步一步向前試探，當(dāng)有多種選擇時可以任意選擇一種，只要目前可行就繼續(xù)向前，一旦發(fā)現(xiàn)問題或失敗就后退，回到上一步重新選擇，借助于回溯技巧和中間增加判斷，這樣常常可以大大地減少搜索時間。常見的迷宮問題以及八皇后問題都可以用回溯方法來解決。動態(tài)規(guī)劃法與分治法相似都是把一個大問題分解為假設(shè)干較小的子問題，通過求解子問題而得到原問題的解。不同點(diǎn)是：分治法每次分解的子問題數(shù)目比較少，子問題之間界限清楚，處理的過程通常是自頂向下進(jìn)行；動態(tài)規(guī)劃法分解的子問題可能比較多，而且子問題相互包含，為了重用已經(jīng)計算的結(jié)果，要把計算的中間結(jié)果全部保存起來，通常是自底向上進(jìn)行。在帶權(quán)圖中，求所有結(jié)點(diǎn)之間最短路徑的Floyd算法〔見第9章〕就屬于動態(tài)規(guī)劃法。分枝界限法與回溯法相似，也是一種在表示問題解空間的樹上進(jìn)行系統(tǒng)搜索的方法。所不同的是，回溯法使用了深度優(yōu)先策略，而分枝界限法一般采用廣度優(yōu)先策略或者采用最大收益〔或最小損耗〕策略，并且利用最優(yōu)解屬性的的上下界來控制搜索的分枝。最后一章，在討論背包問題時，介紹了一個用分枝界限法設(shè)計的算法。1.4.3算法的精化實現(xiàn)一個算法，就是要把設(shè)計者頭腦中的算法思想轉(zhuǎn)化成計算機(jī)中可以執(zhí)行的程序。對于一個比較復(fù)雜的算法，其實現(xiàn)的過程往往需要經(jīng)過屢次細(xì)化才能完成。習(xí)慣上，把這個過程稱為算法的精化。排序問題假設(shè)有n≥1個不同的整數(shù)a0，a1，…，an-1，要求把這些整數(shù)從大到小進(jìn)行排序。排序算法可以明確地用下面的輸入和輸出關(guān)系來描述其功能：輸入：是含n個元素的整數(shù)數(shù)組，記為a，其中的元素依次為：a[0],a[1],…,a[n-1]。輸出：是輸入數(shù)組a中元素重新排列，記為a'，其中的元素依次為：a'[0],a'[1],…,a'[n-1]，滿足a'[i]≥a'[i+1]，對所有的0≤i<n-1都成立直接選擇排序的思想1從a中選出一個最大的整數(shù)放到一個空的數(shù)組a'中，作為a'中的第一個元素。2從a中剩下的元素中再選出最大的整數(shù)放到a'中，接在前一個已放入元素的后面。反復(fù)執(zhí)行步驟2，直到a中所有整數(shù)都放到排好序的數(shù)組a'中。第一步精化:將排序后的數(shù)據(jù)仍然存儲在排序前的數(shù)組里1從a[0]到a[n-1]中選出最大整數(shù)，設(shè)為a[j]，把a(bǔ)[0]與a[j]進(jìn)行交換。2從a[1]到a[n-1]中選出最大整數(shù)，設(shè)為a[j]，把a(bǔ)[1]與a[j]進(jìn)行交換。…………n從a[n-1]到a[n-1]中選出最大整數(shù)，設(shè)為a[j]，把a(bǔ)[n-1]與a[j]進(jìn)行交換〔因為j=n-1,故這步可省〕。第二步精化:把上面執(zhí)行n次重復(fù)的工作，精化成一個循環(huán)。i以1為步長，從0到n-2，循環(huán)執(zhí)行：(1)從a[i]到a[n-1]中選出最大的整數(shù)，設(shè)為a[j]。(2)把a(bǔ)[i]與a[j]進(jìn)行交換。第三步精化循環(huán)i以1為步長，從0到n-2，執(zhí)行(1)j←i(2)循環(huán)k以1為步長，從i+1到n-1，執(zhí)行：

假設(shè)a[k]>a[j]，那么j←k(3)t←a[i]；a[i]←a[j]；a[j]←t使用C語言的函數(shù)形式描述的算法voidsortIntArray(int[]a，intn){ inti,j,k,t; for(i=0;i<n-1;i=i+1){ j=i;/*把a(bǔ)[i]作為最大整數(shù)的初值*/ for(k=i+1;k<n-1;k=k+1)/*從a[i]到a[n-1]中選出最大整數(shù)*/ if(a[k]>a[j]) j=k; t=a[i];a[i]=a[j];a[j]=t; }}1.4.4算法分析分析一個算法主要是看這個算法的執(zhí)行需要花費(fèi)多少機(jī)器資源。在進(jìn)行算法分析時人們最關(guān)心的就是運(yùn)行算法所要花費(fèi)的時間和算法中使用的各種數(shù)據(jù)占有的空間。在文獻(xiàn)中習(xí)慣稱之為算法的時間代價和空間代價。根本概念算法的空間代價(或稱空間復(fù)雜性)：當(dāng)被解決問題的規(guī)模(以某種單位計算)由1增至n時，解該問題的算法所需占用的空間也以某種單位由f(1)增至f(n)，這時我們稱該算法的空間代價是f(n)。算法的時間代價(或稱時間復(fù)雜性)：當(dāng)問題規(guī)模以某種單位由1增至n時，對應(yīng)算法所消耗的時間也以某種單位由g(1)增至g(n)，這時我們稱該算法的時間代價是g(n)。問題的規(guī)模、

空間單位和時間單位問題的規(guī)模一般可以根據(jù)問題本身的提法確定。例如對n個記錄進(jìn)行排序，這里n即可以作為問題的規(guī)模。空間單位和時間單位沒有統(tǒng)一的規(guī)定，通常取算法描述中的初等數(shù)據(jù)占用的空間和根本操作消耗的時間為單位。大O表示法在描述算法分析的結(jié)果時，人們通常采用大O表示法：說某個算法的時間代價(或者空間代價)為O(f(n))，如果存在正的常數(shù)c和n0，當(dāng)問題的規(guī)模n≥n0后，該算法的時間(或空間)代價T(n)≤c·f(n)。這時也稱該算法的時間(或空間)代價的增長率為f(n)。最壞情況下代價的數(shù)量級每個算法的實際運(yùn)行時的代價并不是固定不變的。由于不同的輸入?yún)?shù)，可能使一個算法的實際代價出現(xiàn)很大差異。要全面分析一個算法，應(yīng)該考慮它在最壞情況下的代價、最好情況下的代價和平均情況下的代價等。本書不是專門討論算法分析的教材，所以在分析算法時主要考慮它們在最壞情況下的代價，而且僅僅要求計算它們的數(shù)量級。大O表示法說某個算法的時間代價(或者空間代價)為O(f(n))，如果存在正的常數(shù)c和n0，當(dāng)問題的規(guī)模n≥n0后，該算法的時間(或空間)代價T(n)≤c·f(n)。也稱該算法的時間(或空間)代價的增長率為f(n)。例如，如果有T(n)=3n3，很容易證明T(n)=O(n3)。當(dāng)然我們也可以證明T(n)=O(n4)。但從分析的精度來看，前一結(jié)論給出的是上確界(上界中最小的)，后者給出的僅是一般上界中的一個。計算規(guī)那么1)加法規(guī)那么T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n),f2(n)))2)乘法規(guī)那么T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))

對于大O表示法，以非零正常數(shù)c形成的復(fù)雜性度量O(c)都居于同一個量級，人們習(xí)慣把它們統(tǒng)一記為O(1)。c<log2n<