[算法复习1.docx

重要概念关于算法与复杂度算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算 。算法是解决某类问题的一系列运算的集合，算法是指解决问题的一种方法或一种过程。程序是算法用程序设计语言的具体实现。算法重要特性是什么？确定性、可行性、输入、输出、有穷性（输入、输出、确定性、有限性）算法分析的目的是什么？分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。算法的时间复杂性指算法中 元数据 的执行次数。通常可以通过计算循环次数、基本操作频率、计算步。计算机的资源最重要的是时间和空间资源。因而，算法的复杂性有时间复杂度和空间复杂度之分。设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)=。分治算法的时间复杂性常常满足如下形式的递归方程：其中，g(n)表示将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间 。7、算法的时间复杂性与问题的什么因素相关？算法的时间复杂性与问题的规模相关，是问题大小n的函数。算法的渐进时间复杂性的含义？当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。最坏情况下的时间复杂性和平均时间复杂性有什么不同？最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn10、记号O表示（渐进上界）， 记号表示（渐进下界）， 记号表示（紧渐进界）记号O的定义正确的是O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) }；记号的定义正确的是 (g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) }；a) 以下关于渐进记号的性质是正确的有：（A）A.B.C.O(f(n))+O(g(n)) = O(min{f(n),g(n)})D. b)对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或或，并简述理由。（12分）(1) (2) (3) （1），（2），（3）c)用O、、表示函数f与g之间阶的关系f(n)= g(n)= ???答案： 阶的关系： f(n)=(g(n))算法与基本思想简单描述分治法的基本思想。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。贪心算法的基本思想？简述动态规划方法所运用的最优化原理。“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。简单描述回溯法基本思想。回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先有哪些信誉好的足球投注网站，解为叶子结点。有哪些信誉好的足球投注网站过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的有哪些信誉好的足球投注网站，退回到上层父结点，继续下一步深度优先有哪些信誉好的足球投注网站过程。在有哪些信誉好的足球投注网站过程中，逐步构造出状态空间树，即边有哪些信誉好的足球投注网站，边构造。prim算法的基本思想。思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。阐述归并排序的分治思路。讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。快速排序的基本思想是什么。快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中