算法导论笔记第一章

发布时间:2016-12-10 14:52:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"算法导论笔记第一章",主要涉及到算法导论笔记第一章方面的内容,对于算法导论笔记第一章感兴趣的同学可以参考一下。

首先从别人的博文中看到一个对算法的最为简单而又简洁的理解: 算法=输入+良好的计算过程+正确输出。 仔细想,就是这个样子的。 有时间,习惯了有问题就上网查找,而渐渐使大脑变的迟钝许多,遇到问题第一反应不是仔细想想而是想要去查查怎么回事,这不是个好的习惯。要改正。 下面是自己对习题的一些想法: 1.1-1:给出一个真实世界的例子,其中包含着下列的某种计算问题:排序,确定多矩阵相乘的最佳顺序,或者找出凸壳 排序:很多成绩都可以用到排序,这个自然很常见。 确定多矩阵相乘的最佳顺序:矩阵相乘这个在现实世界中除了做题的时候会遇到其他还真没有遇到什么,也希望广大博友看了可以给我个提示一起来想一下,关于做题的结合律 A*B*C=A*(B*C)用到了这个,而实际上,这跟没说一样,举证相乘的最终目的就是减少运算,为了减少运算量的例子就是矩阵本身的计算,在matlab中的矩阵运算应该是算做这个吧。 找出凸壳:给定平面上n个点,希望找出这些点的凸壳,即包含这些点的最小凸多边形。从直观上看,可以将每一个点看成由一块板上突起的一个钉子表示。因此,包围这些点的凸壳可以看成是一根包围了所有这些钉子的紧绷的橡皮绳。每一个令橡皮绳发生方向变化的钉子都是该凸壳的一个顶点。这些点的2n个子集中的任何一个都可能是凸壳的顶点。知道哪些是该凸壳的顶点还不够,还需要知道他们出现的顺序,因此,该凸壳的顶点构成有多重选择。 1.1-2除了运行速度以为,在真实世界问题背景中,还可以使用哪些效率指标。 空间复杂度,占用内纯大小; 1.1-3选择你原来见过的某种数据结构,讨论一下其长处和局限性。问起数据结构的第一个想到就是链表,下面将链表和数组做个对比: 链表:方便插入和删除,但是在查询的时候,不能直接索引需要遍历。 数组:方便直接索引,但是对于插入和删除的操作可能需要移动位置。 1.1-4上文中给出的最短路径问题和旅行商人问题有哪些相似之处?有哪些不同之处? 相似之处:这两个问题都是求最短的路径 不同之处:最短路径问题其实是给定了情景并且不需要遍历所有的点只需要得到一个点到另外一个点的最短路径就可以了,而旅行商人问题则需要遍历所有的点并求得最短的路程,问题的复杂度不一样。亦可以找到一个最短的路径,但是你无法找到一个选择一条送货车行驶距离最短的送货顺序。其实是一个NP完全问题。(其实这个想了很久,由于要遍历所有的点,得到一个整体最短的路径,实际上是肯定可以找到的,但是这个算法还没有得到,另外我的想法是,在这些点中,(有的点可以走多次)每两个点中肯定可以找到一个最短路径,有点像最有子结构的感觉,但是整体的如何找到一个最短路径,还是个NP完全问题) 1.1-5举出一个现实世界问题的例子,他只能用最佳的解决方案来解决。再举出另一个例子,在其中“近似”最优解决也足以解决问题。 1)有一个固定大小的纸箱子,怎样将不同大小的东西更多的放入纸箱中储藏;(背包问题)(贪心算法基本上找到的都是最有解决方案) 2)解一元二次方程的时候使用逼近法来获得在范围之内的解(无限逼近就是近似的值)。   1.2-1给出一个实际应用的例子,他在引用这一层次上要求有算法性的内容。讨论其中所设计的算法功能。 例如工厂流水线上的流水作业调度问题,就要用到流水作业调度算法,其目的就是为了提高工作效率,(当然,算法也要根据实际来变更。) 1.2-2假设我们要比较在同一台计算机上插入排序和合并排序的实现。对于规模为n的输入,插入排序要运行8n*n步,而合并排序需要运行64n*lgn步。当n取怎样的值时,插入排序的性能要优于合并排序? 实际上是计算8n^2=64nlgn的n的值,算法导论上是lgn,这里的lg是以2为底的而不是已10为底。 n=2时, 8n*n < 64n*lgn即8*2*2=32<64*2*1 n=2^6=64时8*64*64<64*64*6 大概得出n的范围为[2,64]都是的插入排序小于合并排序。 1.2-3对于一个运行时间为100n*n的算法,要使其在同一台机器上,在比一个运行时间为2^n的算法运行的很快,n的最小值是多少? 100n^2=2^n画图可以得到n应该有两个值,一个小于0舍去,另外一个为15 n>15的时候,(注:看的别人计算出来的,高数学的那些计算方法都忘记了。)   1-1思考题 计算方法是f(n)=t,就可以求解n的规模了,注意时间单位是毫秒级别的。

上一篇:小伙伴们的ceph源码分析三——monitor消息处理流程
下一篇:dll动态链接库(4)---MFC规则DLL

相关文章

相关评论