导读：1.一个算法就是一个有穷规则的集合，算法还应具有以下五个重要特性:确定性有穷性可行性0个或多个输入一个或多个输出，2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低，3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质，6.动态规划算法的基本思想是将待求解问题分解成若干子问题_，7.以深度优先方式系统搜索问题解的算法称为回溯法，8.0-1背包问 填空题： 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性
0个或多个输入
一个或多个输出 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干子问题_，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n),用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。
10.二分搜索算法是利用动态规划法实现的算法。 11.一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。 12.出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。 13.动态规划算法有一个变形方法
备忘录方法
。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。 14、这种不断回头寻找目标的方法称为回溯法。 15、直接或间接地调用自身的算法称为递归算法。 16、? 记号在算法复杂性的表示法中表示渐进确界或紧致界。 17、由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
18、建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。 19、下列各步骤的先后顺序是②③④①。①调试程序 ②分析问题 ③设计算法 ④编写程序。 20、最优子结构性质的含义是问题的最优解包含其子问题的最优解。 21、贪心算法从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择。 22、拉斯维加斯算法找到的解一定是正确的。 简答题：
1. 算法分析的目的是什么？ 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
2. 简述二分检索（折半查找）算法的基本过程。 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。上述过程被反复递归调用。 回溯法的搜索特点是什么
3. 回溯法的搜索特点是什么？
在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。
4. 为什么用分治法设计的算法一般有递归调用？ 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。
5. 贪心算法的基本思想？ 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
6. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。 21. 动态规划算法的主要步骤
22. 简单描述分治法的基本思想
23. 简单描述回溯法基本思想
24. 简单描述贪心算法的基本要素是什么？
算法理解： 1：快速排序算法 2：优先队列式分支限界法（画图） 3：矩阵连乘问题 ?m[1][1]?m[2][4]?p0p1p4?0??5?10500?m[1][4]?min?m[1][2]?m[3][4]?p0p2p4??50?40?5?36000?m[1][3]?m[4][4]?ppp??30?5?34500 034??105004：贪心算法活动安排问题（画图） 5：0-1背包问题，贪心算法、动态规划法、回溯法 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 6：贪心算法的哈夫曼编码问题 对于字符集合M={A,B,C,D,E,F}，设这些字符在文本中出现的频率分别为8,1,3,10,6,5， 画出字符集合M的Huffman编码树，并给出各字符的Huffman编码。 7：硬币找零问题，贪心算法
8：动态规划策略求解最长公共子序列问题 9：动态规划算法求解最大子段和问题 10：考虑n=3的批处理作业调度实例：
tji 作业1 作业2 作业3
其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。 要求： （1）画出该问题的解空间树；
（2）写出该问题的剪枝策略(即限界条件)，要求只保留第一个最优解；
（3）按优先队列式分支限界法搜索解空间树，并用剪枝策略对解空间树中该剪枝的位置打?；
（4）给出最优解及最优值。
机器1 1 3 2 机器2 10 1 1 （1） V0 1 11 2 23 3 36 3 23 2 36 3 33 1 18 1 2 4 3 10 1 2 16 2 3 3 1 9 2630 25
（2）若当前代价f >= 当前最优解代价bestf，则剪枝。 （3）见（1）中所画的图。 （4）最优解为{3，1，2}，最优值为25。
包含总结汇报、党团工作、工作范文、办公文档、IT计算机、专业文献、教程攻略、旅游景点、文档下载、资格考试以及算法分析复习题1等内容。
相关内容搜索拒绝访问 |
| 百度云加速
请打开cookies.
此网站 () 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(3d230db3fe2a437c-ua98).
重新安装浏览器，或使用别的浏览器后使用快捷导航没有帐号？
如何衡量一个算法的快慢
查看: 18602|
评论: 0|原作者: 南方小智|来自:
摘要: 当我们说衡量一个算法的快慢时，我们是希望找到一种方便的统一标准，使得对于同一个算法，我们的衡量标准不会受到一些不重要的因素影响而保持一致；对于不同的算法，我们能够比较它们的优劣并在实际的应用中进行选择 ...
本文是一篇时间复杂度的入门介绍。我将逐步引出为何要使用时间复杂度来衡量一个算法的快慢，并给出时间复杂度的表示符号，介绍了较好，最坏和平均时间复杂度。用具体的操作数来衡量当我们说衡量一个算法的快慢时，我们是希望找到一种方便的统一标准，使得对于同一个算法，我们的衡量标准不会受到一些不重要的因素影响而保持一致；对于不同的算法，我们能够比较它们的优劣并在实际的应用中进行选择。一个自然的想法是测量这个算法运行所需要的时间，然后选择跑得快的算法。但是不同的机器运行的速度是不一样的，一个同样的算法在不同机器上测出来的时间可能非常不同。而且，每次想要知道一个算法的快慢如果都要在机器上通过计时来测量的话，是一件非常痛苦的事情，因为有些算法可能一次要跑上一天，一个月，甚至一个世纪。一个有效的替代方法是通过计算一个算法用了多少次操作（或者说运算量）来衡量它运行的快慢，比如用了多少次加减法，乘除法，函数调用和赋值等操作。操作数越多，运行的所需要的时间就越多。这样的一种想法保证了我们对算法的衡量不会因为测试环境的变化而变化，也不用通过实际运行来测量，只需通过计算就能得到操作数的数量。用函数来衡量仅仅计算操作数的一个问题是：一个固定的算法，针对不同的输入规模，它所需要的操作数量是不一样的。比如一个排序的算法，排100个数字和排10000个数字相比，排10000个数字所需要的运算量会大很多。也就是，操作数是随输入规模变化的一个函数。所以，我们假如输入规模是n，那么操作数就是f(n)。有时候，输入规模不只有一个，比如关于一个矩阵的算法需要的操作数，可能和矩阵的长和宽都有关系，这时候，ff就变成了一个关于长和宽的二元函数，比如f(w,h)。这种扩展是合理的，但是为了讨论方便，我们先只考虑规模只是一个变量n的情况。f可能形式会比较复杂。比如那么三个函数到底谁才能代表这个算法的真正时间复杂度呢？为了满足统一的衡量标准，我们必须有一个选择方法。用近似函数来衡量为了解答这个问题，我们首先要认识到，在实践中，我们只关心算法在输入规模比较大的情况下的表现。因为现在的计算机每秒都能做上亿次运算，我们处理的实际问题也是规模比较大的。而当输入规模较大时，我们就可以通过只保留占较大比重的项，并忽略常数，来得到一个统一的近似函数表达式。对于上面的例子来说，近似函数就是：我们从直观上来理解这种近似是合理的。首先，当数据规模nn达到十万的时候，4n^2是40n的一万倍，所以我们已经没有必要考虑40n了，我们舍弃小项，而只保留占较大比重的项。对于忽略常数，是因为，当我们比较两个不同的时间复杂度的时候，常数是无关紧要的：考虑两个时间复杂度n^2和100n。100是比1大很多的，但是当n达到十万的时候n^2是100n的一千倍，可见常数的影响是非常小的。或者说，常数不会随输入规模n的变化而变化，当输入规模越来越大的时候，常数的影响力就越来越小。这种机智的取舍解决了很多细节问题，比如，不同的操作可能会耗时不同，就好像加法操作要快些，乘法要慢些，除法可能更慢，而内存的读写操作可能比逻辑操作更慢些。在一些要求非常精细的情况下，我们可能不得不仔细分开不同的操作，但是，在一般情况下，如果我们忽略常数造成的差异，我们可以把这些不同的操作看成是一个操作单元，也就是说，虽然乘法比加法慢了2倍，但2只是个常数，我们把这种差异忽略掉。近似函数是渐近的现在我们从另一个角度来理解这个近似函数。当nn不断增大时，如果f(n)和g(n)的比值趋向于稳定（稳定等于一个不等于0的常数），我们就认为f(n)和g(n)其实是渐近等价的。g其实是渐近等价的：由此可见，我们选取的【函数四】是和前面的三个函数在变化趋势上是渐近的。总的来说，我们找到了一个统一的标准，两个程序员的编码风格所造成的差别不存在了。表示符号目前，我们找到了操作数关于输入规模的一个近似函数来表示算法运行的快慢。这个近似函数就表示了算法的时间复杂度，通常我们会说某个算法的复杂度是O(f(n))或者Θ(f(n))。下面就说明不同的表示符号代表的含义：很多时候，我们都会使用OO符号，因为我们一般只会证明一个算法复杂度的上界（最坏情况），如果这个上界达到我们的要求了，就不必计算下界了。这里举一个例子，对于一个时间复杂度为n2的算法，我们可以说：最坏，较好和平均时间复杂度前面我们讨论了算法的操作数随输入规模变化，但是即使是相同规模的数据，也能造成操作数的差异。这个时候，如果我们对每种可能的输入都进行时间复杂度的计算的话，是非常麻烦且没有必要的。我们一般只考虑最坏，较好和平均情况下的时间复杂度：最坏时间复杂度：在所有可能的输入中，操作数最多的输入的时间复杂度。较好时间复杂度：在所有可能的输入中，操作数最少的输入的时间复杂度。最坏时间复杂度：对所有可能的输入的操作数取均值得到的时间复杂度。这种表示时间复杂度的方法也可以运用到空间复杂度的上，在这种复杂度的表示方法下，程序员们可以愉快地攀比谁的算法更优，而不需要考虑实际实现的差异和具体运行环境等细枝末节的东西。欢迎加入本站公开兴趣群高性能计算群兴趣范围包括：并行计算，GPU计算，CUDA，MPI，OpenMP等各种流行计算框架，超级计算机，超级计算在气象，军事，航空，汽车设计，科学探索，生物，医药等各个领域里的应用QQ群：
刚表态过的朋友 ()
上一篇：下一篇：
CopyRight 2011- All Right Reserved.相关文章推荐
简单排序算法时间空间复杂度分析及应用(5)-鸡尾酒排序(双冒泡排序)
顾名思义，鸡尾酒排序是属于冒泡排序的一种改进，从数据集合的两边进行冒泡排序，因此在排序过
程中确定数据区域会有两个，分别在数据集...
简单排序算法时间空间复杂度分析及应用-冒泡排序
冒泡排序算法，我上大学一开始接触的算法就是冒泡排序算法，这是算法入门知识，通过冒泡排序算法我接触了循环的概念，循环有开始节点和结束节点，并且算法会经历...
简单排序算法时间空间复杂度分析及应用(4)-二分插入排序
顾名思义，这个二分插入排序是直接插入排序的进化版，主要变化的地方就是在内循环部分，即外循环的循环节点在确定区域...
归并排序采用的是分治的思想，先把数据集和分成两个子数据集合进行归并排序，然后将已经排好序的两个子序列合并成一个有序的数据集合，归并排序是一个非常稳定的排序算法。
基本概念：
归并排序具体算法描...
简单排序算法时间空间复杂度分析及应用(3)-快速排序
和之前的两种算法比较：
1.快速算法适合在n值(排序规模比较大)较大的场景下使用，快速排序算法时间会少一点。
2.冒泡排序...
简单排序算法时间空间复杂度分析及应用（2）-插入排序
上一篇文章提到了一些新的概念，不言而喻，概念的功能对人类来说是一项伟大的发现，百度对“概念”的定义是这样的：概念具有两个基...
简单排序算法时间空间复杂度分析及应用(5)-堆排序
堆排序，属于选择排序的一种，两层嵌套循环，内循环结束后确定最大或最小的值，然后和外循环的节点交换值，待外循环结束后，整个数组排序完成。
他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)算法分析复习题答案(日)-工作总结范文网
全站搜索：
您现在的位置：&>&&>&工学
算法分析复习题答案(日)
一、选择题1、二分搜索算法是利用（
）实现的算法。A、分治策略
B、动态规划法
D、回溯法2、下列不是动态规划算法基本步骤的是（
）。A、找出最优解的性质
B、构造最优解
C、算出最优解
D、定义最优解3、衡量一个算法好坏的标准是（ D
）。A 运行速度快 B 占用空间少 C 时间复杂度低
B和C4．实现棋盘覆盖算法利用的算法是（
）。A、分治法
B、动态规划法
D、回溯法5.下面是贪心算法的基本要素的是（
）。A、重叠子问题
B、构造最优解
C、贪心选择性质
D、定义最优解6. （
）是贪心算法与动态规划算法的共同点。A、重叠子问题 B、构造最优解 C、贪心选择性质
D、最优子结构性质7. 矩阵连乘问题的算法可由（
）设计实现。A、分支界限算法
B、动态规划算法
C、贪心算法
D、回溯算法8、使用分治法求解不需要满足的条件是（A
）。A 子问题必须是一样的
B 子问题不能够重复C 子问题的解可以合并
D 原问题和子问题使用相同的方法解9．下列是动态规划算法基本要素的是（
）。A、定义最优解
B、构造最优解
C、算出最优解
D、子问题重叠性质10．下列算法中通常以自底向下的方式求解最优解的是（
）。A、分治法
B、动态规划法
D、回溯法11．贪心算法与动态规划算法的主要区别是（
）。A、最优子结构
B、贪心选择性质
C、构造最优解
D、定义最优解12. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（
）。A、重叠子问题
B、最优子结构性质
C、贪心选择性质 D、定义最优解二、 填空题1.算法的复杂性有
复杂性之分。2、程序是
用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条
是清晰的，无歧义的。4.矩阵连乘问题的算法可由
设计实现。1
5、算法是指解决问题的
。6、从分治法的一般设计模式可以看出，用它设计出的程序一般使用
机制 。7、计算一个算法时间复杂度通常可以计算
循环次数 、
基本操作的频率
或计算步。8、动态规划算法的基本思想是将待求解问题分解成若干
，然后从这些
的解得到原问题的解。9.算法是由若干条指令组成的有穷序列，且要满足输入、
、确定性和
四条性质。10.任何可用计算机求解的问题所需的时间都与其
有关。11. 写出下列f(n)的渐进性态：1) f(n)=C，为常数：f(n)=。
2) f(n)= 3n+2：f(n)=。3) f(n)= 6×2n+n：f(n)= n。
4) f(n)= nlog n：f(n)= 。12. 按照渐近阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3。又n!应该排在哪一位？2/3，20n，4n2，3n，n！。
三、时间复杂度分析（写出分析过程）1.汉诺塔问题的时间复杂度。解：汉诺塔问题的时间复杂性是完成ｎ个圆盘移动所移动的次数。设移动总次数为Ｔ(ｎ)，由于原问题分成了三个子问题：两个移动ｎ-1个圆盘的问题和一个移动一个圆盘的过程。两个移动ｎ-1个圆盘的问题采用递归调用，花时间Ｔ(ｎ-1)，移动一个圆盘花一个单位时间。所以的递归方程如下：n?1?1
T(n)???2T(n?1)?1n?1直接推导可得T(n)?2(2T(n?2)?1)?1?4T(n?2)?2?1???2n?1T(1)?2n?2?...?.1.?2n?1
2. 冒泡排序算法的基本运算如下：for i ←1 to n-1 dofor j ←1 to n-i doif a[j]&a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。解：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。2
1）设比较一次花时间12）内循环次数为：n-i次,（i=1,?n），花时间为：?1?(n?i)j?1n?in3）外循环次数为：n-1，花时间为：T(n)??(n?i)?(n?1) 2i?1n
3． 递归求取最大和最小元素算法 MAXMIN的时间复杂性。解：设算法的元素比较次数为T(n)，mid将数组分成大小为?n/2?和?n/2?的两部分，递归调用原过程分别在两部分找max1、min1和max2、min2，分别花时间为T(?n/2?)和T(?n/2?)，比较max1、max2和min1、min2找出max、min所花时间为2。因此递归方程为：?0?T(n)??1?T(n/2)?T(n/2)?2?????当n是2的幂时，即对于某个正整数k，n=2k，有?n/2?和?n/2?T(n)=2T(n/2)+2＝2(2T(n/4)+2)+2=4T(n/4)+4+2???2k?1T(2)?＝2k-1+2k-2＝3n/2-2
四、算法设计1.有9件产品，其中一个不合格，不合格的产品比合格产品轻，现有一个天平，请设计算法用最少比较次数找到不合格产品。答：本题使用分治法。算法设计步骤如下：（1）将9件产品分成3组，每组3件产品。（2）用天平称量其中任意两组，有两种情况：第一种情况是天平上其中一组重量轻，则重量轻的一组产品转步骤（3）；第二种情况是天平上的两组重量相等，则剩下的第三组转步骤（3）。（3）将步骤（2）转来这组的3件产品，分开成3组，每组一件产品，用天平称量其中任意两件产品，有两种情况： 第一种：天平中有一件产品轻，则这件产品为不合格产品，算法结束。第二种：天平中两件产品重量相等，则第三件产品为不合格产品，算法结束。使用这样的分治法，可以在两次称量后得出结论，用的比较次数最少。评分标准：设计出算法给5分，算法时间效率好给5分。 1?i?k?1?2
2.试用动态规划算法，解决5个矩阵连乘的问题。（ 用具体实例说明算法设计过程，不要求写具体的算法实现）
上一篇： 下一篇：
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。}