最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 简单的时间复杂度分析

    我们经常能看到用下面这些方式描述时间复杂度

    什么是运行时间和输入数据之间的关系呢?

    我们可以看一个非常简单的代码:下面是对一个数组中所有数字求和的代码,逻辑很简单。

    通常这样一个算法时间复杂度是O(n),n是nums中的元素个数,意思是n和nums中的个数呈线性关系,线性关系表现在n是一次方。

    为什么要用大O,叫做O(n)呢?

    原因是忽略了许多常数。

    在这个算法中,for循环把这个数从nums中取出来,其次还要把sum这个数给取出来,然后把sum和nums加在一起,最终把结果扔回给sum这个变量中。

    对每一个数都要做这么多操作,所花费的总时间叫c1。

    整个算法中,开始前开辟一块int型空间sum,把0初始化赋给sum。

    整个算法运行结束后,还要把sum给return回去,这些过程就是c2。

    所以我们这个算法实际运行时间是c1*n+c2。

    但是在分析的时候,如果把c1和c2具体是多少也分析出来,一方面这是没有必要的,更重要的是在有些情况下也是不可能的。

    比如把num从nums中取出来,不同的语言基于不同的实现,实际运行的时间是不等的,所以一般情况下我们是忽略这些常数的。

    如上图所示,n越大,一个低阶算法的时间复杂度才能体现出来。

    分析动态数组的时间复杂度

    结合上一节的动态数组,我们来分析一下它的时间复杂度。

    添加操作

    首先分析添加操作,总体来说是个O(n)级别的算法,

    删除操作

    再来看一下删除操作,总体来说是个O(n)级别的算法。

    修改操作

    只要知道修改的元素对应的索引是哪个就行了,用专业一点的术语来说就是支持随机访问,是个O(1)级别的算法。

    查询操作

    如果知道所查元素的索引,那么复杂度为O(1),但是如果不知道索引是多少的话,有两个方法,一个是contains(e),另一个是find(e),对于这两个操作时间复杂度为O(n)。

    分析动态数组的时间复杂度

    特别要注意,增和删如果只针对最后一个元素操作的话,无论是addLast还是removeLast,其实这两个操作的是O(1)级别的操作,可是为什么说还是O(n)级别的操作?

    就是因为有resize,我们一旦有resize了,就需要把整个元素全都复制一遍,赋值给一片新的空间。

    看起来resize好像是一个性能很差很耽误事情的这样一个操作,可是实际上对于resize这个操作,如果我们完全使用最坏情况来分析是很不合理的。

    下一小节我们会引入一种新的时间复杂度的分析办法,那就是所谓的均摊时间复杂度。

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(1.8)简单的时间复杂度分析

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 102会员总数(位)
    • 3674资源总数(个)
    • 2本周发布(个)
    • 0 今日发布(个)
    • 136稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级