算法的一些改進(jìn)

1、對(duì)已學(xué)的知識(shí)中提高時(shí)間性能的思索算法對(duì)效率和低儲(chǔ)存量有要求當(dāng)線性表中各結(jié)點(diǎn)的查找概率不相等時(shí)，則可用如下策略提高順序查找的性能：若找到指 定結(jié)點(diǎn)，則將該結(jié)點(diǎn)和其前驅(qū)交換(若存在)，使得經(jīng)常被查找的結(jié)點(diǎn)盡量位于表的前端?！疽部梢越o每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)訪問(wèn)頻度域，每次查找成功時(shí)，將對(duì)應(yīng)結(jié)點(diǎn)訪問(wèn)頻度域加1， 并按訪問(wèn)頻度域調(diào)整鏈表中結(jié)點(diǎn)的位置?！繉?duì)線性表的順序存儲(chǔ)結(jié)構(gòu)int seqsrch(R,k)Rectype R;Krytype k;(int i,t;i=0;While(Ri.key!=k)&(in)(i+;if(inext;While(q!=null)&(q-data!=k)(p=q;q=q-ne

2、xt;If(q&p!=head)(temp=p-data;p-data=q-data;q-data=temp;q=p;return q;設(shè)置訪問(wèn)頻度域Locatenode(dulinklist &L,Elemtype e)(dulinklist *p,*q;While(p)(if(p-data!=e) p=p-next;Else(p-freq+;break;While(q)(if(q-freqp-freq)q=q-next;Else(p-prior-next=p-next;p-next-prior=p-prior;p-next=q;p-prior=q-prior;q-prior-next=p;

3、q-prior=p;return ok;當(dāng)有序表的各記錄查找概率不相等時(shí)，用折半查找的判定樹(shù)其查找性能不是最優(yōu)，這時(shí)需 要構(gòu)造一顆靜態(tài)最優(yōu)查找樹(shù)，但構(gòu)造靜態(tài)最優(yōu)查找樹(shù)花費(fèi)的時(shí)間代價(jià)較高，這時(shí)可構(gòu)造一 顆次優(yōu)查找樹(shù)。構(gòu)造靜態(tài)最優(yōu)查找樹(shù)(代碼是網(wǎng)上找的)#include #include #include #define N 4void OBST(int P, int Q, int RN+1, int n)/采用動(dòng)態(tài)規(guī)劃法構(gòu)造最佳二分樹(shù)int WN+1N+1;/Wi,j=sum(i,j,q)+sum(i+1,j,p);int CN+1N+1;for(int i=0; i=N; i+)for(int

4、 j=0; j=N; j+) Wij=Cij=Rij=0;for(i=0; i=n-1; i+)Wii = Qi;Rii = 0;Cii = 0;Wii+1 = Qi+Qi+1+Pi+1;Rii+1 = i+1;Cii+1 = Qi+Qi+1+Pi+1;Wnn = Qn;Rnn = 0;Cnn = 0;for(int m=2; m=n; m+)找有m個(gè)結(jié)點(diǎn)的最優(yōu)樹(shù)，m從個(gè)開(kāi)始，直到n個(gè)(也就是說(shuō)最佳二分樹(shù)構(gòu)造成了) for(int i=0; i=n-m; i+) /i是本次需要計(jì)算的含m個(gè)內(nèi)節(jié)點(diǎn)的樹(shù)個(gè)數(shù) int j = i+m;/j是含m 個(gè)內(nèi)節(jié)點(diǎn)的樹(shù)的最后一個(gè)葉子節(jié)點(diǎn)下標(biāo)Wij = Wij-

5、1+Pj+Qj;/i是含m個(gè)內(nèi)節(jié)點(diǎn)的樹(shù) 的第一個(gè)葉子節(jié)點(diǎn)的下標(biāo)int k = i+1; / k是本次計(jì)算的第一個(gè)內(nèi)點(diǎn)的下標(biāo)值，以下標(biāo)是k的 內(nèi)節(jié)點(diǎn)為根的最佳二分樹(shù)的權(quán)值和最小，找使得Cik-1+Ckj最小的k,且ik=jint min = Cik-1+Ckj;for(int L=i+2; L=j; L+) int temp = CiL-1+CLj;/if(tempmin) min = temp; k = L;Cij = Wij+Cik-1+Ckj;Rij = k;Printf(“最佳查找樹(shù)舉例:n);printfC輸出 W,C,R 的表格:n);printf(%7s%-11s%-11s%-11

6、s%-11s%-11s”, ”,”0”,”1”,”2”,”3”,”4,for(i=0; i=N; i+) printf(n%-3d”, i);for(int j=0; j=N; j+) printf( %-3d%-3d%-3d ,Wij, Cij, Rij);void getTree(int tree, int num, int R5, int i, int j) if(!Rij) return;treenum = Rij;getTree(tree, num*2, R, i, Rij-1);getTree(tree, num*2+1, R, Rij, j);int main()int PN+1

7、=0, 1, 3, 2, 2;int QN+1=2, 1, 3, 1, 1;int RN+1N+1;OBST(P, Q, R, N);int num=(int)pow(double)2, (double)N)；int* tree=new intnum;for(int i=0; inum; i+) treei = 0;/ 將樹(shù)清空 getTree(tree, 1, R, 0, N);/由Rij獲取最優(yōu)二叉檢索樹(shù)/按照樹(shù)的編碼方式存入數(shù)組tree中printf(nn 輸出如下:n);for(i=1; inum; i+) /輸出在數(shù)組中存儲(chǔ)的樹(shù)的結(jié)點(diǎn)printf(%2d(%d)t, i, treei

8、);if(i%5=0) printf(n);getchar();return 0;動(dòng)態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是 一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，所以它 的空間復(fù)雜度要大于其它的算法。選擇動(dòng)態(tài)規(guī)劃算法是因?yàn)閯?dòng)態(tài)規(guī)劃算法在空間上可以承 受，而搜索算法在時(shí)間上卻無(wú)法承受，所以我們舍空間而取時(shí)間。所以，能夠用動(dòng)態(tài)規(guī)劃解 決的問(wèn)題還有一個(gè)顯著特征：子問(wèn)題的重疊性。這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件， 但是如果該性質(zhì)無(wú)法滿足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在

9、這類(lèi)問(wèn)題中，可能會(huì)有許多可 行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類(lèi) 似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題 的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn) 題往往不是互相獨(dú)立的。若用分治法來(lái)解這類(lèi)問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子 問(wèn)題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已 求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已 解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中

10、。 這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。 任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并 不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化原理和無(wú)后效性。最優(yōu)化原理(最優(yōu)子結(jié)構(gòu)性質(zhì))最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性 質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最 優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問(wèn)題滿足最優(yōu)化原理又稱其 具有最優(yōu)子結(jié)構(gòu)性質(zhì)。無(wú)后效性將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階 段的狀態(tài)無(wú)法直接影響它未來(lái)的決

11、策，而只能通過(guò)當(dāng)前的這個(gè)狀態(tài)。換句話說(shuō)，每個(gè)狀態(tài)都 是過(guò)去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱為無(wú)后效性。子問(wèn)題的重疊性動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)時(shí)間復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式 時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí) 質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)， 所以它的空間復(fù)雜度要大于其它的算法。分析冒泡排序在不同情況下的時(shí)間復(fù)雜度，并針對(duì)相應(yīng)的情況給出可行的改進(jìn)方案。當(dāng)記錄為正序時(shí)，只需要進(jìn)行一次排序，進(jìn)行n-1次關(guān)鍵字的比較，時(shí)間性能為O（n）;當(dāng)記錄為逆序時(shí)，采用每一趟都有“最小”石頭沉到水底的方法，時(shí)間性能為O（n）;當(dāng)記錄的關(guān)鍵字值分布比較隨機(jī)時(shí)，改進(jìn)為快速排序，平均時(shí)間復(fù)雜度為O（nlgn）；快速排序的時(shí)間性能改進(jìn)當(dāng)記錄的關(guān)鍵字值有序或基本有序，通常用三者取中的法則來(lái)選取樞軸記錄，即比較 L.rs.key,L.rt.key和L.r（s+t）/2.key取三者中關(guān)鍵字終值的記錄為樞軸，可改善快速排序 的時(shí)間性能。為進(jìn)一步改善快速排序的時(shí)間性能，可修改一次劃分算法：在指針high減1和low增1的同 時(shí)進(jìn)行“起泡”操作，即在相鄰兩個(gè)記錄處于“