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
0
投稿猜你喜欢
- java.util.concurrent.ExecutionException错误信息，这里给出解决方案，大家根据具体要求更改。SEVERE
前言C#中Try-Catch语句大家都很熟悉了，但是细究起来，还是有很多东西可讲的。最近在翻看之前总结的常见面试题中，发现关于try...c- 首先先简单的说一下其3大特性的定义：封装：隐藏对象的属性和实现细节，仅对外公开接口,控制在程序中属性的读和修改的访问级别。将抽象得到的数据和
- 介绍一款简洁实用的图片编辑器，纯dart开发。支持：涂鸦、旋转&翻转、马赛克、添加文字，及自定义ui风格。功能演示涂鸦旋转&
- 介绍在 .NET4.0 之前，如果我们需要在多线程环境下使用 Dictionary 类，除了自己实现线程同步来保证线程安全外，我们没有其他选
- 一：背景1.讲故事最近遇到一位朋友的程序崩溃，发现崩溃点在富编辑器 msftedit 上，这个不是重点，重点在于发现他已经开启了 页堆 ，看
- 介绍记录将elasticsearch集成到spring boot的过程，以及一些简单的应用和helper类使用。接入方式使用spring-b
- 1. RocketMQ Topic创建机制以下源码基于Rocket MQ 4.7.0RocketMQ Topic创建机制分为两种：一种自动创
- package list;import java.util.ArrayList;/** * Java约瑟夫问题： n个人（不同id
- 目录前言hibernate-validator基本使用引入依赖编写需要验证对象验证对象属性是否符合要求验证规则空/非空验证bool时间数学字
- 对于一个应用程序而言，控件是搭建用户界面的积木。它们具备交互式的特征。VS 2012中的控件都放在工具箱中，添加一个控件到窗体，只需在工具箱
- Quote在学习 Kotlin 的过程中，对 Kotlin 的类型系统产生了好奇，Kotlin 是否存在类似于 Java 中 Object
- IntelliJ IDEA 安装后需要进行初始化配置已更加方便使用。本文整理了比较通用的安装后初始配置。本文的版本：IntelliJ IDE
- kafka消费不到数据的排查集群上新安装并启动了3个kafka Broker，代码打包上传至集群，运行后发现一直消费不到数据，本地
- yml 文件规则yml文件的好处，天然的树状结构，一目了然，实质上跟properties是差不多的。不支持tab缩进可以使用 "-
- 前言在前面的篇章中，对Java语言的简单数据类型、数组、运算符和表达式以及流程控制的方法做了详细介绍。从本章开始，我们正式介绍面向对象的程序
- 本文实例讲述了C#使用xsd文件验证XML格式是否正确的实现方法。分享给大家供大家参考，具体如下：//创建xmlDocumentXmlDoc
- Android手机或平板都会存在横竖屏切换的功能，通常是由物理重力感应触发的，但是有时候也不尽然，通常在设置里面我们可以对手机的横竖屏切换进
- 程序在32位操作系统上运行正常，在64位操作系统上运行读卡功能提示”试图加载格式不正确“。-------------------------
- 本文实例讲述了C#警惕匿名方法造成的变量共享。分享给大家供大家参考，具体如下：匿名方法匿名方法是.NET 2.0中引入的高级特性，“匿名”二
