《算法設(shè)計(jì)與分析》第4章窮舉法概要課件

第4章 窮舉法成都學(xué)院計(jì)算機(jī)系窮舉法的設(shè)計(jì)思想漸近表示法算法分析22023/11/22成都學(xué)院計(jì)算機(jī)系主要知識點(diǎn)掌握好算法的評價(jià)標(biāo)準(zhǔn);了解影響程序運(yùn)行時(shí)間的因素;掌握算法的評價(jià)標(biāo)準(zhǔn):時(shí)間復(fù)雜度和空間復(fù)雜度的概念;掌握漸近時(shí)間復(fù)雜度的幾種表示方式;掌握常見時(shí)間復(fù)雜度漸近表示之間的關(guān)系.32023/11/22成都學(xué)院計(jì)算機(jī)系4.1

窮舉法思想成都學(xué)院計(jì)算機(jī)系一、窮舉法定義52023/11/22成都學(xué)院計(jì)算機(jī)系是一種簡單而直接地解決問題的方法，常常直接基于問題的描述。是最容易應(yīng)用的方法，其時(shí)間性能比較低。通常典型的指數(shù)時(shí)間算法一般都是通過窮舉法搜索而得到的。二、設(shè)計(jì)思想采用的基本技術(shù)是掃描技術(shù)，即使用一定的策略將待求解問題的所有元素依次處理一次，從而找到問題的解。為了避免重復(fù)試探，在基本的數(shù)據(jù)結(jié)構(gòu)中采用遍歷來處理每一個(gè)元素。62023/11/22成都學(xué)院計(jì)算機(jī)系集合的遍歷按照元素序號的順序依次處理每個(gè)元素。線性表的遍歷元素序號，如數(shù)組是按元素的下標(biāo)來處理。樹的遍歷先序、中序、后序72023/11/22成都學(xué)院計(jì)算機(jī)系三、采用窮舉法的原因理論上可以解決可計(jì)算領(lǐng)域的各種問題。經(jīng)常用來解決一些較小規(guī)模的問題。對一些重要問題（排序、查找、字符串匹配等）有一些實(shí)用價(jià)值，且不受問題規(guī)模的限制。可作為某類問題時(shí)間性能下限，進(jìn)行高效算法的比較。82023/11/22成都學(xué)院計(jì)算機(jī)系4.2

查找問題中的窮舉法92023/11/22成都學(xué)院計(jì)算機(jī)系順序查找思想：從表的一端向另一端逐個(gè)將元素與給定值進(jìn)行比較，若相等，查找成功，給出該元素的具體位置；若整個(gè)表檢測完仍未找到與給定值相等的元素，則查找失敗！假設(shè)以n個(gè)數(shù)放入數(shù)組r[1]～r[n]中，查找值k的算法。int

Seqsearch(int

r[],

int

n,

int

k){

i=n;while

(i>0

&&r[i]!=k)i--;return

i;}102023/11/22成都學(xué)院計(jì)算機(jī)系其基本語句

i>0和r[i]!=k，其執(zhí)行次數(shù)缺陷：每次都要判斷下標(biāo)i是否越界。112023/11/22成都學(xué)院計(jì)算機(jī)系改進(jìn)方法：哨兵122023/11/22成都學(xué)院計(jì)算機(jī)系將k放入到r[0]中，每次將r[1]～r[n]中的值與r[0]進(jìn)行比較。int

Seqsearch(int

r[],

int

n,

int

k){ i=n;

r[0]=k;while

(r[i]!=k)i--;return

i;}其基本語句

i>0和r[i]!=k，其執(zhí)行次數(shù)比較順序查找方法，減少了系數(shù)。132023/11/22成都學(xué)院計(jì)算機(jī)系4.3

排序問題中的窮舉法142023/11/22成都學(xué)院計(jì)算機(jī)系一、選擇排序思想：開始掃描整個(gè)序列，找到最小記錄和序列中的第一個(gè)記錄交換，再從第二個(gè)記錄掃描，找到最小記錄與第二個(gè)記錄交換，直到掃描第n-1個(gè)記錄與第n個(gè)記錄進(jìn)行交換，使得整個(gè)序列有序。一般情況，第i趟排序從第i個(gè)記錄開始掃描序列，在n-i+1(1≤i≤n)個(gè)記錄中找最小記錄，并與第i個(gè)記錄進(jìn)行交換。152023/11/22成都學(xué)院計(jì)算機(jī)系Void

Selectsort(int

r[],int

n){

for

(i=1;i<=n-1;i++){

index=i;for

(j=i+1;j<=n;j++)//找最小記錄if

(r[j]<r[index])

index=j;if

(index!=i)

r[j]

>r[index];}}162023/11/22成都學(xué)院計(jì)算機(jī)系基本語句 內(nèi)層循環(huán)中的r[j]<r[index]，其執(zhí)行次數(shù)為：選擇排序最多交換n-1次數(shù)據(jù)。172023/11/22成都學(xué)院計(jì)算機(jī)系二、冒泡排序一開始就掃描整個(gè)序列，在掃描的過程中兩兩比較相鄰記錄，如反序則交換，最終將最大記錄置于最后一個(gè)記錄位置，第二大記錄置于倒數(shù)第二個(gè)記錄位置，重復(fù)至整個(gè)序列有序。182023/11/22成都學(xué)院計(jì)算機(jī)系Void

Bubblesort(int

r[],int

n){

for

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

(j=1;j<=n-i;j++)//找最小記錄if

(r[j]<r[j+1])

r[j]

>r[j+1];}192023/11/22成都學(xué)院計(jì)算機(jī)系基本語句 內(nèi)層循環(huán)中的r[j]<r[j+1]，其執(zhí)行次數(shù)為：不足：如果整個(gè)序列已經(jīng)有序，還是要直接整個(gè)外循環(huán)執(zhí)行完。思想有沒有改進(jìn)的辦法？有則寫出算法。202023/11/22成都學(xué)院計(jì)算機(jī)系4.5

幾何問題中的窮舉法最近對問題要求找出一個(gè)包含n個(gè)點(diǎn)的集合中距離最近的兩個(gè)點(diǎn)。應(yīng)用實(shí)例：空中交通212023/11/22成都學(xué)院計(jì)算機(jī)系前提假設(shè)二維空間中的點(diǎn)，并且點(diǎn)的坐標(biāo)形式(x,y)給出的。若Pi=(xi,yi),Pj=(xj,yj)，則其間距離d:最近對問題的求解過程：分別計(jì)算每一對點(diǎn)之間的距離，然后找出距離最小的那一對，只考慮i<j的那些點(diǎn)對。222023/11/22成都學(xué)院計(jì)算機(jī)系int

closetpoint(int

n,int

x[],int

y[],int

&index1,int&index2){

mindist=+∞;for

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

(j=i+1;j<=n;j++){ d=(x[i]-x[j])*(x[i]-x[j])+

(y[i]-y[j])*(y[i]-y[j]);if

(d<mindist){mindist=d;index1=i;index2=j;}}return

mindist;}232023/11/22成都學(xué)院計(jì)算機(jī)系實(shí)驗(yàn)—串匹配題目：給定一個(gè)文本，在該文本中查找并定位任意給定字符串實(shí)驗(yàn)?zāi)康模豪斫獠⒄莆崭F舉法的設(shè)計(jì)思想；實(shí)驗(yàn)要求：實(shí)現(xiàn)BF算法及對其的改進(jìn)算法BM算法對BF、BM進(jìn)行時(shí)間復(fù)雜度的分析并編程驗(yàn)證。242023/11/22成都學(xué)院計(jì)算機(jī)系BM算法基本思想：假設(shè)將主串中自位置i起往左的一個(gè)子串與模式進(jìn)行從右到左的匹配過程中，若發(fā)現(xiàn)不匹配，則下次應(yīng)從主串的i+dist(si)位置開始重新進(jìn)行新一輪的匹配，其效果相當(dāng)于把模式和主串均右滑過一段距離dist(si),即跳過dist(si)個(gè)字符而無需進(jìn)行比較。252023/11/22成都學(xué)院計(jì)算機(jī)系假設(shè)字符表{a,b,c,……,z}，BM算法對給定的模式T=“t1t2…tm”,定義一個(gè)從字符到正整數(shù)的映射：dist:c

{1,2,…，m}

,c屬于字符表滑動(dòng)函數(shù)給出了正文中可能出現(xiàn)的任意字符在模式中的位置，定義如下：m-j

j=max{j|tj=c且1≤j≤m-1dist(c)=c 若c不出現(xiàn)在模式中或tm=c262023/11/22成都學(xué)院計(jì)算機(jī)系Int

BM(char

s[],char

t[],int

n,int

m){i=