首页  思维导图  详情

数据结构与算法

2021-03-29 13:21:34   0  举报





AI智能生成

数据结构与算法

算法

数据结构图

作者其他创作

大纲/内容

复杂度

斐波那契数(0,1,1,2,3,5,8......)

直接法(效率慢)

时间复杂度：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表示，忽略常熟，系数，低阶。例如：9 >>O(1), n^2+2n+5 >>O(n^2)

常见复杂度

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 set(int index,E element)

往index位置添加元素：void add(int index,E element)

删除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){
int oldCapacity = elemens.length;
if( oldCapacity >= capacity) return
//新容量为旧容量的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内置方法复制快

System.arraycopy(源数组,源数组中的起始下标,目标数组,存放的起始下标,复制的元素的个数)

源数组与目标数组可以一样，此时源数组就被扩容了

源数组 = Arrays.copyOf(源数组，扩容之后的长度)

数组泛型 MyList<E>

对象数组

Object[] obj = new Object[7],如果此时它在方法中，当方法运行完了之后，栈空间定义的变量Object [] obj会被销毁，
此时垃圾回收器查看堆空间中的new Object[7]对象是否有引用，如果没有，垃圾收集器会自动回收掉

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>)

指向下一个Node，最后一个Node指向null

有参构造器,两个参数

链表的接口与动态数组一样

实现与动态数组一样的接口，抽离出来AbstractList

protected int size;

size方法实现

return size;

isEmty方法实现

size==0

contains方法实现

indexOf(element) != -1

add添加实现

add(size,element);

其他接口具体实现

清除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;

if(index == 0){
first = new Node<>(element, first);
}else{
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;

刪除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

实现的改变

添加无参构造函数

public LinkedList() {
first = new Node(null,null);
}

获取index位置节点方法node以及toString中

Node<E> node = first.next

add,remove方法修改

去掉index == 0的情况，修改为：
Node<E> prev = index ==0?first:node(index - 1);

复杂度分析

动态数组ArrayList

get/set

O(1)

add/remove

最好复杂度：O(1)

最坏复杂度：O(n)

平均复杂度：O(n)

链表LinkedList

get/set/add/remove

最好复杂度：O(1)

最坏复杂度：O(n)

平均复杂度：O(n)

平时说的add、remove、set的复杂度为O(1)是指插入的那一刻操作加入到结点，
不像动态数组，插入点后的数据都要挪动

均摊复杂度

动态数组ArrayList

最后位添加add

最好复杂度：O(1)

最坏复杂度：O(n)

这种情况是在扩容时发生

平均复杂度：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

双向链表

子主题

单向循环链表

双向循环链表

静态链表

所学的链表是依赖指针(引用)实现的，有些编程语言没有指针。比如早期的BASIC,FORTRAN语言。