- 1.什么是集合框架
- 2.集合框架的重要性
- 3.所涉及的数据结构
- 4.算法效率
- 5.时间复杂度
- 5.1时间复杂度的概念
- 5.2 大O的渐近表示法
- 5.3 推导大O的方法
- 5.4 常见的时间复杂度计算举例
- 6.空间复杂度
Java的集合框架可以看作是一个容器，是定义在包下的一组接口和其实现类。将多个元素置于一个单元内，用于对这些元素的存储，检索，管理，也就是增删改查。
- 有助于我们便捷，快速的写出高效，稳定的代码
- 学习背后的数据结构知识，有助于理解各个集合的优缺点以及应用场景
数据结构：是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合
collection：是一个接口，包含了大部分容器常用的一些方法
list：是一个接口，规范了ArrayList 和linkedLIst 中要实现的方法
ArrayList：实现了list的接口，底层是动态类型的顺序表
linkedLIst：实现了list接口，底层为双向链表
Stack：底层是栈，栈是一种特殊的顺序表
Queue：底层是队列，队列是一种特殊的顺序表
deque：是一个接口
Set：集合，是一个接口，里面放置k模型
hashset：底层为哈希桶，查询时间复杂度为O(1)
treeset：底层是红黑树，查询的时间复杂度为O(logn)
Map：映射，里面存储的是k-v模型的键值对
hashmap：底层为哈希桶，查询时间复杂度为O(1)
treemap：底层是红黑树，查询的时间复杂度为O(logn)
算法效率分析分为两种：
1.时间效率 衡量一个算法运行速度
2.空间效率 衡量一个算法的额外空间
时间复杂度是一个函数，描述了该算法的运行时间，一个算法在执行上所消耗的时间。算法中的基本操作的执行次数，为算法的时间复杂度
5.2 大O的渐近表示法实际中计算时间复杂度，我们不一定要计算精确的执行次数，只需要大概执行次数，那么我们使用大O的渐近表示法
用于描述函数渐近行为的数学符号
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
算法的时间复杂度存在最好 最坏 平均情况
最坏情况：最大运行次数（上界）
最好情况：最小运行情况（下界）
平均情况：期望运行次数
一般情况，我们关注算法最坏运行情况
O(N)
void func2(int N){
int count = 0;
for(int k = 0;k<2*N;k++)
{
count ++;
}
int M = 10;
while((M--)>0){
count++;
}
System.out.println(count);
}
O(N+M)
void func3(int N,int M){
int count = 0;
for(int k = 0;k
O(1)
void func4(int N){
int count = 0;
for(int k = 0;k<100;k++)
count ++;}
System.out.println(count);
}
O(N^2)
int bubbleSort(int[] array){
for(int end = array.length;end>0;end--){
boolean sorted = true;
for(int i =1;iarray[i]){
Swap(array,i-1;i);
sorted = false;
}
}
if(sorted == true){
break;
}
}
}
O(N)
//计算递归的时间复杂度
long factorial(int N){
return N < 2? N:factorial(N-1)*N;
}
O(2^N)
计算斐波那契的时间复杂度
inr factorial(int N){
return N < 2? N:factorial(N-1)*factorial(N-2);
6.空间复杂度
空间复杂度是一个对算法在运行过程中临时占用存储空间大小的量度。
O(1)
int bubbleSort(int[] array){
for(int end = array.length;end>0;end--){
boolean sorted = true;
for(int i =1;iarray[i]){
Swap(array,i-1;i);
sorted = false;
}
}
if(sorted == true){
break;
}
}
}
O(N)
inr factorial(int N){
return N < 2? N:factorial(N-1)*factorial(N-2);
O(N)
java
long factorial(int N){
return N < 2? N:factorial(N-1)*N;
}
