算法的一些改进

算法对效率和低储存量有要求

1.当线性表中各结点的查找概率不相等时，则可用如下策略提高顺序查找的性能：若找到指定结点，则将该结点和其前驱交换（若存在），使得经常被查找的结点尽量位于表的前端。【也可以给每个结点设置一个访问频度域，每次查找成功时，将对应结点访问频度域加1，并按访问频度域调整链表中结点的位置。】

对线性表的顺序存储结构

int seqsrch(R,k)

Rectype R[];

Krytype k;

{int i,t;

i=0;

While((R[i].key!=k)&&(i{i++;}

if(i{t=R[i];R[i]=R[i-1];R[i-1]=t;

i--;

return(i);}

else return False;

}

对线性表的链式存储结构

Linklist linksrch(head,k)

Linklist *head;

Keytpe k;

{linklist *p,*q;

int temp;p=head;

q=head->next;

While((q!=null)&&(q->data!=k)

{p=q;q=q->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;

Else{p->freq++;break;}

While(q)

{if(q->freq>p->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;

q->prior=p;}

return ok;

}

2.当有序表的各记录查找概率不相等时，用折半查找的判定树其查找性能不是最优，这时需要构造一颗静态最优查找树，但构造静态最优查找树花费的时间代价较高，这时可构造一颗次优查找树。

构造静态最优查找树(代码是网上找的）

#include

#include

#include

#define N 4

void OBST(int P[], int Q[], int R[][N+1], int n)

{

//采用动态规划法构造最佳二分树

int W[N+1][N+1];//W[i,j]=sum(i,j,q)+sum(i+1,j,p);

int C[N+1][N+1];

for(int i=0; i<=N; i++)

{

for(int j=0; j<=N; j++)

{ W[i][j]=C[i][j]=R[i][j]=0;

}

}

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

{

W[i][i] = Q[i];

R[i][i] = 0;

C[i][i] = 0;

W[i][i+1] = Q[i]+Q[i+1]+P[i+1];

R[i][i+1] = i+1;

C[i][i+1] = Q[i]+Q[i+1]+P[i+1];

}

W[n][n] = Q[n];

R[n][n] = 0;

C[n][n] = 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个内节点的树的最后一个叶子节点下标W[i][j] = W[i][j-1]+P[j]+Q[j];//i是含m个内节点的树的第一个叶子节点的下标int k = i+1; // k是本次计算的第一个内点的下标值，以下标是k的内节点为根的最佳二分树的权值和最小，找使得C[i][k-1]+C[k][j]最小的k,且iint min = C[i][k-1]+C[k][j];

for(int L=i+2; L<=j; L++)

{

int temp = C[i][L-1]+C[L][j];/

if(temp{ min = temp; k = L;

}

C[i][j] = W[i][j]+C[i][k-1]+C[k][j];

R[i][j] = k;}

}

Printf（“最佳查找树举例: \\n\");

printf(\"输出W,C,R的表格: \\n\");

printf(\"%7s%-11s%-11s%-11s%-11s%-11s\

for(i=0; i<=N; i++)

{

printf(\"\\n%-3d\

for(int j=0; j<=N; j++)

{ printf(\" %-3d%-3d%-3d \j], C[i][j], R[i][j]);

}

}

}

void getTree(int tree[], int num, int R[][5], int i, int j)

{ if(!R[i][j]) return;

tree[num] = R[i][j];

getTree(tree, num*2, R, i, R[i][j]-1);

getTree(tree, num*2+1, R, R[i][j], j);

}

int main()

{

int P[N+1]={0, 1, 3, 2, 2};

int Q[N+1]={2, 1, 3, 1, 1};

int R[N+1][N+1];

OBST(P, Q, R, N);

int num=(int)pow((double)2, (double)N)；

int* tree=new int[num];

for(int i=0; i// 将树清空getTree(tree, 1, R, 0, N);

// 由R[i][j]获取最优二叉检索树

// 按照树的编码方式存入数组tree[]中

printf(\"\\n\\n输出如下:\\n\");

for(i=1; i{ // 输出在数组中存储的树的结点

printf(\"%2d(%d)\\

if(i%5==0) printf(\"\\n\");

}

getchar();

return 0;

}

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样

的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

2.无后效性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

3.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

3.分析冒泡排序在不同情况下的时间复杂度，并针对相应的情况给出可行的改进方案。

当记录为正序时，只需要进行一次排序，，进行n-1次关键字的比较，时间性能为O（n);

当记录为逆序时，采用每一趟都有“最小”石头沉到水底的方法，时间性能为O（n);

当记录的关键字值分布比较随机时，改进为快速排序，平均时间复杂度为O（nlgn)；

4.快速排序的时间性能改进

当记录的关键字值有序或基本有序，通常用三者取中的法则来选取枢轴记录，即比较L.r[s].key,L.r[t}.key,和L.r[(s+t)/2].key,取三者中关键字终值的记录为枢轴，可改善快速排序的时间性能。

为进一步改善快速排序的时间性能，可修改一次划分算法：在指针high减1和low增1的同时进行“起泡”操作，即在相邻两个记录处于“逆序”时进行互换，同时在算法中附设两个布尔型变量分别指示指针low和high在从两端向中间的移动过程中是否进行过交换记录的操作，若指针low在低端向像中间的移动过程中没有进行交换记录的操作，则不再需要对低端子表进行排序；类似的，若指针high在从高端像中间的移动过程没有进行交换的记录，则不再需要对高端子表进行排序，如此划分，可进一步改善快速排序的品均时间性能。