目录
一.数据结构
1. 什么是数据结构
2. 如何学好数据结构
二.集合框架
三.算法效率 (时间复杂度和空间复杂度)
1. 时间复杂度
2. 空间复杂度
一.数据结构
1. 什么是数据结构
数据结构(Data Structure)是计算机储存,组织数据的方式, 指相互之间存在一种或多种特定关系的数据元素的集合. 数据结构是一门单独的学科,和语言没有关系 (用C / C++ / Java 等语言均可实现). 数据结构 = 数据 + 结构. 数据结构和数据库的关系是: 数据库的背后,需要数据结构来支持.
2. 如何学好数据结构
数据结构十分抽象,有时必须结合图形来思考.所以想要学好数据结构,我们需要: 多画图,多思考,多写练习(写代码 / 刷题).
二.集合框架
Java集合框架(Java Collection Framework) , 又被称为容器(Container) , 是定义在java.util包下的一组接口及其实现类. 其主要作用表现为将多个元素置于一个单元中,对这些元素进行快速,便捷的"增删查改".
三.算法效率 (时间复杂度和空间复杂度)
1. 时间复杂度
时间复杂度(又称时间效率), 主要衡量的是一个算法的运行速度.一般用算法中基本操作的执行次数来表示.
实际中我们计算时间复杂度时, 并不需要计算精确的执行次数, 而只需要一个大概的数字.所以这里我们可以使用大O的渐进表示法.(大O渐进法去掉了那些对结果影响不大的项, 简洁地表示出了一个算法大概的执行次数).
推导大O阶的方法:
(1) 用常数1取代所有加法常数.
(2) 在经过(1)步骤修改后的表达式中, 只保留最高阶项.
(3) 若最高阶项不是1, 则去掉最高阶项的常系数, 得到的结果就是大O阶. (若最高阶项为1, 则时间复杂度就是1).
代码示例:
public class test {
void func(int N){
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
count++; //N*N 次
}
}
for (int k = 0; k < 2*N; k++) {
count++; //2N次
}
int M = 10;
while ((M--) > 0) {
count ++; //10次
}
}
}
上述代码基本操作执行次数为: + 2N + 10;
按推导大O阶的方法来计算:
(1) + 2N + 1
(2)
(3)
所以此代码的时间复杂度为: O()
2. 空间复杂度
空间复杂度, 主要衡量的是一个算法所需要占用的空间. 一般用算法中变量的个数来表示.
我们在计算空间复杂度时, 同样可以用大O渐进法来大概表示.
代码示例:
public class test {
void bubbleSort(int[] array){
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if(array[i-1] > array[i]) {
//...
}
}
}
}
}
冒泡排序, 仅创建了一个数组, 在内存上开辟了一块空间. 所以此算法的空间复杂度为O(1).
public class test {
long fac(int N) {
return N < 2 ? N : fac(N - 1)*N;
}
}
递归求阶乘, 递归调用了N次,开辟了N个栈帧. 所以此算法的空间复杂度为O(N) .
那么,以上就是本篇博客的全部内容啦,如果喜欢小编的文章,可以点赞,评论,收藏~