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

《《算法設(shè)計(jì)與分析》第4章窮舉法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第4章窮舉法4.1窮舉法的設(shè)計(jì)思想4.2漸近表示法4.3算法分析2021/7/122成都學(xué)院計(jì)算機(jī)系主要知識(shí)點(diǎn)掌握好算法的評(píng)價(jià)標(biāo)準(zhǔn);了解影響程序運(yùn)行時(shí)間的因素;掌握算法的評(píng)價(jià)標(biāo)準(zhǔn):時(shí)間復(fù)雜度和空間復(fù)雜度的概念;掌握漸近時(shí)間復(fù)雜度的幾種表示方式;掌握常見(jiàn)時(shí)間復(fù)雜度漸近表示之間的關(guān)系.2021/7/123成都學(xué)院計(jì)算機(jī)系4.1窮舉法思想一、窮舉法定義是一種簡(jiǎn)單而直接地解決問(wèn)題的方法，常常直接基于問(wèn)題的描述。是最容易應(yīng)用的方法，其時(shí)間性能比較低。通常典型的指數(shù)時(shí)間算法一般都是通過(guò)窮舉法搜索而得到的。2

2、021/7/125成都學(xué)院計(jì)算機(jī)系二、設(shè)計(jì)思想采用的基本技術(shù)是掃描技術(shù)，即使用一定的策略將待求解問(wèn)題的所有元素依次處理一次，從而找到問(wèn)題的解。為了避免重復(fù)試探，在基本的數(shù)據(jù)結(jié)構(gòu)中采用遍歷來(lái)處理每一個(gè)元素。2021/7/126成都學(xué)院計(jì)算機(jī)系（1）集合的遍歷按照元素序號(hào)的順序依次處理每個(gè)元素。（2）線性表的遍歷元素序號(hào)，如數(shù)組是按元素的下標(biāo)來(lái)處理。（3）樹(shù)的遍歷先序、中序、后序2021/7/127成都學(xué)院計(jì)算機(jī)系三、采用窮舉法的原因理論上可以解決可計(jì)算領(lǐng)域的各種問(wèn)題。經(jīng)常用來(lái)解決一些較小規(guī)模的問(wèn)題

3、。對(duì)一些重要問(wèn)題（排序、查找、字符串匹配等）有一些實(shí)用價(jià)值，且不受問(wèn)題規(guī)模的限制?？勺鳛槟愁悊?wèn)題時(shí)間性能下限，進(jìn)行高效算法的比較。2021/7/128成都學(xué)院計(jì)算機(jī)系4.2查找問(wèn)題中的窮舉法順序查找思想：從表的一端向另一端逐個(gè)將元素與給定值進(jìn)行比較，若相等，查找成功，給出該元素的具體位置；若整個(gè)表檢測(cè)完仍未找到與給定值相等的元素，則查找失??！2021/7/129成都學(xué)院計(jì)算機(jī)系假設(shè)以n個(gè)數(shù)放入數(shù)組r[1]～r[n]中，查找值k的算法。intSeqsearch(intr[],intn,intk){

4、i=n;while(i>0&&r[i]!=k)i--;returni;}2021/7/1210成都學(xué)院計(jì)算機(jī)系其基本語(yǔ)句i>0和r[i]!=k，其執(zhí)行次數(shù)缺陷：每次都要判斷下標(biāo)i是否越界。2021/7/1211成都學(xué)院計(jì)算機(jī)系改進(jìn)方法：哨兵將k放入到r[0]中，每次將r[1]～r[n]中的值與r[0]進(jìn)行比較。intSeqsearch(intr[],intn,intk){i=n;r[0]=k;while(r[i]!=k)i--;returni;}2021/7/1212成都學(xué)院計(jì)算機(jī)系其基本語(yǔ)句i

5、>0和r[i]!=k，其執(zhí)行次數(shù)比較順序查找方法，減少了系數(shù)。2021/7/1213成都學(xué)院計(jì)算機(jī)系4.3排序問(wèn)題中的窮舉法一、選擇排序思想：開(kāi)始掃描整個(gè)序列，找到最小記錄和序列中的第一個(gè)記錄交換，再?gòu)牡诙€(gè)記錄掃描，找到最小記錄與第二個(gè)記錄交換，直到掃描第n-1個(gè)記錄與第n個(gè)記錄進(jìn)行交換，使得整個(gè)序列有序。2021/7/1214成都學(xué)院計(jì)算機(jī)系一般情況，第i趟排序從第i個(gè)記錄開(kāi)始掃描序列，在n-i+1(1≤i≤n)個(gè)記錄中找最小記錄，并與第i個(gè)記錄進(jìn)行交換。2021/7/1215成都學(xué)院計(jì)算機(jī)

6、系VoidSelectsort(intr[],intn){for(i=1;i<=n-1;i++){index=i;for(j=i+1;j<=n;j++)//找最小記錄if(r[j]r[index];}}2021/7/1216成都學(xué)院計(jì)算機(jī)系基本語(yǔ)句內(nèi)層循環(huán)中的r[j]

7、鄰記錄，如反序則交換，最終將最大記錄置于最后一個(gè)記錄位置，第二大記錄置于倒數(shù)第二個(gè)記錄位置，重復(fù)至整個(gè)序列有序。2021/7/1218成都學(xué)院計(jì)算機(jī)系VoidBubblesort(intr[],intn){for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++)//找最小記錄if(r[j]r[j+1];}2021/7/1219成都學(xué)院計(jì)算機(jī)系基本語(yǔ)句內(nèi)層循環(huán)中的r[j]

8、行完。思想有沒(méi)有改進(jìn)的辦法？有則寫(xiě)出算法。2021/7/1220成都學(xué)院計(jì)算機(jī)系4.5幾何問(wèn)題中的窮舉法最近對(duì)問(wèn)題要求找出一個(gè)包含n個(gè)點(diǎn)的集合中距離最近的兩個(gè)點(diǎn)。應(yīng)用實(shí)例：空中交通2021/7/1221成都學(xué)院計(jì)算機(jī)系前提假設(shè)1.二維空間中的點(diǎn)，并且點(diǎn)的坐標(biāo)形式(x,y)給出的。2.若Pi=(xi,yi),Pj=(xj,yj)，則其間距離d:最近對(duì)問(wèn)題的求解過(guò)程：分別計(jì)算每一對(duì)點(diǎn)之間的距離，然后找出距離最小的那一對(duì)，只考慮i