这篇文章主要介绍 什么是数据结构，算法的时间复杂度，空间复杂度计算，包装类的装箱拆箱，

泛型语法，以及擦除机制。

目录

一、什么是数据结构

二、时间复杂度，空间复杂度

2.1 时间复杂度，空间复杂度是什么？

2.1.2 时间复杂度的计算（大O渐进表示法）

2.1.3空间复杂度的计算（大O渐进表示法）

三、包装类

3.1包装类是什么？

3.2 为什么引入包装类

3.3 包装类的装箱与拆箱

3.3.1 面试题（阿里）

四、泛型

4.1 什么是泛型

4.2 泛型的使用

4.3 泛型中的擦除机制

4.4 泛型的上界

4.4.1 泛型类型接入接口 Comparable

---

一、什么是数据结构

一种描述组织一组数据的方式

其实很好理解，就是把不同种类的数据用不同的结构存储，就是数据结构

但是对数据结构的操作离不开算法，所以我们一般会把数据结构和算法放到一起来学

---

二、时间复杂度，空间复杂度

2.1 时间复杂度，空间复杂度是什么？

我们在写出一个算法时，不同的方法会有不同的执行速度，不同的程序占用的空间也不同。

比如你去算1-100的和，一个一个加和用通项公式的速度肯定不同，在代码中，一般会判断在循环中循环多次，大概判断执行次数。

我们为了评判一个算法或者程序的好坏，就提出了时间复杂度，空间复杂度的概念。

---

2.1.2 时间复杂度的计算（大O渐进表示法）

一个算法实际的执行时间是求不出来的，所以我们用一种 数学函数 去 算一个程序执行的最差的执行时间 它的计算原则是：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。 

看着有点懵，我们通过实践来理解规则:

再来几个例子

有限次数的程序：

---

冒泡排序算法：

---

对数级的时间复杂度：

---

对于递归算法，我们计算的公式稍微有些不同：

递归的时间复杂度 = 递归的次数*每次递归执行的次数

斐波那契递归算法要具体分析，不能套用公式，它是等比数列求和。

---

2.1.3空间复杂度的计算（大O渐进表示法）

以前的内存资源比较珍惜，现在技术发展，我们没有那么关注空间复杂度了

空间复杂度的计算主要就看算法中创建了多少个变量，一个就是O(1)，N个O(N)。

---

常见的复杂度：

---

三、包装类

3.1包装类是什么？

包装类就是 把 基本类型，写成一个类，在里面有操作这个类型的方法，底层还是基本类型

除了Integer 和 Character 其他 基本类型 的包装类都是首字母大写

---

3.2 为什么引入包装类

引入包装类是为了解决基本数据类型（例如int，char等）不能直接参与面向对象的操作的问题。在面向对象编程中，只能使用对象来进行操作，而基本数据类型不是对象。为了能够在面向对象的环境中使用基本数据类型，Java引入了包装类来将基本数据类型封装成对象。

---

3.3 包装类的装箱与拆箱

把基本类型 转化 为包装类型 我们叫 装箱，也叫装包

把包装类型 转化 为基本类型 我们叫 拆箱，也叫拆包

有自动和显示两种方法：

---

装箱：

---

拆箱：

---

3.3.1 面试题（阿里）

结果：

是第一个是 true 第二个是 false

---

原理：

这里使用自动装箱，我们看看装箱的源码：

范围在 low 和high 之间的直接拿数组中的值（左闭右开），在这个范围外的返回一个新的对象，所以a b是相同的，而c d 地址不同，返回false

---

四、泛型

4.1 什么是泛型

一般的类和方法，只能使用具体的类型: 要么是基本类型，要么是自定义的类.

有什么办法可以随意更改类型呢？

泛型是一种特性，在JDK1.5中引入的语法，就是为了解决上面的问题，将类型进行参数化，使用方法或者类时，指定具体的类型参数，这就是泛型。

---

4.2 泛型的使用

1. 先定义一个万能数组，可以存放各种类型的数据：

2. 我们作为使用者去调用一下试试：

---

4.3 泛型中的擦除机制

我们也好奇，泛型真神奇，真好用，那我们调用的数组就变成 Integer 类型的了吗

这里就用到了一种叫 擦除机制 的机制，泛型是一种编译时期的机制，在运行时没有；

在上方我们对数组传值，虽然传入的是 Integer 类型的，但在运行时会被 擦除机制 擦除为 Object类型，包括下面我们展示的数组 也被擦除为原来的类型了。

---

4.4 泛型的上界

泛型的上界是指在使用泛型时限制类型的范围。它可以用来限制必须是泛型类型 必须是某个类的子类 或 实现了 某个接口。

public class MyClass<T extends Number> {}

是不是很奇怪，干嘛要这么做？？？下面为你举个例子

4.4.1 泛型类型接入接口 Comparable

我们之前介绍了，基本类型比较比较简单，但是自定义类型的比较要继承 Comparable 类

 我们写一个泛型类，当中有个方法 可以求数组最大值：

先不定义上界：

这下全明白了，为了规避这种情况，提出了泛型的上界概念

我们修改代码：

这样代码就正常了