算法分析与设计总结.docx

1、算法（algorithm)就是定义良好的计算过程，取一个或一组值作为输入，并产生一个或一组输出。也就是，算法是一系列的计算步骤，用来将输入数据转换成输出结果。2、插入排序的基本思想：将待排序表看作是左右两部分；其中左边为有序区，右边为无序区；整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。伪代码如下：voidinsert_sort(elementtype A[n+1]){ for (i=2; i=n; i++) // i表示待插入元素的下标 { temp=A[i]; // 临时保存待插入元素，以腾出A［i］的空间 j=i-1; //j指示当前空位置的前一个元素 while (j=1 A[j].keytemp.key ) //有哪些信誉好的足球投注网站插入位置并腾空位{ A[j+1] =A[j]; j=j-1; } A[j+1]=temp; //插入元素 } }3、分治法在每一层递归上都有3个步骤：分解（Devide)：将原问题分解成一系列子问题；求解（Conquer) : 递归地求解各子问题，若子问题“足够小”（递归出口），则直接求解。合并（combine) ：合并子问题的解，以求解原问题的解。归并排序（merge sort）的操作：分解：分解数组为两个n/2规模的数组；求解：对两个子序列分别采用归并排序进行求解；合并：合并两个已排序子序列，得到排序结果。为了合并，引入一个函数Merge(A,p,q,r), 其功能是：合并已排序子序列A[p..q]和A[q+1..r]，得到已排序子序列A[p..r]。merge(A,p,q,r){ len1= q-p+1; len2=r-q;for(i=1; i=len1; i++) L[i]=A[p+i-1]; //复制到另外的数组中for(i=1; i=len2; i++) R[i]=A[q+i];i1=1; i2=1; L[len1+1]=∞; R[len2+1]=∞;//设置监视哨(先排完的数组先到无穷大)for (k=p; k=r; k++){ if (L[i1]=R[i2]){ A[k]=L[i1]; i1++;}else { A[k]=L[i2]; i2++;}}}时间性能：分解：不费时间，求解：2T（n/2），合并：O(n)2T（n/2）+ O(n) =整个排序：O(nlogn)4、递归式代换法求解的两个步骤：（1）猜测解的形式（2）用数学归纳法找出使得解真正有效的常数。递归树方法主方法给出求解如下形式的递归式方法：T(n)=aT(n/b)+f(n)，其中，a=1, b1是常数，f(n)是渐近正的函数。描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b。每个子问题的求解时间为T(n/b)，划分和合并的时间为f(n).5、堆排序：每一结点均不大于(或不小于）其左、右孩子结点的值。若序列(a1,a2,…,an)是堆，则堆顶(完全二叉树的根)必为序列中的最小或最大值。将根最大的堆称为大根堆，根最小的堆称为小根堆。（1）如果初始序列是堆，则可通过反复执行如下操作而最终得到一个有序序列：筛选过程即输出根：即将根（第一个元素）与当前子序列中的最后一个元素交换。（2）调整堆：将输出根之后的子序列调整为堆。如果初始序列不是堆，则首先要将其先建成堆，然后再按（1）的方式来实现。void sift(elementtype A[ ], intk,int m) //大根堆的堆排序//对数组中下标为1～n中的元素中的序号不大于m的以k为根的子序列调整{ finished=FALSE；i=k; j=2*k; //i指示空位，j先指向左孩子结点while (j=m !finished ) { if (jm A[j].keyA[j+1].key) j=j+1; //让j指向左右孩子中的最大者if (A[i].key=A[j].key) finished=TRUE; //根最大else { temp=A[i]; A[i]=A[j]; A[j]=temp;//大的孩子结点值上移i=j; j=2*j; } //继续往下筛选 } } //算法时间复杂度O(nlog2n)voidheap_sort(elementtype A[ ],int n) { for (i=n/2; i=1, i--) sift(A,i,n); //建初始堆for (i=n; i=2; i--){ println(A[1]);//