数据结构笔记总结(1.8)简单的时间复杂度分析

简单的时间复杂度分析

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

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

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

通常这样一个算法时间复杂度是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)简单的时间复杂度分析

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

立即加入 了解更多