枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这里他们就是判断类问题我们就可以使用枚举。

​ 但是注意这里我们需要考虑的就是枚举的方式,也就是枚举的角度。这里有一个小的例子就是最长回文子串的问题。

​ 首先我们就是用一个最简单的方式就是枚举出所有的字串,然后在这些字串里面找回文串。这样我们首先需要进行枚举就需要 n 平方的复杂度,然后我们还需要 n 的时间去判断这个串是不是回文,那么也就是说我们需要 n 三次方的时间复杂度。

​ 然后上面的方式枚举的对象就是所有的字串,但是我们仔细就会发现重点在于回文子串的中心,如果我们枚举的是回文子串的中心以及回文的长度,我们就更简单的找到最长回文子串。中心不仅仅就是每一个字符还包括他们之间的缝隙,这样我们就有了 2n + 1 个中心,然后在对他们进行回文判断,最后的时间复杂度也就是 n 平方。

​ 这里是从 n 三次方降到了 n 平方的复杂度,这样的原因在于我们去掉了很多的无用的字串,第一个枚举的方法就是枚举所有的字串,然后第二个就是仅仅找出那些具有回文形式的字串,这样就少了一个 n 。经常这样思考会慢慢锻炼我们优化时间复杂度的能力。

​ 并且这里看着是 n 平方其实他根本没有那么多的复杂度,因为每一个中心能找到的会问其实并不多除非我们给的一个串是一个完全相同的字符,这也就是第二种算法的最坏情况。

​ 其实在枚举的过程中有的枚举并没有必要,因为这些就是用来占用了时间复杂度但是没有给程序带来多大的帮助。然后我们在计算的时候有时候题目给的条件很少,这时候我们就需要使用枚举来增加我们已知的条件。

​ 再看一个例子就是在一个矩阵中填满数,然后这些数有正有负我们需要获取一个和的最大矩阵。这里我们先不考虑 DP 而是使用枚举的方式来解这道题。因为这道题的内容是静态的,也就是矩阵是不变化的,我们可以使用计算存储,然后再使用排容原理解题。首先我们考虑一维的情况,我们可以新开一个矩阵,这个矩阵的目的就在于把原来的矩阵的到当前位置的和记录下来。这样我们仅仅需要一次的扫描就能获取从 0 到当前位置的和,然后我们可以计算出任何两个点的之间的和,使用排容原理,就是后面的下标的和减去前面的下标的和即可。这样一个最大的和我们就可以使用 n 的复杂度完成。

​ 然后我们扩展到二维的情况,就是新开一个矩阵,然后每一个位置记录 ( 0 , 0 ) 位置到当前位置的和。至于这个和怎么算还需要一个过程,中间我们还需要构造一个矩阵,这个矩阵就是先计算出每一行的和,也就是我们上面所说的一维的情况,然后再过渡到二维的辅助阵列。

​ 那么这个算法的复杂度就是一开始我们需要算出这个辅助矩阵的和需要 n 平方的时间,然后需要进行排容原理,也就是我们要枚举左上角和右下角的位置这里就需要 n 的四次方的时间。

​ 但是这样做还是不够好,也就是我们枚举了每一个矩形,我们只是优化了 计算矩形的和。但是我们可以使用另外一种思路就是枚举左右边界,然后我们计算出上下界,这样的话这里的时间复杂度就是 n 平方乘以我们算出上下界的时间。而我们算上下界的时候因为我们已经指定了宽度所以说这个宽度之间的东西我们可以把它影射成一维的解决即可。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MyBatis笔记二:配置

    lwen
  • MyBatis笔记二:配置

    可以看到我们使用 <properties resource="db.properties"/> 引入了我们的数据据库的配置文件,然后这个标签有两个属性 : r...

    lwen
  • 动态规划

    ​ 动态规划一般来说和分治有点类似都是让他们去处理相同的子问题,但是在动态规划里面你会遇到更多的相同子问题。然后我们就会导致很多的重复计算,所以一般我们可...

    lwen
  • 历时3个月,我们是如何为一个开源项目集资300万美元的?

    长期以来,开源项目一直都面临着融资难的问题。PostHog很幸运地获得了大量的资金,并希望跟大家分享我们的经历,以帮助其它那些很酷的项目也能早日启动。

    CDA数据分析师
  • 腾讯云服务器购买配置的选择

    这里我要说的是,目前腾讯云只有服务器,没有虚拟主机,所以这里我们说的云服务器就是所谓的服务器。对于服务器的选择还是很讲究的,比如配置、内存、带宽,以及机房。

    用户5908769
  • 陆奇的创业方法论:潮流、挑战和机遇

    创业很难,挑战很多,往往九死一生,但创业机会也很大,如何拥抱机会,应对挑战是创业者们关心的话题。

    AI科技大本营
  • 《Java从入门到放弃》框架入门篇:hibernate基本配置

    十方上下
  • [计算机视觉论文速递] 2018-03-20

    通知:这篇推文有13篇论文速递信息,涉及图像分割、SLAM、显著性、深度估计、车辆计数等方向 往期回顾 [计算机视觉] 入门学习资料 [计算机视觉论文速递] ...

    Amusi
  • Django实战-生鲜电商-订单评论

    经过几轮的视图类的编写,整个电商项目的逻辑有清晰一点了么?对于事务逻辑的数据处理,分为查询和创建。相对于本项目来说,创建的操作大多数在用户下单到支付成功这一过程...

    小团子
  • 【NIPS要改名】米兔运动掀巨浪,AI学术圈不再容忍性别歧视!(投票)

    【新智元导读】NIPS会议的名称一直饱受争议。今天,女性AI研究者lu popolvuh在Medium上发表文章,使用 #MeTooSTEM 的tag,揭露在会...

    新智元

扫码关注云+社区

领取腾讯云代金券