數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)提綱（詳細(xì)版）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)提綱（詳細(xì)版）=stackSize）2、棧的應(yīng)用（分析算法思想：首先創(chuàng)立一個(gè)空棧并順序讀入符號）⑴、平衡符號（關(guān)鍵：三種出錯(cuò)狀況）

⑵、后綴表達(dá)式（遇見數(shù)則壓棧；遇見操作符則連續(xù)兩次彈棧，計(jì)算后再壓棧）

⑶、中綴到后綴的轉(zhuǎn)換（遇見數(shù)輸出/遇見操作符，級別高則入棧，否則一直彈棧直到遇見級別更低的操作符/遇見（，入棧，直到遇見），則將（）之間的所有操作符彈棧）

五、隊(duì)列ADT（循環(huán)隊(duì)列）

1、★重要概念：頭指針和尾指針（front：指向?qū)︻^元素；rear：指向隊(duì)尾元素下一個(gè)位置）2、★重要操作：入隊(duì)和出隊(duì)（入隊(duì)rear++；出隊(duì)front++）

3、★重要條件（隊(duì)空條件：front=rear；隊(duì)滿條件：front=（rear+1）%maxSize

第四章樹

一、二叉查找樹

1、二叉查找樹的概念（對于每個(gè)結(jié)點(diǎn)X，左子樹中的所有結(jié)點(diǎn)的值>：：const_iteratoritr；）

第五章散列

一、★★鏈地址法

1、基本思想（將hash值一致的所有記錄保存在同一個(gè)線性鏈表中）2、實(shí)現(xiàn)鏈地址法的HashTable類模板

⑴、數(shù)據(jù)成員（thelists（鏈表數(shù)組）和currentsize（已存儲結(jié)點(diǎn)個(gè)數(shù)））⑵、核心操作：myhash（）（散列到適合位置）⑶、基本操作：makeEmpty（）和contains（）（關(guān)鍵：利用find例程）⑷、重要操作：insert（）和remove（）

二、★★探測法

1、基本思想（hi（x）=（hash（x）+f（i））modTableSize；其中f為沖突解決函數(shù)）2、線性探測法和平方探測法（f（i）=i；f（i）=i2）3、實(shí)現(xiàn)探測法的HashTable類模板

⑴、數(shù)據(jù)成員（HashEntry（通過HashType）定義；數(shù)組array和currentsize）⑵、核心操作：findPos（）（若x存在，返回位置；否則返回待插入位置）⑶、基本操作：makeEmpty（）（關(guān)鍵：打上EMPTY標(biāo)記）⑷、重要操作：insert（）和remove（）

三、★再散列（3個(gè)基本步驟：備份；增容并初始化；拷貝）1、鏈地址法的再散列2、探測法的再散列

=npl（右孩子））⑶、定理：在右路徑上有r個(gè)結(jié)點(diǎn)的左式堆至少有2r-1個(gè)結(jié)點(diǎn)（左側(cè)全部鋪滿）2、★★左式堆的類模板（LeftistHeap）

⑴、數(shù)據(jù)成員（LeftistNode*root；左式堆結(jié)點(diǎn)LeftistNode增加一個(gè)npl字段）

⑵、關(guān)鍵操作：merge操作（驅(qū)動程序加兩個(gè)merge完成；思想：大的合并到小的右子樹）⑶、重要操作：insert操作和deleteMin操作

3、斜堆（斜堆與左式堆的關(guān)系，類似伸展樹與AVL樹的關(guān)系）⑴、概念：斜堆（具有堆序性質(zhì)的二叉樹）（即左式堆去掉npl限制）

⑵、基本操作：merge（除右路徑上最終一個(gè)結(jié)點(diǎn)，每次合并都必需交換）

三、★★二項(xiàng)隊(duì)列1、基本概念和性質(zhì)

⑴、概念：二項(xiàng)樹（雙重條件：堆序；Bk的遞歸定義）⑵、重要概念：二項(xiàng)隊(duì)列（由若干棵二項(xiàng)樹構(gòu)成）

⑶、重要性質(zhì)（二項(xiàng)隊(duì)列的兩特性質(zhì)：每個(gè)高度上至多有一棵二項(xiàng)樹；可以用二項(xiàng)樹的集合唯一表示任意大小的優(yōu)先隊(duì)列）

2、★★二項(xiàng)隊(duì)列的類模板（BinomialQueue）

⑴、結(jié)點(diǎn)類BinomialNode（孩子兄弟表示法：leftchild指向結(jié)點(diǎn)最多的子樹；rightsibling）⑵、數(shù)據(jù)成員（指針數(shù)組theTrees；currentSize（按遞減方式存放））⑶、核心操作：combineTrees（同等高度的合并；保持堆序性質(zhì)）

⑷、基本操作：merge（三個(gè)步驟：resize、carry和whichcase、清空（currentSize的作用））⑸、重要操作：findMinIndex（尋覓最小項(xiàng)）和deleteMin（H2：deletedTree和deletedQueue）

第七章排序

一、★插入排序

1、算法思想（插入到前面有序序列）

2、插入算法（關(guān)鍵：分析明白邊界狀況（i控制插入趟數(shù)，j控制每趟中的插入位置））

二、一些簡單排序算法的下界

1、逆序的概念、性質(zhì)（一次相鄰結(jié)點(diǎn)的交換，逆序改變1；逆序數(shù)=插入算法比較次數(shù)））2、定理：N個(gè)互異元素的數(shù)組，其平均逆序數(shù)為N（N-1）/4

3、定理：通過交換相鄰元素進(jìn)行排序的任何算法平均需要Ω（N2）時(shí)間

三、希爾排序（ShellSort，縮減增量排序）

1、算法思想（由若干趟Hk排序構(gòu)成；每趟Hk排序使用插入算法）

2、使用希爾增量的希爾排序（關(guān)鍵：三重循環(huán)（gap表Shell增量，i和j作用同插入排序）3、定理：使用希爾增量的希爾排序的最壞運(yùn)行時(shí)間為Ω（N2）（注意構(gòu)造和嚴(yán)格證明）

四、★堆排序（heapSort）

1、算法思想（兩個(gè)步驟：創(chuàng)立大堆；首尾交換并下濾）

2、堆排序算法（關(guān)鍵：基于二叉堆的buildHeap和percolateDown（修改為大堆））

五、★★歸并排序（mergeSort）

1、算法思想（分治算法；合并兩個(gè)已排序的表）

2、歸并算法（由驅(qū)動程序、mergeSort和merge構(gòu)成；關(guān)鍵：tempArray臨時(shí)數(shù)組；而merge包含三個(gè)while和一個(gè)拷貝）

3、★算法分析（關(guān)鍵公式：T（N）=2T（N/2）+N，疊縮求和法）

六、★★快速排序（quickSort）

1、算法思想（分治算法：選取樞紐元素pivot；將S分割S1和S2；對S1和S2遞歸調(diào)用）2、快速算法（median3（關(guān)鍵：3元素中值法選取樞紐元素）；quickSort（關(guān)鍵：i向右探尋第一個(gè)≥pivot的結(jié)點(diǎn)，j相反操作（注意i和j起始位置）；還原pivot并從i處分割）3、★★算法分析（關(guān)鍵公式：T（N）=T（i）+T（N-i-1）+CN）（i為S1中元素個(gè)數(shù)）

七、其它

1、間接排序（解決comparable對象復(fù)制代價(jià)太高的問題）

2、定理：只使用元素間比較的任何排序算法需要Ω（NlogN）次比較3、桶排序（前提條件（正整數(shù)）和算法思想）4、外部排序

⑴、外部排序的概念（大文件的排序，排序過程中需要進(jìn)行屢屢的內(nèi)、外存之間的交換）⑵、基本思想（歸并算法）

第八章不相交集

一、基本操作

1、find（x）操作（查找操作：返回x所屬的集合）

2、unionSets（S1，S2）操作（求并操作：求集合S1和S2的并）

二、DisjSets類（不相交集類）

1、基本思想（利用樹表示每個(gè)集合，根表示這個(gè)集合的名稱；整個(gè)集合表示為一顆森林）2、基本數(shù)據(jù)結(jié)構(gòu)（關(guān)鍵：雙親表示法）⑴、數(shù)據(jù)成員（數(shù)組S：（S[i]為i的雙親，其中-1表示根））⑵、構(gòu)造函數(shù)（數(shù)組S全部初始化為-1）

⑶、基本操作：find（）操作和unionSets（）操作3、算法分析（unionSets操作為O（1），find操作的最壞情形為O（1））

三、靈敏求并算法

第八章不相交集類

一、基本概念

1、關(guān)系R：ARelationRisdefinedonasetSisforeverypair（a，b），a，b∈S，eitherTrueorFalse.

2、等價(jià)關(guān)系：滿足自反、對稱和傳遞等三條性質(zhì)的關(guān)系3、等價(jià)類（更確鑿的名稱為：集合S上的R關(guān)系等價(jià)類）等價(jià)類的作用：形成對集合S的一個(gè)劃分

（即：根據(jù)關(guān)系R將集合S劃分為S1，S2，S3??等等）

二、基本操作

1、find（x）操作：Returnthenameofsetcontainingagivenelement.2、unionSets（S1，S2）操作：（求并操作）UniontwodisjointsetsS1，S2

（對兩個(gè)不相交的非空集合S1和S2求并）

三、不相交集類的基本數(shù)據(jù)結(jié)構(gòu)1、數(shù)據(jù)結(jié)構(gòu)的表示

⑴、Useatreetorepresenteachset，therootcanbeusedtonametheset.

（利用樹來表示每一個(gè)集合，而且利用該樹的根結(jié)點(diǎn)來表示這個(gè)集合的名稱）⑵、這樣，整個(gè)集合S可表示為一顆森林2、數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

采用雙親表示法實(shí)現(xiàn)（注意：雙親表示法是利用數(shù)組來存貯一棵樹）其中：

⑴、S[i]表示元素i的雙親結(jié)點(diǎn)⑵、若i是根結(jié)點(diǎn)，則S[i]＝－13、★★不相交集類的算法實(shí)現(xiàn)

（包括類的定義、構(gòu)造函數(shù)的實(shí)現(xiàn)以及兩個(gè)基本操作find和unionSets的實(shí)現(xiàn)）4、★算法分析

⑴、unionSets操作的時(shí)間繁雜度為O（1）⑵、find操作的最壞時(shí)間繁雜度為O（N）

Ⅰ、unionSets操作和find操作在算法效率上是一對矛盾的操作Ⅱ、連續(xù)的求并操作，在最壞狀況下會建立起一棵深度為N-1的樹Ⅲ、一般狀況下，運(yùn)行時(shí)間使針對連續(xù)混和使用M個(gè)指令來計(jì)算的

在這種狀況下，M次連續(xù)操作在最壞情形下可能花費(fèi)O（MN）時(shí)間

四、算法的改進(jìn)

1、unionSets操作的改進(jìn)

⑴、按大小求并（與按高度求并十分類似）

⑵、按高度求并（保證將比較淺的子樹并入比較深的子樹）思路1：可利用每個(gè)根的數(shù)據(jù)元素來存貯整顆子樹高度的負(fù)值

思路2：為了同原算法類定義和構(gòu)造函數(shù)實(shí)現(xiàn)的兼容，我們假定只有一個(gè)根結(jié)點(diǎn)的樹的高度為－1，依此類推⑶、★算法分析

兩種算法都將find操作的時(shí)間繁雜度改進(jìn)為O（logN）（給出詳細(xì)的證明）

（另外的一個(gè)結(jié)論是：對于連續(xù)M個(gè)指令，平均需要O（M）時(shí)間，

但最壞情形還是O（MlogN））

2、find操作的改進(jìn)－路徑壓縮（Pathcompression）⑴、路徑壓縮的概念：

Everynodeonthepathfromxtotheroothasitsparentchangedtotheroot.（從x到根的路徑上每一個(gè)結(jié)點(diǎn)都使它的父結(jié)點(diǎn)變成根）⑵、★路徑壓縮的算法實(shí)現(xiàn)

⑶、結(jié)論：路徑壓縮與按大小求并完全兼容，與按高度求并部分兼容

五、按秩求并和路徑壓縮的最壞情形

1、秩（rank）的概念：一個(gè)結(jié)點(diǎn)的秩，是指以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹的高度2、幾個(gè)重要引理⑴、引理1：當(dāng)執(zhí)行一系列union指令以后，一個(gè)秩為r的結(jié)點(diǎn)必然至少有2r個(gè)后裔結(jié)點(diǎn)（包括它自己）

⑵、引理2：秩為r的結(jié)點(diǎn)至多有N/2r個(gè)

⑶、引理3：在求并查找算法的任意時(shí)刻，從樹葉到根結(jié)點(diǎn)路徑上的結(jié)點(diǎn)的秩單調(diào)增加3、★重要定理：

當(dāng)使用求并探測法和路徑壓縮時(shí)，算法在最壞狀況下需要的時(shí)間為O（α（M，N））其中，α（M，N）是Ackermann函數(shù)的逆

（推論：任意次序的M=Ω（N）次union/find操作花費(fèi)的總運(yùn)行時(shí)間為O（Mlog*N））

六、迷宮問題

1、算法思想：對于隨機(jī)選中的一堵墻，使用union/find操作2、算法分析：時(shí)間繁雜度為O（Nlog*N）

第九章圖論算法

一、圖的表示

1、鄰接矩陣（adjacentmatrix）表示法（分析優(yōu)缺點(diǎn)）2、★鄰接表（adjacencylist）

Ⅰ、對每一個(gè)頂點(diǎn)，使用一個(gè)鏈表來存放與之鄰接的所有頂點(diǎn)Ⅱ、圖的鄰接表的一種簡單的表示方式：Vectorarray（使用一個(gè)數(shù)組來存放所有的頂點(diǎn)）

二、拓?fù)渑判?/p>

1、概念：拓?fù)渑判蚴菍τ邢驘o環(huán)圖的頂點(diǎn)的一種排序

2、★★拓?fù)渑判虻乃惴ㄋ枷耄梢允褂肧tack或者Queue來實(shí)現(xiàn)）⑴、計(jì)算每一個(gè)頂點(diǎn)的入度

⑵、將所有入度為0的頂點(diǎn)放入一個(gè)初始為空的隊(duì)列中

⑶、若隊(duì)列非空，則v出隊(duì)，且所有與v鄰接的頂點(diǎn)的入度減1⑷、若有頂點(diǎn)的入度降為0，則該頂點(diǎn)入隊(duì)3、★拓?fù)渑判虻乃惴ǎㄊ褂脗未a描述）（注意：利用一個(gè)輔助變量來判斷是否出現(xiàn)回路）4、★算法分析：時(shí)間繁雜度為O（|E|+|V|）

三、最短路徑

1、無權(quán)最短路徑（加權(quán)最短路徑的特別情形）

⑴、采用廣度優(yōu)先探尋（Breadth–FirstSearch）的策略（層次遍歷的推廣）⑵、★Vertex的數(shù)據(jù)結(jié)構(gòu)

Ⅰ、known：當(dāng)一個(gè)頂點(diǎn)被訪問以后，其known置為trueⅡ、dist：從s到該頂點(diǎn)的距離

Ⅲ、path：引起dist變化的最終頂點(diǎn)（通過追溯path，可以得到s到該頂點(diǎn)的完整最短路徑）⑶、★無權(quán)最短路徑的算法思想和算法（關(guān)鍵：使用一個(gè)隊(duì)列來實(shí)現(xiàn)）

⑷、算法分析：時(shí)間繁雜度為O（|E|+|V|）

2、加權(quán)最短路徑

⑴、貪心算法（greedalgorithm）

Ⅰ、Solvetheprobleminstages（分階段進(jìn)行）Ⅱ、每個(gè)階段都把出現(xiàn)的方案當(dāng)成最優(yōu)的解決方案⑵、、★★Dijkstra算法思想和算法Ⅰ、對所有結(jié)點(diǎn)初始化

Ⅱ、在所有known標(biāo)記為false的結(jié)點(diǎn)中，尋覓一個(gè)其dist值最小的結(jié)點(diǎn)

Ⅲ、掃描與v鄰接的所有known標(biāo)記為false的結(jié)點(diǎn)w，分析是否有必要update其dist值Ⅳ、更新w的path

⑶、★★Dijkstra的算法分析

Ⅰ、常規(guī)方法：通過掃描存放頂點(diǎn)的數(shù)組來尋覓最小值，時(shí)間是O（|E|+|V|2）Ⅱ、使用優(yōu)先隊(duì)列的deleteMin方法尋覓最小值：，其時(shí)間是O（|E|log|V|＋|V|log|V|）

3、具有負(fù)邊值的圖

⑴、★算法思想和算法：

綜合了無權(quán)最短路徑（采用隊(duì)列）和Dijkstra算法（需要update）的思想Ⅰ、不需要再設(shè)置known來判斷結(jié)點(diǎn)是否已經(jīng)被訪問過

Ⅱ、掃描與v鄰接的所有結(jié)點(diǎn)w，分析是否有必要update其dist值，再分析w是否入隊(duì)⑵、★算法分析：時(shí)間是O（|E|×|V|）（給出詳細(xì)證明）

4、無環(huán)圖

⑴、★算法思想

以Dijkstra算法作為基礎(chǔ)，但是頂點(diǎn)的選取采用拓?fù)湓瓌t（而不是尋覓dist值最小的頂點(diǎn)）⑵、基本概念：動作結(jié)點(diǎn)圖和事件結(jié)點(diǎn)圖（注意：兩者的轉(zhuǎn)換方法）

⑶、基本概念：最早完成時(shí)間，最晚完成時(shí)間，松弛時(shí)間（分析其計(jì)算公式）⑷、基本概念：關(guān)鍵路徑－由零松弛邊組成的路徑

四、網(wǎng)絡(luò)流問題

1、概念：最大流問題

設(shè)有向圖G＝（V，E）的每條邊表示邊容量，求從給定的源點(diǎn)s到匯點(diǎn)t可通過的最大流量2、算法思想

⑴、輔助工具：流圖（初始：每條邊均為0）和剩余圖（初始：等于原圖）⑵、從剩余圖中選擇一條增長路徑（關(guān)鍵：對流圖和剩余圖進(jìn)行調(diào)整）⑶、算法一直運(yùn)行到?jīng)]有增長路徑為止

五、最小生成樹1、基本概念和性質(zhì)

⑴、生成樹的概念和性質(zhì)

概念：SpanningtreeisatreeformedfromgraphedgesthatconnectsallverticesofG.性質(zhì)：生成樹的邊數(shù)為N－1⑵、最小生成樹的概念和性質(zhì)

MST性質(zhì)：若（u，v）是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊（u，v）的最小生成樹

2、Prim算法

⑴、★Prim算法的基本思想：設(shè)G=（V，E），TE是G上最小生成樹的邊的集合Ⅰ、初始：U={u0}，TE={}

Ⅱ、從所有的（u，v）中尋覓一條代價(jià)最小的邊（u0，v0），其中u0∈U，v0∈V－UⅢ、U=U∪{u0}，TE=TE∪（u0，v0）Ⅳ、上述操作一直做到U=V為止⑵、★★Prim算法

Ⅰ、同Dijkstra算法十分類似，唯一區(qū)別在于dv的含義和更新方法不同（這里dv是指從v到所有known頂點(diǎn)的最短邊）

Ⅱ、注意：如何獲取最終的最小生成樹和計(jì)算出其代價(jià)

3、Kruskal算法

⑴、★★Kruskal算法的基本思想和算法Ⅰ、使用優(yōu)先隊(duì)列來存放所有的邊

Ⅱ、利用等價(jià)類的思想來決定（u，v）邊是應(yīng)當(dāng)添加還是舍棄

⑵、Kruskal的算法分析：同Prim算法一樣，其時(shí)間繁雜度為（|E|log|V|）

六、深度優(yōu)先探尋的應(yīng)用

1、深度優(yōu)先探尋（DFS，Depth-firstsearch）（DFS是對前序遍歷的推廣）⑴、★DFS算法思想和算法

尋常狀況下，DFS算法均由兩個(gè)模板構(gòu)成

Ⅰ、外圍模板：針對整個(gè)圖G進(jìn)行（初始化，再掃描結(jié)點(diǎn)，若unvisited則調(diào)用核心模板）Ⅱ、核心模板：是一個(gè)從指定頂點(diǎn)開始的，十分簡練的DFS遞歸程序⑵、DFS算法分析：時(shí)間繁雜度為O（|E|+|V|）

2、無向圖

⑴、★概念：前序編號（對圖G進(jìn)行DFS，圖中的各個(gè)頂點(diǎn)被依次訪問的順序編號）⑵、★概念：DFS樹（深度優(yōu)先生成樹）

對圖G進(jìn)行DFS以后，圖中的所有邊被分成兩大類：前向邊和后向邊其中所有的前向邊構(gòu)成了DFS樹

⑶、算法思想和算法（分析以上概念的算法實(shí)現(xiàn)）

3、無向圖的雙連通性

⑴、概念：雙連通性和割點(diǎn)

⑵、★low（v）的概念和計(jì)算方法

Low（v）是頂點(diǎn)v可到達(dá)的最低頂點(diǎn)編號（關(guān)鍵：計(jì)算low的三條法則）⑶、割點(diǎn)的判斷條件

若頂點(diǎn)v存在一個(gè)孩子結(jié)點(diǎn)w，有l(wèi)ow（w）>=num（v），則v必然是一個(gè)割點(diǎn)⑷、★算法：尋覓連通圖中的所有割點(diǎn)

該算法通過對圖的兩次遍歷而實(shí)現(xiàn)（一次前序遍歷和一次后序遍歷）Ⅰ、結(jié)點(diǎn)Vertex包含以下域：visited，num，low，parent

Ⅱ、首先計(jì)算圖G的每個(gè)頂點(diǎn)的前序編號（計(jì)算出num和parent）Ⅲ、利用一趟后序遍歷對各個(gè)頂點(diǎn)計(jì)算low，并判斷是否割點(diǎn)

4、歐拉回路

⑴、概念：歐拉環(huán)游和歐拉回路

⑵、歐拉定理：任何一個(gè)連通圖存在歐拉回路的充分必要條件是圖中所有頂點(diǎn)的度為偶數(shù)⑶、★歐拉回路的算法思想

Ⅰ、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：遍歷的路徑采用鏈表保存；

為避免重復(fù)掃描鄰接表，對每一個(gè)鄰接表必需保存最終掃描到的邊

Ⅱ、對給定的頂點(diǎn)進(jìn)行一次DFS

Ⅲ、選定一個(gè)拼接點(diǎn)，從該頂點(diǎn)開始進(jìn)行DFSⅣ、上述步驟重復(fù)進(jìn)行，直到所有的邊都被遍歷

⑷、歐拉回路的算法和算法分析：時(shí)間繁雜度為O（|E|+|V|）

5、有向圖

⑴、依照與無向圖一致的策略，對有向圖進(jìn)行DFS（若圖G非強(qiáng)連通的，則產(chǎn)生DFS森林）

⑵、有向圖DFS的虛邊有三種類型（無向圖只有一種，即后向邊）后向邊、前向邊和交織邊

⑶、對有向圖進(jìn)行DFS的一個(gè)作用是：判斷該有向圖是否無環(huán)圖法則如下：一個(gè)有向圖是無環(huán)圖當(dāng)且僅當(dāng)它沒有后向邊

6、查找強(qiáng)分支

⑴、★查找強(qiáng)分支的算法思想：兩次DFS

Ⅰ、首先對圖G進(jìn)行第一次DFS，得到DFS森林

（通過對DFS的后序遍歷得到每個(gè)頂點(diǎn)的后序編號；并且將G的所有邊反向得到GR）Ⅱ、再對GR進(jìn)行其次次DFS，總是在編號最高的頂點(diǎn)開始一次新的深度優(yōu)先探尋⑵、★定理：依照上述算法生成的DFS森林中的每棵樹都是一個(gè)強(qiáng)連通的分支（分析其證明）

七、NP完全性介紹1、P問題

指保證以多項(xiàng)式時(shí)間運(yùn)行的算法2、不可判定問題

⑴、可以證明：計(jì)算機(jī)不可能解決所有的問題，這些不可能解出的問題稱為不可判定問題⑵、著名的不可判定問題：停機(jī)問題Ⅰ、什么是停機(jī)問題？

Ⅱ、停機(jī)問題的實(shí)質(zhì)是：一個(gè)程序很難檢查它自己

3、NP類

⑴、NP類代表非確定型多項(xiàng)式時(shí)間這類問題在難度上稍遜于不可判定問題⑵、判斷一個(gè)問題是否NP問題的方法

假使我們能在多項(xiàng)式時(shí)間內(nèi)證明一個(gè)問題的任意“是〞的實(shí)例是正確的，那么這個(gè)問題就屬于NP類

典例：哈密爾頓回路問題就是一個(gè)NP問題⑶、NP類同其它集合的關(guān)系

Ⅰ、性質(zhì)：NP類包括P類，即包括所有具有多項(xiàng)式時(shí)間解的問題

Ⅱ、性質(zhì)：不是所有的可判定問題都是NP問題（即NP問題并不是不可判定問題的補(bǔ)集）典例：無哈密爾頓回路問題顯然是一個(gè)可判定問題，但不是NP問題

4、NP完全問題

⑴、NP完全問題是NP問題的一個(gè)子集

⑵、重要性質(zhì)：NP中的任何一個(gè)問題都可以多項(xiàng)式地歸約成NP完全問題⑶、證明一個(gè)問題是NP完全問題的方法Ⅰ、首先證明該問題是NP問題

Ⅱ、然后將一個(gè)適當(dāng)?shù)腘P問題變換到此問題

典例：假設(shè)哈密爾頓回路問題是一個(gè)NP完全問題，證明旅行商問題也是一個(gè)NP完全問題

第十章算法設(shè)計(jì)技巧

一、貪心算法

1、★貪心算法（greedalgorithm）

⑴、Solvetheprobleminstages（分階段進(jìn)行）⑵、每個(gè)階段都把出現(xiàn)的方案當(dāng)成最優(yōu)的解決方案（當(dāng)算法終止時(shí)，希望局部最優(yōu)成為全局最優(yōu)）

2、調(diào)度問題

⑴、★調(diào)度問題的概念：將作業(yè)平均完成的時(shí)間最小化

（假設(shè)：非搶占調(diào)度，即一旦開始一個(gè)作業(yè)，就必需把該作業(yè)運(yùn)行完）⑵、多處理器情形Ⅰ、實(shí)現(xiàn)步驟：（首先排序，然后按順序開始作業(yè)，處理器之間輪番分派作業(yè)）Ⅱ、證明：依照這種算法思想實(shí)現(xiàn)的，一定是最優(yōu)解⑶、將最終完成時(shí)間最小化（這是一個(gè)NP完全問題）

3、赫夫曼（Huffman）編碼⑴、概念：滿樹和前綴碼

⑵、赫夫曼編碼的算法思想（頻率出現(xiàn)高的字符編碼要短）⑶、★赫夫曼編碼的算法和算法分析

（采用優(yōu)先隊(duì)列時(shí)，運(yùn)行時(shí)間為O（ClogC））

4、裝箱問題⑴、基本概念

Ⅰ、★概念：裝箱問題（將物品裝到最少數(shù)量的箱子中）

Ⅱ、★概念：聯(lián)機(jī)裝箱（每一件物品必需放入一個(gè)箱子之后才能處理下一個(gè)物品）⑵、聯(lián)機(jī)算法

Ⅰ、重要性質(zhì)：對于聯(lián)機(jī)裝箱問題不存在最優(yōu)算法（分析其證明）Ⅱ、★定理一：任意聯(lián)機(jī)裝箱算法的下界為4M/3（分析其證明）⑶、下項(xiàng)適配

Ⅰ、下項(xiàng)適配的基本思想（能放入當(dāng)前箱子則放，否則開拓一個(gè)新的箱子）Ⅱ、★定理二：下項(xiàng)適配算法的上界為2M（分析其證明）⑷、首次適配

Ⅰ、首次適配的基本思想（掃描并尋覓第一個(gè)能放入的箱子，否則開拓一個(gè)新箱子）Ⅱ、定理三：首次適配算法的上界為17M/10⑸、最正確適配

最正確適配的基本思想和上界分析（放入所有能夠容納它的最滿的箱子中）⑹、脫機(jī)裝箱

Ⅰ、★首次適配遞減的算法思想（首先排序，然后再使用首次適配算法）Ⅱ、引理一：大小至多是1/3（分析其證明）

Ⅲ、引理二、個(gè)數(shù)至多是M-1（放入其它箱子中的物品個(gè)數(shù)至多是M-1，分析其證明）Ⅳ、★定理四、首次適配遞減算法的上界是（4M+1）/3Ⅴ、定理五、首次適配遞減算法的上界可以縮減為11M/9+4

二、分治算法

1、分治算法（divideandconquer）

⑴、★分治算法的基本思想：分治算法由兩個(gè)階段構(gòu)成Ⅰ、分：遞歸解決較小的問題

Ⅱ、治：從子問題的解構(gòu)建原問題的解

⑵、分治算法的特性（至少含有兩個(gè)遞歸調(diào)用，且子問題是不相交的）

2、分治算法的運(yùn)行時(shí)間

K

⑴、★定理六：方程T（N）=aT（N/b）+O（N）的解（分析其證明）

KP

⑵、定理七：方程T（N）=aT（N/b）+O（NlogN）的解（定理六的推廣）⑶、定理八：若∑αi<1，T（N）=∑T（αiN）+O（N）的解為T（N）=O（N）

3、最近點(diǎn)問題

⑴、★概念：最近點(diǎn)問題（對于平面上的點(diǎn)列P，找出一對最近的點(diǎn)）⑵、關(guān)鍵性質(zhì)：在2δ×2δ區(qū)域上，考察點(diǎn)必為常數(shù)情形⑶、最近點(diǎn)算法的基本思想

4、選擇問題

⑴、★概念：選擇問題（從含有N個(gè)元素的集合S中尋覓第K個(gè)最小的元素）⑵、概念：五分化中項(xiàng)的中項(xiàng)（分析其作用）

⑶、定理：使用“五分化中項(xiàng)的中項(xiàng)〞的快速選擇算法的運(yùn)行時(shí)間為O（N）

5、一些算術(shù)問題的理論改進(jìn)⑴、整數(shù)相乘

Ⅰ、概念：實(shí)現(xiàn)兩個(gè)N位數(shù)X和Y相乘

Ⅱ、★基本思想：分治算法（將X和Y拆分為兩半：將遞歸調(diào)用次數(shù)從4降為3）⑵、矩陣相乘（同上分析）

三、動態(tài)規(guī)劃

1、動態(tài)規(guī)劃的基礎(chǔ)知識

⑴、★重要性質(zhì)：所有數(shù)學(xué)遞推公式都可以直接翻譯成遞歸算法⑵、★動態(tài)規(guī)劃的概念和作用

Ⅰ、概念：動態(tài)規(guī)劃是解遞歸的一種技術(shù)（關(guān)鍵：將中間的計(jì)算結(jié)果保存下來）Ⅱ、作用：避免直接翻譯引起的低效（關(guān)鍵