算法与数据结构.md

算法

概念

• 逻辑结构
  • 线性结构：顺序表、栈、队列
  • 非线性结构：树、图
• 物理结构
  • 顺序存储结构：数组
  • 链式存储结构：链表

什么是算法

在计算机领域里，算法是一系列程序执行，用于处理特定的运算和逻辑问题。

衡量算法优劣的主要表示标准是时间复杂度和空间复杂度

什么是数据结构

数据结构是数据的组织、管理和存格式，其使用目的是为了搞笑低访问和修改数据。

数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构

时间复杂度

是对一个算法运行时间长短的量度，用大O表示，记作 T(n) = O(f(n))

常见4种执行方式

1. 执行次数是线性的，时间复杂度：O(n)
2. 执行次数是对数的，时间复杂度：O($logn$)
3. 执行次数是常量，时间复杂度：O(1)
4. 执行次数是多项式计算，时间复杂度：O($n^2$)

时间排序（从小到大）

O(1) < O(${log{n}}$) < O(n) < O ($n^2$)

空间复杂度

是对一个算法在运行过程中临时占用存储空间大小的量度，用大O表示，记作S(n) = O(f(n))。

常见空间复杂度几种情形：

1. 常量空间 O(1)

   当算法的存储空间大小固定，和输入规模没有直接的关系时，空间负责度记O(1)

2. 线性空间 O(n)

   当算法分配的存储空间是一个线性的集合（如数组），并且集合大小和输入规模n成正比时，空间负责度记O(n)

3. 二维空间 O( $n^2$ )

   当算法分配的空间是一个二位数组集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度即O( $n^2$ )

4. 递归空间 O(n)

   递归时计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。

   “方法调用栈”包括进栈和出栈两个行为，如：

   void fun4(int n){
     if(n<=1){
       return;
     }
     fun4(n-1);
     ...
   }

   当持续调用fun4方法会执行入栈操作，当入参n=1时执行出栈操作

   执行递归操作所需要的内存空间和递归的深度成正比，即空间复杂度是线性的，如果递归的深度是n，那么空间复杂度就是O(n)

数据结构

数组（array)

基本操作

特点：在内存中顺序存储

1. 读取元素

   随机读取即可，T(n)=O(1)

2. 更新元素

   下标更新即可，T(n)=O(1)

3. 插入元素

   3种情况

   尾部插入：

   直接插入即可等同于更新元素 T(n) = O(1)
   

   中间插入：

   需要挪动插入位置后元素向后移动，腾出地方 T(n)=O(n)
   

   超范围插入

   需要扩容，创建一个新数组，长度是旧数组的2倍，在把旧数组中元素统统赋值过去，T(n) = O(n)
   

4. 删除元素

   如果删除的元素位于数组中间，其后的元素需要向前挪动1位，T(n) = O(n)

优势和劣势

优势

• 非常高效的随机访问能力，有一个搞笑查找元素的算法二分查找就是用的数组优势

劣势

• 插入、删除元素会导致大量元素被迫移动，影响效率

总结

适合读操作多，写操作少

链表（linked list)

是一种在屋里上非连续、非顺序的数据结构，有若干节点（node）所组成

单向链表

一部分是存放数据的变量data，另一部分是指向下一个节点的指针next

private static class Node{
  int data;
  Node next;
}

链表的第一个节点叫头节点，最有一个节点叫尾结点，尾结点的next指针指向null

双向链表

private static class Node{
  int data; //存储的数据
  Node prev; //前一节点地址，头节点指向链表的最后节点地址
  Node next; //下一节点地址
}

存储方式

在内存中是随机存储，分布在内存的不同位置，依靠next指针关联起来，可以灵活的利用零散的碎片空间

基本操作

1. 查找节点

   1）将查找的指针定位到头节点
   2）根据头节点的next指针，定位到第2个节点
   3）依次类推，知道查找到第n个节点

   最坏的T(n) = O(n)

2. 更新节点

   找到更新节点，直接旧数据替换成新数据即可

3. 插入节点

   尾部插入

   把最后一个节点的next指向新插入的节点即可
   

   头部插入

   1）把新节点的next指针指向原先的头节点
   2）把新节点变为链表的头节点
   

   中间插入

   1)新节点的next指针，指向插入位置的节点
   2）插入位置前置节点的next指针指向新节点
   

   T(n) = O(1)

4. 删除元素

   尾部删除

   把倒数第2个节点next指针指向空即可
   

   头部删除

   把链表的头节点设为原先头节点的next指针即可
   

   中间删除

   把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可
   

   删除元素时间复杂度T(n) = O(1)

代码位置

TODO

数组VS链表

时间复杂度相比

	查找	更新	插入	删除
数组	O(1)	O(1)	O(n)	O(n)
链表	O(n)	O(1)	O(1)	O(1)

数组优势在快速定位元素，针对读多，写少场景

链表优势在灵活插入和删除，针对频繁插入、删除元素场景

栈和队列

这两者都属于逻辑结构，他们的物理实现既可以利用数组，也可以利用链表来完成。

栈(stack)

一种线性结构，先入后出（First In Last Out 简称FILO)。最早计入的元素存放的位置叫作栈底(bottom)，最后进入的元素存放的位置叫作栈顶（top)。

基本操作

• 入栈操作(push) T(n) = O(1)

  把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶

• 出栈操作(pop) T(n) = O(1)

  把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶

队列（queue)

FIFO。度列的出口端叫作队头(front)，入口段叫作队尾(rear)

基本操作

• 入队(enqueue) T(n) = O(1)

  只允许在队尾放入元素，新元素的下一个位置会成为新的队尾

• 出队(dequeue) T(n) = O(1)

  只允许在队头一侧移除元素，出队元素的最后一个元素将会成为新的队头

循环队列（百度一下）

(队尾下标+1) % 数组长度 = 队头下标，代表队列满了

栈和队列的应用场景

• 栈：输出顺序和输入顺序相反
  • 历史的回溯，例如实现递归逻辑
  • 面包屑导航，浏览页面时可轻松回溯到上一级或更上一级页面
• 队列：输出顺河和输入顺序相同
  • 对历史的回访，照历史书序，把历史重演一遍，例如多线程中，争夺公平锁的等待队列，顺序就是按照队列中排序的
  • 网络爬虫，待转区网站URL存入队列，再按照有序队列的顺序来一次抓取和解析
• 双端队列：综合栈和队列的有点，从队头一端可以入队和出队，从队一端也可以入队和出队
• 优先队列：按照优先级最高，谁先出队（需了解二叉堆）

散列表(哈希表 hash table)

提供了**键(key)和值(value)**的映射关系，查找时间复杂度接近O(1)

二叉树

Btree

Btree+

红黑树

...

常用算法

常用算法

一致性哈希

https://zhuanlan.zhihu.com/p/34985026