1. 初识集合框架
1.1 什么是集合框架
在了解集合框架之前,我们先来认识一下数据结构,所谓数据结构就是描述和组织数据的一个东西.
那什么是集合框架呢?在java里面集合框架(Java Collection Framework),又被称为容器container,说白了就是很多个接口,抽象类,实现类组成的一个包,集合框架的这些实现类和接口被放在java.util下面.主要用来对元素进行增删查改.
下图是主要的结构:
接口之间是extends扩展关系,类和类之间是extends继承关系,接口与类之间是
implements实现关系.
1.2 后续会实现的底层
1> Collection: 是一个接口,包含了大部分容器常用的一些方法
2> List: 是一个接口,规范了ArrayList和LinkedList中要实现的方法
ArrayList: 实现了List接口,底层为动态类型顺序表
LinkedList: 实现了List接口,底层为双向链表
3> Stack: 底层是栈,栈式一种特殊的顺序表(先进后出)
4> Queue: 底层是队列,队列是一种特殊的顺序表(先进先出)
5> Deque: 是一个接口
6> Set: 集合,是一个接口里面放的是K模型
HashSet: 底层是哈希桶,查询的时间复杂度是O(1)
TreeSet: 底层是红黑树,查询的时间复杂度为O(log2N),关于key有序的
7> Map: 映射,里面存储的是K-V模型的键值对
HashMap: 底层是哈希桶,查询的时间复杂度是O(1)
TreeSet: 底层是红黑树,查询的时间复杂度为O(log2N),关于key有序的
2. 时间复杂度空间复杂度
2.1 如何衡量一个算法的好坏?
衡量一个算法的好坏,我们一般分俩种情况
1> 时间效率
时间复杂度,粗略估计用大O的渐进表示法,计算的是算法中的基本操作的执行次数
2> 空间效率
空间复杂度,临时占用存储空间大小的度量.(额外的开销)
对于一个复杂度,我们一般从这三个方面来考虑
1> 最好情况下
2> 平均情况下
3> 最坏情况下(这个是我们以后默认讨论的情况)
2.2 时间复杂度
算法的时间复杂度是一个数学函数,算法中的基本操作的执行次数，为算法的时间复杂度。
2.2.1 大O的渐进表示法
几个规则:
1> 用常数1 取代运行时间中所有的加法常数
2> 在修改后的运行次数函数中,只保留幂次最高的项数(这个和高数的取极限类似,当n比较于无穷的时候幂次最大的项数占主导地位,也叫做取大头)
3> 最高阶的项数于之相乘的常数化为1
经历以上三个步骤就可以算出来大O阶
我们来看一个详细例子
2.2.2 几个小例题
我们计算递归的话,需要注意一下,我们计算的是 递归的次数*每次递归后执行的次数
相当于等比数列求和:
2^0+2^1+....+2^(n-)
可以得出O(2^n)
2.3 空间复杂度
我们之间看题目
我们每次调用dibonacci就会创建一个数组,大小为N,因此空间复杂度为O(N)
这个我们递归了N次,开辟了N个栈帧,因此空间复杂度为O(N)