《算法的一些改进》由会员分享，可在线阅读，更多相关《算法的一些改进（5页珍藏版）》请在金锄头文库上搜索。
1、对已学的知识中提高时间性能的思索算法对效率和低储存量有要求1.当线性表中各结点的査找概率不相等时，则可用如下策略提高顺序査找的性能：若找到指 定结点，则将该结点和其前驱交换(若存在)，使得经常被査找的结点尽量位于表的前端。【也可以给每个结点设置一个访问频度域，每次查找成功时，将对应结点访问频度域加1, 并按访问频度域调整链表中结点的位置。】对线性表的顺序存储结构int seqsrch(R,k)Rectype R;Krytype k;int i,t;i=0;While(Ri.key!=k )&(ivn)i+；if(inext;While(q!=nu ll)&(q-data!=k)p=q;q=q-
2、next;If(q& p!=head)temp=p-data;p-data=q-data;q-data=temp;q=p;return q;设置访问频度域Locatenode(dulinklist & L,Elemtype e)dulinklist *p,*q;While(p)if (p-data!=e) p=p-next;Elsep-freq+;break;While(q)if(q-freqp-freq)q=q-next;Elsep-prior-next=p-next;p-next-prior=p-prior;p_next=q;p-prior=q-prior;q-prior-next=p;q
3、-prior=p;return ok;2当有序表的各记录査找概率不相等时，用折半査找的判定树其査找性能不是最优，这时需 要构造一颗静态最优査找树，但构造静态最优査找树花费的时间代价较高，这时可构造一 颗次优査找树。构造静态最优査找树(代码是网上找的)#include vstdio.h#include vstdlib.h#include #define N 4void OBST(int P, int Q, int RN+1, int n)采用动态规划法构造最佳二分树int WN+1N+1;/Wi,j=sum(i,j,q)+sum(i+1,j,p);int CN+1N+1;for(int i=0;
4、 i=N; i+)for(int 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个结点的最优树，m从个开始，直到n个(也就是说最佳二分树构造成了)for(int i=0; i=n-m; i+) /i是本次需要计算的含m个内节点的树个数 int j = i+m;/j是含m 个内节点的树的最后一个叶
5、子节点下标Wij = Wij-1+Pj+Qj;/i是含m个内节点的树 的第一个叶子节点的下标int k = i+1; / k是本次计算的第一个内点的下标值，以下标是k的 内节点为根的最佳二分树的权值和最小，找使得Cik-1+Ckj最小的k,且ivkv=jint min = Cik-1+Ckj;for(int L=i+2; L=j; L+)int temp = CiL-1+CLj;/if(tempvmin) min = temp; k = L;Cij = Wij+Cik-1+Ckj;Rij = k;Printf (“最佳查找树举例:n);printf(”输出 W,C,R 的表格:n);print
6、f(”7s%-11s%-11s%-11s%-11s%-11s, ，”0,1,2,3,4); for(i=0; iv=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
7、()int PN+1=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; ivnum; i+) treei = 0;/ 将树清空 getTree(tree, 1, R, 0, N);/由Rij获取最优二叉检索树/按照树的编码方式存入数组tree中printf(nn 输出如下:n);for(i=l; ivnum; i+) /输出在数组中存储的树的结点printf(”2d(%d
8、)t, i, treei); if(i%5=0) printf(n);getchar(); return 0;动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是 一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它 的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承 受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。所以，能够用动态规划解 决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件, 但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。动态规划算法通常用于求
9、解具有某种最优性质的问题。在这类问题中，可能会有许多可 行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类 似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题 的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问 题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子 问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已 求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已 解的子问题的答案。不管该子问题以后是否被用到，只要它
10、被计算过，就将其结果填入表中。 这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并 不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1最优化原理(最优子结构性质)最优化原理可这样阐述：一个最优化策略具有这样的性 质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最 优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其 具有最优子结构性质。2无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶
11、 段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都 是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式 时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实 质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态, 所以它的空间复杂度要大于其它的算法。3分析冒泡排序在不同情况下的时间复杂度，并针对相应的情况给出可行的改进方案。当记录为正序时，只需要进行一次排序,，进行n-1次关键字的比较，时间性能为0(n);当记录为逆序时，采
12、用每一趟都有“最小”石头沉到水底的方法，时间性能为0 (n);当记录的关键字值分布比较随机时，改进为快速排序，平均时间复杂度为0(nlgn)；4快速排序的时间性能改进当记录的关键字值有序或基本有序，通常用三者取中的法则来选取枢轴记录，即比较 L.rs.key,L.rt.key和L.r(s+t)/2.key取三者中关键字终值的记录为枢轴，可改善快速排序 的时间性能。为进一步改善快速排序的时间性能，可修改一次划分算法：在指针high减1和low增1的同 时进行“起泡”操作，即在相邻两个记录处于“逆序”时进行互换，同时在算法中附设两个 布尔型变量分别指示指针low和high在从两端向中间的移动过程中是否进行过交换记录的 操作，若指针low在低端向像中间的移动过程中没有进行交换记录的操作，则不再需要对低 端子表进行排序；类似的，若指针high在从高端像中间的移动过程没有进行交换的记录， 则不再需要对高端子表进行排序，如此划分，可进一步改善快速排序的品均时间性能。
