算法分析与设计算法汇总

《算法分析与设计算法汇总》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分治法的治本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解合并得到原问题的解。快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交挽到后而单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。最坏时间复杂度：0(n2)平均时间复杂度：O(nlogn)voidQuicksort(Typea[],intp,intr){if(p

2、;//对左半段排序Quicksort(a,q+1,r);//对右半段排序}}intPartition(TypeaQ,intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交挽到右边区域while(true){while(a[++i]x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[)]；a[j]=x;returnj;}动态规划的基本思想将待求问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。与分治法不同的是解，经

3、分解得到的解往往不是互相独立的。动态规划的步骤：⑴找出最优解的性质，并刻划其结构特征。(2)递归地定义最优値。(3)以自底向上的方式计算fli最优值。(4)根据计算最优伉时得到的信息，构造最优解。矩阵连乘计算时间上界为0(n3)voidMatrixChain(int*p,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i]D】=m[i+1]D]+p[i-1]*p[i]*p[j];s[i]0]=i;f

4、or(intk=i+1;k

5、+1;b[i][j]=elseif(c[i-1][j]>=c[i]0-1]){c[i]0]=c[i-1]0]；b[i]0]=“T”;}else{c[i]0]=c[i]D-1];b[i][j]=}}voidLCS(inti,intj,char*x,int**b){if(i==0

6、

7、j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout«x[i];}elseif(b[i]0]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);贪心算法基本思想贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整

8、体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题O(n)先将活动按照结束时间升序排列voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=t「ue;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f01){A[i]=true;j=i;}elseA[i]=false;}}最优装载O(nlogn)最优装载问题

9、

10、J•用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。voidLoading(intx[]，Typew[]，Typec,intn)

11、{int*t=newint[n+1]；Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1；c-=w[t[i]];}}回溯法的基本思想：1、确定问题的解空间2、找出适当的剪枝函数3、以深度优先的方式搜索解空间装载问题O(2n)voidbacktrack(inti){II搜索第i层结点if(i>n)//到达叶结点更新最优解bestx,bestw;return;r-=w[i];if(cw+w[i]<=c)//搜索左子树{x[i]=1;cw+=w[i];back

12、track