搜索
计算机算法复习提纲题型：一、选择（2*8=16分）二、填空（2*10=20分）三、简答（3小题，共16分）四、程序填空（3小题，每空2分，共24分）五、综合题（3小题，共24分）范围:第一章1．算法的形式化表示算法是一个四元组（Q、I、Ω、f）Q是一个集合，表示计算的状态I是Q的一个子集，表示计算的输入Ω是Q的一个子集，表示计算的输出f是Q到它自身的一个映射，表示计算的规则2．算法设计的步骤计算机算法复习提纲3．算法时间复杂度的分类4．算法的性质5.算法与程序的区别程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。计算机算法复习提纲第二章1．贪心法的定义指的是从对问题的某一初始解出发,一步一步的攀登给定的目标,尽可能快地去逼近更好的解。当达到某一步,不能再攀登时,算法便终止。2．贪心法的特点、基本要素特点：贪心算法总是做出在当前看来是最好的选择,它并不是从总体最优上加以考虑他所作出的选择只是在某种意义上的局部最优选择。能够得到的解不一定是最优解。基本要素：贪心选择性质--指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。最优子结构性质--当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。3．单源最短路径、活动安排活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。计算机算法复习提纲下面给出解活动安排问题的贪心算法GreedySelector:由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212F[i]4567891011121314计算机算法复习提纲若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。单源最短路径问题：给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1、算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。基本思想:设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。计算机算法复习提纲输入带权有向图G=(V，E)，V={1，2，…，n}，顶点V1是源C[i][j]表示边(i,j)的权dist[i]表示从源到顶点v1的最短特殊路径长度prev[i]表示从源到顶点i的最短路径上i的前一个顶点。输入参数：n,v1,c[i][j]输出参数：dist[i],prev[i]算法描述：基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。S[i]—源点到i顶点的最短路径是否找到初始化：for(i=1;i=n;i++){s[i]=0;dist[i]=c[v1][i];}S[v1]=1,dist[v1]=0;每次从V-S中取出具有最短特殊路长度的顶点u，并将u添加到S中for(num=2;num=n;num++){从dist[2]到dist[n]选取一顶点u且满足s[u]=0,使dist[u]=min{dist[2],dist[3],…,dist[n]};s[u]=1;}Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中后，同时对数组dist作必要的修改。for(j=1;j=n;j++){if(s[j]==0&&c[u][j]maxint){newdist=dist[u]+c[u][j];if(newdistdist[j]){dist[j]=newdist;prev[j]=u;}}}整个过程执行n-1次计算机算法复习提纲2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要时间。这个循环需要执行n-1次，所以完成循环需要时间。算法的其余部分所需要时间不超过。第三章1．递归与分治的基本思想分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法解决一个问题可以分为“分”和“治”两个阶段，而且整个过程使用的是递归的思想。因此，通常都是利用递归方式进行描述。2．递归的优缺点分析优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。3．分治的基本步骤divide-and-conquer(P){if(|P|=n0)adhoc(P);//解决小规模的问题dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题for(i=1,i=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解计算机算法复习提纲}4．阶乘、二分搜索、快速排序二分搜索问题：给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。intBinarySearch(Typea[],intx,intl,intr){while(r=l){intm=(l+r)/2;if(x==a[m])returnm;if(xa[m])r=m-1;elsel=m+1;}return-1;}算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。快速排序问题：在快速排序中，记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。voidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}计算机算法复习提纲快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。templateclassTypeintRandomizedPartition{inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)快速排序算法分析：Partition(a,p,r)计算时间为O(r-p+1),即f(n)=n最好情况，每次q=(p+r)/2O(1)n=1T(n)=2T(n/2)+nn1解方程得：T(n)=n+nlog2n=O(nlog2n)最坏情况，每次q=p或q=rO(1)n=1T(n)=T(n-1)+nn1解方程得：T(n)=O(n2)计算机算法复习提纲第四章1．动态规划的基本思想、基本步骤基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。基本步骤：找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。2．投资问题、矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)举例：假设有四个矩阵A,B,C,D1050A4010B3040C530D思考：计算次序和数乘次数？16000,10500,36000,87500,34500矩阵连乘问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。},...,,{21nAA