阅读 401

数据结构与算法 <一>

其他更多java基础文章:
java基础学习(目录)


这系列是根据极客时间《数据结构与算法之美》这个课程做的笔记

本篇目录

  • 复杂度分析
  • 数组
  • 链表
  • 队列

复杂度分析

最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。
最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。

平均情况时间复杂度,把每种情况发生的概率也考虑进去,全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度,及它对应的分析方法,摊还分析(或者叫平摊分析)。对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

数组

数组的查找操作时间复杂度并不是O(1)。即便是排好的数组,用二分查找,时间复杂度也是O(logn)。
正确表述:数组支持随机访问,根据下标随机访问的时间复杂度为O(1)。

低效的插入和删除

  1. 插入:从最好O(1) 最坏O(n) 平均O(n)
  2. 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。作者举例说明
  3. 删除:从最好O(1) 最坏O(n) 平均O(n)
  4. 多次删除集中在一起,提高删除效率,记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

为什么大多数编程语言中,数组要从0开始编号,而不是从1开始呢?

从偏移角度理解a[0] 0为偏移量,如果从1计数,会多出K-1。增加cpu负担。为什么循环要写成for(int i = 0;i<3;i++) 而不是for(int i = 0 ;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据,而后者2-0+1个数据,多出1个加法运算,很恼火。

链表

什么是链表?

  1. 和数组一样,链表也是一种线性表。
  2. 从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
  3. 链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。

为什么使用链表?即链表的特点

  1. 插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。
  2. 和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

常用链表:单链表、循环链表和双向链表

  1. 单链表
    • 每个节点只包含一个指针,即后继指针。
    • 单链表有两个特殊的节点,即首节点和尾节点。为什么特殊?用首节点地址表示整条链表,尾节点的后继指针指向空地址null。
    • 性能特点:插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)。
  2. 循环链表
    • 除了尾节点的后继指针指向首节点的地址外均与单链表一致。
    • 适用于存储有循环特点的数据,比如约瑟夫问题。
  3. 双向链表
    • 节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)。
    • 首节点的前驱指针prev和尾节点的后继指针均指向空地址。
    • 性能特点:和单链表相比,存储相同的数据,需要消耗更多的存储空间。插入、删除操作比单链表效率更高O(1)级别。以删除操作为例,删除操作分为2种情况:给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况,单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除,时间复杂度为O(n)。对于第二种情况,要进行删除操作必须找到前驱节点,单链表需要从头到尾进行遍历直到p->next = q,时间复杂度为O(n),而双向链表可以直接找到前驱节点,时间复杂度为O(1)。

对于一个有序链表,双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p,每一次查询时,根据要查找的值与p的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

  1. 双向循环链表:首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。

选择数组还是链表?

  1. 插入、删除和随机访问的时间复杂度
    数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
    链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。
  2. 数组缺点

1)若申请内存空间很大,比如100M,但若内存空间没有100M的连续空间时,则会申请失败,尽管内存可用空间超过100M。
2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。

  1. 链表缺点

1)内存空间消耗更大,因为需要额外的空间存储指针信息。
2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。

  1. 如何选择?

数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。如果代码对内存的使用非常苛刻,那数组就更适合。

常见的链表操作:

  1. 单链表反转 【代码】
  2. 链表中环的检测 【代码】
  3. 两个有序链表合并 【代码】
  4. 删除链表倒数第n个节点 【代码】
  5. 求链表的中间节点 【代码】
  6. 基于数组的LRU 【代码】
  7. 基于链表的LRU 【代码】
  8. 单链表判断回文串 【代码】

什么是栈?

  1. 后进者先出,先进者后出,这就是典型的“栈”结构。
  2. 从栈的操作特性来看,是一种“操作受限”的线性表,只允许在端插入和删除数据。

为什么需要栈?

  1. 栈是一种操作受限的数据结构,其操作特性用数组和链表均可实现。
  2. 但,任何数据结构都是对特定应用场景的抽象,数组和链表虽然使用起来更加灵活,但却暴露了几乎所有的操作,难免会引发错误操作的风险。
  3. 所以,当某个数据集合只涉及在某端插入和删除数据,且满足后进者先出,先进者后出的操作特性时,我们应该首选栈这种数据结构。

如何实现栈?

public class Stack {
//压栈
public void push(Item item){}
//弹栈
public Item pop(){}
//是否为空
public boolean isEmpty(){}
//栈中数据的数量
public int size(){}
//返回栈中最近添加的元素而不删除它
public Item peek(){}
}
复制代码

队列

什么是队列?

  1. 先进者先出,这就是典型的“队列”结构。
  2. 支持两个操作:入队enqueue(),放一个数据到队尾;出队dequeue(),从队头取一个元素。
  3. 所以,和栈一样,队列也是一种操作受限的线性表。

如何实现队列?

public interface Queue {
public void enqueue(T item); //入队
public T dequeue(); //出队
public int size(); //统计元素数量
public boolean isNull(); //是否为空
}
复制代码

队列实现