Java数据结构与Java算法学习---时间复杂度分析

逻辑结构：数据与数据之间的关系分类的

物理结构：计算机存储角度出发的分类

逻辑结构：之间的不同是按照数据之间不同的关系进行分类的

逻辑结构中最常用的是数组。根据索引进行查找

目录

一、基本内容的了解 

1.1数据结构 2

1.1.1顺序结构 

1.1.2链式结构 

1.1.3两种数据结构的比较

1.2算法 3

二、算法的时间复杂度分析 4

2.1事后分析估算方法

2.2事前分析估算方法

影响时间的因素：

2.3算法核心操作次数与输入规模关联（事前分析估算方法分析---函数渐近增长）5、6

2.4算法时间复杂度 7

2.4.1大O记法 

2.4.2常见的大O阶 8

2.4.3函数调用的时间复杂度分析 9

2.4.4最坏情况 9

三、空间复杂度分析 10

3.1java中常见内存占用

3.2空间复杂度的案例

---

本部分是算法分析的ppt学习内容

一、基本内容的了解 

1.1数据结构 2

1.1.1顺序结构 

顺序结构：使用的是数组 

顺序结构的弊端：数据顺序排列好后，再有其他的数据来加入，不能插入。

1.1.2链式结构 

链式结构：解决了该弊端，采取指针解决。内存地址不是连续的

1.1.3两种数据结构的比较

区别：

查询效率：顺序结构高

插入效率：链式结构高

1.2算法 3

算法的要求： 

二、算法的时间复杂度分析 4

2.1事后分析估算方法

该方法是要求所测试的算法按照实际进行跑通。算法要是过长的话，就会浪费很长的时间。

2.2事前分析估算方法

影响时间的因素：

2.3算法核心操作次数与输入规模关联（事前分析估算方法分析---函数渐近增长）5、6

2.4算法时间复杂度 7

2.4.1大O记法 

函数渐近增长分析：

大O记法的原则：也是根据函数渐近增长分析来进行。

注： 

1、函数渐近增长的分析中，常数可以被忽略。在大O记法中将所有的常数无论大小，都记为1。

2、对应函数渐近增长分析中的第三条，只保留最高次幂即保留高阶项。

3、对应函数渐近增长分析中的第二条，和最高次幂的常数因子可以被忽略。

例子看PPT。

2.4.2常见的大O阶 8

本部分具体看本节的ppt 

1、线性阶

2、平方阶

3、立方阶

4、对数阶

 对数阶的时间复杂度：为什么忽略掉对数的底数？

 5、常数阶

 时间复杂度的总结：

 时间复杂程度从低到高（效率越低）：

 通常如果时间复杂程度的是大于等于O(n^2)的话，这个算法是要考虑进行优化的。

2.4.3函数调用的时间复杂度分析 9

每个方法的时间复杂度的相加。参考PPT中的案例三

2.4.4最坏情况 9

 看本部分的PPT

三、空间复杂度分析 10

3.1java中常见内存占用

1、基本数据类型内存占用情况

 

2、计算机访问内存的方式都是每次一次一个字节

 

3、一个引用需要8个字节表示

一个引用：程序中的变量

4、创建对象需要的内存大小

创建对象本身16个字节（保存自身的开销）+对象内部存储的数据大小

由上面两部分组成。

5、一般内存的使用，如果不是8为字节的倍数，会自动填充为8字节

例子： 

 6、创建一个数组为对象的话，占用内存24个字节

3.2空间复杂度的案例

 详情看PPT

注：在Java开发中，一般只考虑时间复杂度即可。