数据结构与算法
2021-03-29 13:21:34 0 举报
AI智能生成
登录查看完整内容
数据结构与算法
作者其他创作
大纲/内容
数据结构与算法
复杂度
直接法(效率慢)
时间复杂度:2^(n-1)-1 = O(2^n)
优化的方法
时间复杂度:O(n)
算法的好坏评判标准
正确性
可读性
健壮性(对不合理值的反应能力)
事后统计法
比较不同算法对同一组输入的执行处理时间
存在缺陷,依赖硬件及环境的不确定因素
时间、空间复杂度,稳定性
时间复杂度 time complexity
估算程序指令的执行次数(执行时间)
举例求方法的时间复杂度
1 + 1 + 4 + 4 + 4 =O(14)
if -else的判断为: 1次
i=0:1次
i < 4判断:4次
i++:4次
打印test:4次
1+n+n+n = O(n)
1 + 2n + n * (1 + 3n) =O(n^2)
1 + 2n + n * (1 + 45)=O(n)
O(logn)
1 + 2*log2(n) + log2(n) * (1 + 3n)=O(nlogn)
O(n)
常见复杂度
O(1):常数阶
O(n):线性阶
O(n^2):平方阶
O(logn):对数阶
O(nlogn):nlogn阶
O(n^3):立方阶
O(2^n):指数阶
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
空间复杂度 space complexity
估算所占用的存储空间
举例求方法的空间复杂度
O(1)
int i = 0只占用了:1个
1+1+1+n+1 =n+3=O(n)
int a = 10:1个
int b = 20:1个
int c = a + b:1个
int[] array = new int[n]:n个
int i = 0:1个
算法优化方面
尽量少用时间,少用空间
根据情况
空间换时间
时间换空间
多个数据规模:O(n+k)
相关知识
最好最坏复杂度
均摊复杂度
复杂度震荡
平均复杂度
动态数组
数据结构:计算机存储,组织数据的方式
线性结构
线性表
树形结构
二叉树
AVL树
红黑树
B树
堆
Trie
哈夫曼树
并查集
图形结构
邻接矩阵
邻接表
具有n个相同类型元素的有限序列(n>=0)
索引
首元素(首结点)
尾元素(尾结点)
前驱,后继
分类
数组
链表
栈
队列
哈希表(散列表)
一种顺序存储的线性表,所有元素的内存地址是连续的
数组的缺点:无法动态修改容量
动态数组接口设计
元素的数量:int size()
是否为空:boolean isEmty()
是否包含某个元素:boolean contains(E element)
添加元素到最后:void add(E element)
返回index位置对应的元素:E get(int index)
删除index位置对应的元素: E remove(int index)
查看元素的位置: int indexOf(E element)
清除所有元素:void clear()
简单实现
属性
数组大小:int size
所有元素:E [] elements
构造函数
有参,设置元素E的大小:(E [])new Object[capacity]
不能直接new E[],而是要使用Object,再强转
无参,设置默认容量10,(E [])new Object[10]
传入的index位置参数不在数组范围:IndexOutOfBoundsException
清空clear实现
for (int i = 0; i < size; i++) elements[i] = null; size = 0;
将对象的地址引用设置为null,此时对象无引用,垃圾回收掉对象
不可将elements=null,这样会将整个数组回收掉
添加元素add实现
elements[size++] =element
两步操作:数组的size下标赋值element,再将数组的大小size+1
需要先判断是否容量足够,不够扩容
删除下标元素remove实现
for(int i=index +1;i<=size-1;i++) elements[i-1] =elements[i]; elements[--size] = null;
三步操作:index位置后的元素全部向前移动1位,将要删除位置的元素地址设置为null,回收掉删除的对象,最后在将szie减1
在之前要判断index大小必须在size范围内,不能大于size;不允许否则下标越界if(index <0 || index >=size) IndexOutOfBoundsException
指定位置添加元素add实现
for(int i=size-1;i>=index;i--) elements[i+1] =elements[i]; elements[index] = element;size++;
index位置后的元素全部向后移动1位,在将新数据添加到数组的index位置,size+1
在之前要判断index大小必须在size范围内,允许等于size。否则下标越界if(index <0 || index >size) IndexOutOfBoundsException
扩容
private void ensureCapacity(int capacity){\tint oldCapacity = elemens.length;\tif( oldCapacity >= capacity) return\t//新容量为旧容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity>>1); E [] newElements = (E [])new Object[newCapacity]; for(int i=0;i<size;i++) newElements[i] =elements[i]; elements = newElements; }
可以使用jdk内置方法复制快
源数组 = Arrays.copyOf(源数组,扩容之后的长度)
数组泛型 MyList<E>
对象数组
obj指向了堆内存中的数组,数组中每个存储的是地址,每个地址指向的是一个对象,当某个地址为null时,它原来所对应的对象就将被回收
检验对象是否被回收
在对象类中重写finalize方法在打印便于观察:super.finalize(); System.out.println(\"sss\")
通知jvm进行回收:System.gc()
动态数组中需要改动的
clear
elements[i] = null;
remove
elements[--size] = null;
查看元素下的索引indexOf实现
if (element == null) { for (int i = size-1; i >= 0; i--) if (elements[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (element .equals(elements[i])) return i; }
两个问题
equals
这里不能使用 ==,如果是对象数组比较的是地址,equals是比较对象是否相等,默认对象的equals方法就是。也可以重写对象的equals方法:例如Person中如果以年龄相等为相等:
@Override public boolean equals(Object obj) { Persion persion = (Persion) obj; return this.age == persion.age; }
null值处理
是否允许添加null元素?
默认允许
如果不允许,在add方法前添加非空判断
if(element==null) return
下标查询为null元素
如果为null,找到为null的第一个元素下标
链表LinkedList
简介
明显的缺点
可能造成内存空间大量浪费
链表是一种链式存储的线性表,所有元素的内存地址不一定是连续的
链表设计
LinkedList<E>
size
first(Node<E>)
指向下一个Node
Node<E>
element(Node<E>)
next
指向下一个Node,最后一个Node指向null
链表的接口与动态数组一样
实现与动态数组一样的接口,抽离出来AbstractList
protected int size;
size方法实现
return size;
isEmty方法实现
size==0
contains方法实现
indexOf(element) != -1
add添加实现
其他接口具体实现
清除clear实现
size=0; first =null
需要将next设置为null吗?
不需要,在first为null之后,链表指向下一个的Node无关联了,会回收,这样依次将被回收Node到结束
可以在Node对象中实现finalize方法打印,使用System.gc()方式进行验证
添加add实现
获取index位置节点
/** * 获取index位置节点 * @param index * @return */ private Node<E> node(int index){ //检验index是否超出size范围 Node<E> node = first; for(int i=0;i<index;i++){ node =node.next; } return node; }
获取位置元素get实现
node(index).element
设置位置元素set实现
Node<E> node = node(index); E oldElement = node.element; node.element =element;
刪除remove实现
Node<E> node = first; if(index == 0){ first = first.next; }else{ Node<E> prev = node(index - 1); node = prev.next; prev.next = node.next; } size--;
要先判断index范围
查询元素的第一个下标indexOf实现
Node<E> node = first; if (element == null) { for (int i = size-1; i >= 0; i--) { if (node.element == null) return i; node = node.next; } } else { for (int i = size-1; i >= 0; i--) { if (element.equals(node.element)) return i; node = node.next; } }
打印toString
数据结构和算法动态可视化网站
https://visualgo.net/zh
练习
节点删除
删除链表中的节点
只提供了节点,要删除它
解法:获取此节点的下一个节点数据,将此节点的所有数据替换为下一个节点的数据
node.val = node.next.val; node.next = node.next.next;
反转一个链表
反转链表
递归
迭代
环形链表
快慢指针思想
启动两个指针:快指针fast,慢指针slow,快指针走两步,慢指针走一步。如果有环,那么在后面一定会相遇。能指向同一个指针。
移除链表元素
删除排序链表中的重复元素
链表中的中间节点
虚拟头结点
在最前面加一个虚拟头结点(不存储数据)first与第一个Node结点之间增加一个虚拟结点:包含null与next
实现的改变
添加无参构造函数
获取index位置节点方法node以及toString中
Node<E> node = first.next
去掉index == 0的情况,修改为: Node<E> prev = index ==0?first:node(index - 1);
复杂度分析
动态数组ArrayList
get/set
add/remove
最好复杂度:O(1)
最坏复杂度:O(n)
平均复杂度:O(n)
get/set/add/remove
平时说的add、remove、set的复杂度为O(1)是指插入的那一刻操作加入到结点,不像动态数组,插入点后的数据都要挪动
最后位添加add
这种情况是在扩容时发生
平均复杂度:O(1)
均摊复杂度:O(1)
后面扩容的均摊到前面add中,相当于每次add操作次数是2,也就是O(1)复杂度
什么情况下适合使用均摊复杂度?
经过连续的多次复杂度比较低的情况后,出现个别复杂度比较高的情况。多数均摊复杂度就是最好复杂度
动态数组缩容
如果内存比较紧张,动态数组有比较多的剩余空间,可以考虑缩容操作
比如剩余空间占总容量的一半时,就进行缩容缩容用于删除方法中,在最后添加这个方法trim();
private void trim() { int capacity = elements.length; int newCapacity = capacity >> 1; if (size >= (newCapacity >> 1) || capacity <= 10) return; //剩余空间很多,进行缩容 E[] newElements = (E[])new Object[newCapacity]; for(int i =0;i<size;i++){ newElements[i] = elements[i]; } elements =newElements; }
如果扩容倍数与缩容时机不得当,有可能导致复杂度震荡
举例
如果扩容按2倍,缩容为一半。当动态数组刚好在扩容点添加元素,此时复杂度为O(n),如果在之后删除最后这个元素,此时满足缩容条件,此时复杂度为O(n)。如果这个动态数组按照这样反复操作。此时它的复杂度就为O(n)。这就是复杂度震荡
避免方式
扩容与缩容相乘最好不要等于1
双向链表
子主题
单向循环链表
双向循环链表
静态链表
没有指针下如何实现链表
通过数组模拟链表,就称为静态链表
实现
数组的每个元素存放2个数据:值,下个元素的索引。数组0位置存放的是头结点信息,最后一个结点的索引可以存-1,表示结束
如果数组每个元素只能存放1个数据呢?
就使用2个数组,1个数组存放所有关系,1个数组存放值
0 条评论
回复 删除
下一页