对集合、复杂度以及泛型的认识

文章目录

一、集合框架是什么？
二、复杂度
- 1.时间复杂度
- 2.空间复杂度
三、泛型

一、集合框架是什么？

Java 集合框架 Java Collection Framework ，又被称为容器 container ，是定义在 java.util 包下的一组接口 interfaces 和其实现类 classes 。

类和接口如下：

1. Collection：是一个接口，包含了大部分容器常用的一些方法

2. List：是一个接口，规范了ArrayList 和 LinkedList中要实现的方法

ArrayList：实现了List接口，底层为动态类型顺序表

LinkedList：实现了List接口，底层为双向链表

3. Stack：底层是栈，栈是一种特殊的顺序表

4. Queue：底层是队列，队列是一种特殊的顺序表

5. Deque：是一个接口

6. Set：集合，是一个接口，里面放置的是K模型

HashSet：底层为哈希桶，查询的时间复杂度为O(1)

TreeSet：底层为红黑树，查询的时间复杂度为O(log以2为底N ),关于key有序的

7. Map：映射，里面存储的是K-V模型的键值对

HashMap：底层为哈希桶，查询时间复杂度为O(1)

TreeMap：底层为红黑树，查询的时间复杂度为O(log以2为底N )，关于key有序

二、复杂度

1.时间复杂度

2.空间复杂度

这里请参考之前写的一篇关于复杂度的博客：如何评价一个算法的好坏？-复杂度_crazy_xieyi的博客-CSDN博客大O表示法来描述复杂度，需要忽略常数、系数和低阶。O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)。用尽量小的存储空间，用尽量少的执行步骤。第64个斐波那契数（n=64），用O(n)计算大约耗时6.4*10^(-8)秒，用O(2^n)计算大约耗时584.94年。… 对集合、复杂度以及泛型的认识 https://blog.csdn.net/crazy_xieyi/article/details/126062123?spm=1001.2014.3001.5501

这里看一个非常经典的题目：

// 计算斐波那契递归的复杂度？

int fifibonacci(int N) {

return N < 2 ? N : fifibonacci(N-1)+fifibonacci(N-2);

}

1.时间复杂度

这里就要分析递归了多少次。

计算执行次数，为等比数列求和：2^0+2^1+2^2+……+2^(n-1)=2^n-1

所以时间复杂度为：O(2^N)

2.空间复杂度

在计算空间复杂度的时候，需要注意一点就是：当一条链路递归完成之后，返回来的时候，其所占的空间就被释放了，所以空间复杂度以最长链路为准，及空间复杂度为：O(N）

三、泛型

泛型是在JDK1.5引入的新的语法，通俗讲，泛型
就是适用于许多许多类型。从代码上讲，就是对类型实现了参数化。在编译的时候会进行类型的检查和转换。

小技巧：设置泛型：shift + F6

语法

泛型类变量名; // 定义一个泛型类引用

new 泛型类(构造方法实参); // 实例化一个泛型类对象

注意：泛型只能接受类，所有的基本数据类型必须使用包装类！

当编译器可以根据上下文推导出类型实参时，可以省略类型实参的填写。

MyArray list = new MyArray();

擦除机制

在编译的时候会进行类型检查，最后在编译完成的字节码文件中，都变成了Object。

泛型的上界

在定义泛型类时，有时需要对传入的类型变量做一定的约束，可以通过类型边界来约束。

public class MyArray {

…

}

只接受 Number 的子类型作为 E 的类型实参。此时E是 Number的子类或Number本身，因为此时引入了泛型的上界，那么在擦除之后，为Number。

注意：没有指定类型边界 E，可以视为 E extends Object

如果涉及到元素的比较，那么E必须是实现了Comparable接口的。

public class MyArray<E extends Comparable> {

…

}

通配符

? 用于在泛型的使用，即为通配符。

一个例子：

public class TestDemo {

public static void main(String[] args) {

Message message = new Message() ;

message.setMessage(55);

fun(message);

}

// 此时使用通配符”?”描述的是它可以接收任意类型，但是由于不确定类型，所以无法修改

public static void fun(Message temp){

//temp.setMessage(100); 无法修改！

System.out.println(temp.getMessage());

}

}