简单的时间复杂度分析-尊龙官方平台

简单的时间复杂度分析

el/2024/3/25 17:23:43

 n是数据规模,o是渐进时间复杂度,描述的是n趋近于无穷的时候的算法用时,所以忽略常数,毕竟在无穷的面前常数可以忽略不计。

o(1):算法运行时间是一个常数与数据规模无关
o(n):算法运行时间与数据规模是线性关系
o(lgn):
o(nlogn):
o(n^2):算法运行时间与数据规模是平方关系

下图第三个算法在数据量小的时候效率高于第二个算法的效率,但是在对复杂度分析时数据量n是趋近于无穷的,所以前两个算法都比第三个算法的效率高。可以利用很多高阶算法的常数比较小的特性,将较小的数据量传给他,这样得到的结果的效率就会提升很多。

在算法复杂度分析的时候我们一般都是关注最慢(最坏)的情况,但是有些算法复杂度小概率是o(n),大概率是是o(1),动态数组的添加方法addlast(),只要数组不满就不需要创建一个新的更大的数组resize(),因此对这种算法的复杂度分析要均摊复杂度

假设数组容量为n,进行了n 1次addlast(),触发resize,总共进行了2n 1次的操作,平均每次addlast()进行2次基本操作,意味着时间复杂度是o(1)

如果如下列代码所示addlast()方法新增值,removelast()方法删除值,那么他们就会发生复杂度震荡, addlast()与removelast()明明在均摊的时候复杂度都是o(1),但下列代码行时就此次都是o(n)复杂度。造成这种情况的原因是扩容和缩容的都太激进了(eager),可以将resize()的调容策略设置的懒惰(lazy)点,修改为本次添加时数组容量添加不下再扩容两倍本次删除后使用容量小于总容量的四分之一再缩容一半,就不会出现复杂度震荡。

执行while的代码前:数组容量为10,已经使用了9个容量
while(true){addlast()添加一个值 -> 使用了全部的容量 -> 触发resize() -> 容量调整为20removelast()删除一个值 -> 占用总容量的一半 -> 触发resize() -> 容量调整为10
}

 注:resize()方法是当数组容量已满时创建一个原数组两倍容量的新数组,或者当数组使用容量为数组容量的一半时创建一个原数组一半容量的新数组,遍历原数组中的值全部存放到新数组中


http://www.ngui.cc/el/5127253.html

相关文章

什么是栈以及用数组实现一个栈-java

虽然栈操作看起来比数组要简单的多,但对于计算机逻辑来说是非常重要的 我们在执行程序的的时候,可能会如下列伪代码一样在方法1里调用方法2,在方法2里调用方法3,执行完毕后一层一层的返回,这就是借助程序调用的系统栈来…

什么是队列以及用数组实现队列-java

就和我们现实生活中排队一样,队列就是先进先出,从队尾进,从队首出 然后使用https://blog.csdn.net/test253506088/article/details/119538593编写的动态数组来实现一个队列arrayqueue public class arrayqueue implements queue<…

效率更高的循环队列-java

数组队列中的出队,在时间复杂度上是o(n)复杂度,因为你删除数组首端,后面的数据都要左移一位。 我们可以记录一下队首的索引和队尾索引,入队时队尾索引1,出队时队首索引-1,当队首索引与队尾索引相等时代表队…

单向链表-java

如果某个节点的next是null则代表该节点是最后一个节点,属性名为head的为第一个节点。 虚拟头结点(dummyhead)对于链表的使用者来说毫无意义,只是为了让头结点固定不改动、实现起来更方便而设计出来的一个概念。 实现代码 package blacktv.linkedlist;/*…

用单向链表实现栈-java

链表的读取、添加、删除第一个节点的时间复杂度是o(1),所以我们可以用链表来实现一个栈,最关键的是不需要考虑栈的大小,所以链表栈会比数组栈时间复杂度会低。 接口 package blacktv.stack;/*** 栈需要实现的一些接口*/ public interface stack

用单向链表实现队列-java

本文档编写的队列用的是根据单向链表编写的单向链表改进后编写的。总效果和循环队列是一样的。 接口: package blacktv.queue;/*** 实现队列需要完成的接口*/ public interface queue {/*** 入队** param e*/public void enqueue(e e);/*** 出队…

java 不同情况下byte里存储的是什么编码格式

string转成byte[]存成什么? 并不一定是ascii码。 1、 在java语言中,string 对象通过方法gebytes()可以获得byte[]对象, 它实际上是把内部的char字符,按照平台默认的字符集编码成byte数组, 2、 此外,也可以使用getbyte…

java 线程wati使用中出现的问题

首先先声明一点,wiat()方法必须释放cpu资源和锁资源,因此wiat()方法必须在锁里面调用,不在锁里面写就没有锁可释放,没锁资源可释放的话就会抛出异常。有了上述的铺垫我们来看以下代码: package test; /* 主线程测试类…

java 线程中断究竟是个啥玩意

个人对中断的理解: 线程中断就是一个信号,当有调用中断方法之后会发送一个中断信号,interrupted()或isinterrupted()的返回值会是true,没有中断信号时interrupted()或isinterrupted()的返回值是false。接收到信号之后,…

双向链表与双向循环链表

循环链表的末尾指向dummyhead 第一个节点是66下面的1代表第二个节点在数组的索引为1的地方,而99这一个节点的下一个节点索引为-1则该节点为最后一个节点。
网站地图