Java针对封装数组的简单复杂度分析方法
作者:WFaceBoss 时间:2022-12-22 03:28:58
本文实例讲述了Java针对封装数组的简单复杂度分析方法。分享给大家供大家参考,具体如下:
完成了数组的封装之后我们还需对其进行复杂度分析:
此处的复杂度分析主要是指时间复杂度分析,算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。
1.简单概念
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。相关图如下:
从图中可见,我们应该尽可能选用多项式阶O(nk)的算法,而不希望用指数阶的算法。
见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
2.大O简单定义(非数学领域)
大O描述的是算法运行时间和输入数据之间的关系
3.简单程序时间复杂度分析
在上述中算法和n呈线性关系,那为什么要使用大O呢?称作O(n)?
其实上述的程序中,实际的实际时间复杂度:T = c1*n + c2,在这里忽略了常数c1和c2。
因此:算法和N呈线性相关,取n的高阶项,因为当n趋于无穷大的时候,低阶项起的作用很小。
4.对动态数组的时间复杂度进行分析
(1)动态数组添加操作时间复杂度分析
(1)addLast(e)方法 :只需在最后位置添加 时间复杂度 为O(1)
(2)addFirst(e)方法,数组中均需向后移动一位 时间复杂度 为O(n)
(3)add(index,e)方法,在index位置插入e,时间复杂度与选择的位置有关,选择最后时间复杂度 为O(1);选择第一个位置时间复杂度 为O(n);对于其他情况与概率有关,在平均情况下只需要移动n/2个位置 时间复杂度 为O(n/2)=O(n)
总的来说:数组添加的时间复杂度为O(n)(最坏情况考虑)
在添加的时候可能会触发resize方法,需要移动n个元素到新数组中 时间复杂度 为O(n)
(2)动态数组删除操作时间复杂度分析
相同的分析方法,可以得出删除操作的时间复杂度
(3)动态数组修改操作时间复杂度分析
对于修改,只要通过索引找到即可进行修改,时间复杂度为O(1)
(4)动态数组查找操作时间复杂度分析
动态数组时间复杂度分析总结:
关于resize方法,我们完全使用最坏情况分析是不合理的,其分析情况我们将在下一节进行学习~
希望本文所述对大家java程序设计有所帮助。
来源:https://www.cnblogs.com/wfaceboss/p/10619316.html
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Linux环境g++编译GDAL动态库操作方法
![](https://img.aspxhome.com/file/2023/4/109784_0s.jpg)
C#动态生成DropDownList执行失败原因分析
spring启动加载程序的几种方法介绍
C# 汉字与拼音互转的实现示例
![](https://img.aspxhome.com/file/2023/0/98200_0s.png)
springmvc如何使用POJO作为参数
![](https://img.aspxhome.com/file/2023/1/61831_0s.png)
Android实现Tab切换界面功能详解
![](https://img.aspxhome.com/file/2023/7/118977_0s.png)
深入理解Java8新特性之接口中的默认方法和静态方法
![](https://img.aspxhome.com/file/2023/9/59759_0s.png)
SpringBoot应用启动流程源码解析
深入理解Java并发编程之ThreadLocal
![](https://img.aspxhome.com/file/2023/8/59018_0s.jpg)
springboot如何获取相对路径文件夹下静态资源的方法
![](https://img.aspxhome.com/file/2023/2/86782_0s.png)
C#中的静态成员、静态方法、静态类介绍
![](https://img.aspxhome.com/file/2023/1/92961_0s.jpg)
Spring自定义注解配置简单日志示例
Unity shader实现消融效果
![](https://img.aspxhome.com/file/2023/4/66584_0s.gif)
SpringSecurity实现访问控制url匹配
![](https://img.aspxhome.com/file/2023/1/63401_0s.jpg)
springboot中request和response的加解密实现代码
![](https://img.aspxhome.com/file/2023/6/79826_0s.png)
在Java中int和byte[]的相互转换
Android仿淘宝商品详情页
![](https://img.aspxhome.com/file/2023/6/111726_0s.gif)
为何Java8需要引入新的日期与时间库
![](https://img.aspxhome.com/file/2023/9/71659_0s.png)
详解context root修改无效web修改项目路径(eclipse)
![](https://img.aspxhome.com/file/2023/2/85902_0s.png)
JavaWeb利用struts实现文件下载时改变文件名称
![](https://img.aspxhome.com/file/2023/1/71621_0s.jpg)