展开

关键词

系列:分治

说起分治,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无皇帝多远,山有多高,整个国家都属于朝廷统治,但皇帝一个人是管不了这么多事情的 秦始皇的郡县制其实就是分而治之的一种变种,我们现在的国家也是这样,国家分省,市,县,乡,这样层次管理,无在那个偏僻的角落,都不是无政府的.而我们的分治,其实是一种很古老的策略,里有句古话,”凡治众如治寡 ,分数是也”,这里的”分数”,是指分到各层次的部分,”数”是指每部分人的人数,意思就是将帅只需要通过管理少数几个人即可实现管理全部队的各个组织,这样,人数众多的军队,就如同管理几个人一样容易.在设计中 ,我们也引入分而治之的策略,称为分治,其本质其实就是将一个问题分解为若干个规模较小的相同子问题,分而治之.分治秘籍:分治解题的基本步骤如下:1:分解问题:将要解决的问题分解为若干个规模较小,相互独立 .一句话总结,分治就是将一个难以直接解决的大问题,分割成规模较小的相同子问题,以便各个击破,分而治之.在使用分治时,使用递归是解决问题的利器.下面我们用二分搜索,这个最典型的分治问题来举例,看看分治是如何进行工作的

24420

重读基础

重读基础----插入排序​ 对于少量数据的一种有效。 ----循环不变式​ 循环不变式主要用来帮助我们理解的正确性。 要证明一个是循环不变式,必须证明该满足三条性质:初始化:循环的第一次迭代之前,它为真保持:如果循环的某次迭代之前它为真,那么进行完当前迭代,下次迭代之前仍然为真终止:在循环终止时,不变式为我们提供了一个有用的性质 ,该性质有助于证明是正确的​ 循环不变式类似于数学上的归纳。 只不过在归纳中,归纳步是无限地使用的,而这里存在循环终止,停止归纳。----用循环不变式验证插入排序初始化: 从上面的代码可以看到。

482100
  • 广告
    关闭

    50+款云产品免费体验

    提供包括云服务器,云数据库在内的50+款云计算产品。打造一站式的云产品试用服务,助力开发者和企业零门槛上云。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    系列:贪心(2)

    这篇文章我们将来一起看看贪心一个具体例子, DijkstraDijkstra最著名的应用是解决单元最短路径,这是一类贪心,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径 ,知道求出从起点到各个定点的最短路径.这个不仅仅是贪心,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围 现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:下图是的过程(用电子屏幕写字果然很不舒服):最终的路径为:代码如下:运行结果:1:

    34010

    系列:贪心(1)

    回想起自己学习的过程中,遇到了不少的坑坑.特想写一些文章去记录下自己过程中的所思说想,也借这些文章自己复习学习一下.这系列文章主要包括几个大类的,包括贪心,分治,动态规划,回溯,分支定界 ,线性规划等等,具体在这些大类内每次会选几个小例子去加深意识,并且会给出能够运行的代码来! .正文开始:贪心其实本身就跟我们人性一样,看到眼前的好吃的,拿来拿来别客气.但是丝毫不顾忌自己还得燃烧卡路里.贪心也是这样.贪心的本质其实就是总是做出当前最好的选择,也就是说总是期望通过局部最优选择从而得到全局最优的解决方 下一篇文章我们将说说使用Dijkstra解决最短路径问题,这也是贪心的一种,也是挺有意思的,还请多多指教.参考资料:1:大话数据结构,清华大学出版社2:,机械工业出版社3:趣学,人民邮电出版社 4:分析,人民邮电出版社

    44220

    系列:贪心(2)

    这篇文章我们将来一起看看贪心一个具体例子, DijkstraDijkstra最著名的应用是解决单元最短路径,这是一类贪心,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径 ,知道求出从起点到各个定点的最短路径.这个不仅仅是贪心,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围 下图是的过程(用电子屏幕写字果然很不舒服):??最终的路径为:?代码如下:?运行结果:1:输入样例?2:输出结果?下一篇文章我们将一起学习下哈夫曼编码

    39430

    -插入排序

    最近重新翻开宝典,打重新温习一下,顺便记录下自己的点滴。 中都是用的伪代码进行描述,我们这里直接用java代码进行第一章是描述一些的作用,我们这里直接忽略,下面就直接进入部分第二章第一节插入排序插入排序又是增量排序如下:另一种插入public 每次循环都将下标为i的元素插入到它前面已经排好序的队列中 for(int j=1;j 0 && arrs > temp) { arrs = arrs; i--; n++; } arrs = temp; } }}复杂度

    13220

    -归并排序

    第二章第一节插入排序插入排序又是增量排序如下:** * 归并排序 * 简介:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。

    19520

    leetcode 一些题及

    你可以假设每种输入只会对应一个。但是,你不能重复利用这个数组中同样的元素。 请你找出这两个有序数组的中位数,并且要求的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。 注意:中不可以包含重复的三元组。 不考虑输出的顺序。 示例:输入:23输出:.输入:234输出:.说明:尽管上面的是按字典序排列的,但是你可以任意选择输出的顺序。

    8320

    》堆排序笔记

    堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

    46990

    设计与分析_(第二版)

    【下载地址】 本书在介绍时,重点介绍用干设计的策略.非常与众不同。 书中介绍了剪枝搜索、分摊分析、随机、在线以及多项式近似方等相对较新的思想和众多基于分摊分析新开发的,每个都与实例一起加以介绍,而且每个例子都利用图进行详细解释。 本书适合作为高等院校设计与分析课程的高年级本科生和低年级研究生的教材,也可供相美科技人员和专业人七参考使用。

    37210

    之最大子段和

    》一书中对最大字段和可谓讲的是栩栩如生,楚楚动人。如果简单的说最大字段和,没有意义。而《》上举了一个股票的例子。 还有一点说明的是的实现是和语言没有关系的,下面是用OC来实现的,你也可以用Java, PHP, C++等你拿手的语言进行实现,注重的还是思想。   求此问题是通过分治来做的,通过递归方式来进行分治。 即为分解,计,合并的过程。

    42870

    第十八章 B树

    前面还留了两章:贪心和摊还分析,打后面再来补充。 之前的章节讨的支持动态数据集上的操作,如查找、插入、删除等都是基于简单的线性表、链表和树等结构,本章以后的部分在原来更高的层次上来讨这些操作,更高的层次意味着更复杂的结构,但更低的时间复杂度(包括摊还时间 在堆排序章节讨过二叉堆,除了union操作,二叉堆的性能都很好。该部分讨的二项堆和斐波那契堆对union操作能够获得很好的性能,此外,对于其他操作,也能获得较好的改进。 pair Search( int key ) { return _SearchInNode( _root, key ); } @brief 插入一个值的操作 这里没有使用《》里介绍的一趟的方 ,而是自己想象出来的二趟的方 效率肯定不如书上介绍的一趟优美,但是能解决问题。

    26360

    第七章快速排序

    一、快速排序概述关于快速排序,我之前写过两篇文章,一篇是写VC库中的快排函数,另一篇是写了快排的三种实现方。 现在再一次看,发现对快速排序又有了些新的认识,总结如下:(1)、快速排序最坏情况下的时间复杂度为O(n^2),虽然最坏情况下性能较差,但快排在实际应用中是最佳选择。

    323100

    第六章堆排序(一)

    Build_Max_Heap()经过严格推,可得时间复杂度为线性的,为O(n)。所以,Heap_Sort()就为O(nlgn)。

    314100

    第二章小试牛刀

    Author: bakari   Date: 2015.9.11《》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的呈现,读来让人欲罢不能;至于恨,是因为它在进行分析的时候所体现的数学思想太过于强大 关于,我认为掌握它最主要的是需要掌握两个方面:设计和分析,这也是的核心之处。这本书好就好在它是从的核心来展开章节的写作。 所以,本书刚开始的几章都是着眼于分析的本质:的执行效率,也就是的时间复杂度。 通过第二章对分析复杂度有初步印象之后,第三章趁热打铁引出相关描述复杂度的符号,如此便对如何表示一个的复杂度,以及如何分析的复杂度有了比较深入完整的认识。 我一直在想怎么来组织笔记的结构,也看了一些网友的博客,大致可以有三种方:是看了书之后提炼自己的想,还是照着书把重点的东西摘抄一边,亦或是把课后书本里的编程题还有课后习题自己动手实践一遍后在搬上来,第二种方很明显自己是学不到东西的

    462100

    第十三章 红黑树

    这次总挺过来了,前后零零散散的时间加起来差不多也有两天时间。 这次能坚持下来并攻克,我想大概有这么几个原因吧:第一是之前下定的决心要写一个最新版《》的读书笔记,之前几章都坚持写了,不能让这个成为拦路虎,即使再难再花时间都要弄懂;第二是通过前面几章的动手实践 但是是无如何也不可能找到这样的平衡条件,有一种树退而求其次,它的平衡条件是要求任何结点的左右子树高度相差不超过1,就是AVL树。AVL树是最早提出的将搜索树平衡化的想的实践。 如果按照《》书的步骤一步步往下看,是一定看得懂的,因为书上的东西是写的最全的,网友写的博客虽然有些也不错,但都是经过自己过滤过的,且不说语言表达怎样,肯定没有书本记录得详细。 书上没说具体的方,如果让我们在纸上写个左旋,估计好多人都要跪,因为指针指来指去,没有思路完全不行。

    33780

    第十一章 散列表

    散列表(为了形象描述,我们通常叫槽)从表意上看是一种数据结构,但把它归为思想更为贴切。对于大部分的查找问题,使用散列表能达到O(1)的效率。 当数据量很大的时候,要保证效率,这时采用hash表来处理是最佳的解决方。(详细可见July的博客:从头到尾解析hash表)。   回这个问题需要一定的数学底子,尤其是数,据前人计机科学家们多年的总结整理,有这样的三种设计方,我们不纠结这些方是如何设计出来,那样就违背了我们学习的原则,当然如果你想深究,那是甚好。 1、除散列:hash(key) = key % m其中,m是散列表的大小,该函数的一个指原则是将m选取为接近散列集合大小的质数。 其中,开放寻址又细分为:线性探查,二次探查,双重散列;链表和桶排序的思想一样,位每一个槽建立一些个桶来存放散列值相同的value,由于这种方比较简单,本文就不再做记录,后面的实现采用的是这种方

    49060

    》动态规划笔记(1)

    问题描述为:给定一段长度为n英寸的钢条和一个价格表pi,求切钢条方,使得销售收益最大。 课本上举了一个当n=4英寸的栗子,n=4时,有8种切割方,其中切为两段2英寸的方,收益最大为10.最优子结构为了求解规模为n的原问题,我们先求解形式完全一样,但规模更小的两个子问题,即当首次切割后, 我们通过组合两个相关子问题的最优解,并在所有可能的两段切割方中选取组合收益最大者,构成原问题的最优解。 如果随后再次需要此字问题的解,只需要查找保存的结果,而不必重新计。注意这里要保存之前的计结果,所以会消耗一定的存储空间,所以动态规划是典型的时空权衡的例子。 如果是,则直接返回保存的值,从而节省了计时间。否则,按通常方式计这个子问题,我们称这个递归过程是带备忘的,因为他“记住了”之前已经计过的结果。

    501100

    》动态规划笔记(2)

    然后看下重叠子问题重叠子问题重叠子问题是指子问题的空间必须足够小,即问题的递归会反复求解相同的子问题,而不是一直生成新的子问题。 步骤1:刻画最长公共子序列的特征首先可以想到的是暴力搜索方,暴力搜索就是说把X中的所有子序列找出来,然后判断是不是Y的子序列,如果是,就保存下来。 步骤3:计LCS的长度接受两个序列X,Y为输入,首先新建一个表c,然后把结果保存到表中。表b用来帮助构造最优解,b保存的是子问题的最优解。

    41290

    聊聊字典编码1 2 LZ773 LZ78

    最近由于课程设计需要做解压缩?特此来考察字典编码1 许多场合,开始时不知道要编码数据的统计特性,也不一定允许你事先知道它们的统计特性。 LZW在LZW中使用的术语与LZ78使用的相同,仅增加了一个术语—前缀根(Root),它是由单个字符串组成的缀-符串(String)。 现将LZW编码和译码介绍如下。1. 编码   LZW编码是围绕称为字典的转换表来完成的。 LZW编码器使用了一种很实用的分析(parsing),称为贪婪分析(greedy parsing algorithm)。 LZW取得了专利,专利权的所有者是美国的一个大型计机公司—Unisys(优利系统公司),除了商业软件生产公司之外,可以免费使用LZW

    1.5K30

    相关产品

    • IP 虚拟人

      IP 虚拟人

      IP 虚拟人(IP Virtual Human,IVH)运用了语音交互、数字模型生成等多项 AI 技术,让 IP 虚拟人的口型与发音一致、表情及动作自然拟人。IP 虚拟人支持 AI 合成虚拟形象播报视频和实时语音交互两大类使用场景,其中虚拟形象播报能力支持输入文本生成 AI 合成的音视频文件,广泛运用于媒体、教育、会展服务等场景;语音交互场景支持与用户进行实时语音互动,广泛运用于客服、助理等场景。

    相关资讯

    热门标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      扫码关注云+社区

      领取腾讯云代金券