# algorithm

**Repository Path**: ldb-gitee/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-07-08
- **Last Updated**: 2022-08-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


# 算法  

## 时间复杂度
一个算法运行时间的长短  
O(1)、O(logn)、O(n)、O(nlogn)、O(n<sup>2</sup>)等

## 空间复杂度
一个算法在运行过程中临时占用的存储空间大小  
O(1)、O(n)、O(n<sup>2</sup>)等

## 数据结构
### 线性
数组，链表
#### 数组
- 数组中的每一个元素都有自己的下标，下表从0开始，一直到数组长度-1
- 数组的元素在内存中顺序存储，每一个元素都存储在小小的内存单元中，并且元素之间紧密排列，
即不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储
  
- Python种类似数组的类型有：列表(list)和元组(tuple)
    - list是可动态扩展的，支持增删改
    - tuple是不可变的，一旦创建就不可修改
    
- 数组读取元素和更新元素的时间复杂度都是O(1)
- 数组插入和删除元素的时间复杂度都是O(n)
- 数组适合**读操作多，写操作少的场景**

#### 链表(linked list)
- 链表是一种在物理上非连续、非顺序的数据结构，由若干节点(node)组成
- **单向链表**每个节点包含两部分：data和next
- **双向链表**每个节点包含三部分：data、next和prev
- 链表适合**频繁插入、删除元素**的场景

#### 栈(Stack)
- 栈的元素只能是**先进后出(First In Last Out, FIFO)**
- 最先放入的元素在**栈底**，最后放入的元素在**栈顶**
- 栈的操作有： 
    - 入栈(push)：新元素入栈，并成为新的栈顶
    - 出栈(pop)：取出栈顶元素，栈顶元素的前一个元素作为新的栈顶
    - Python中list类型对应的方法有append(入栈)，pop(出栈)
    
#### 队列
- 队列的元素只能是**先进先出(First In First Out, FIFO)**
- 队列出的端口叫队头(front)，入的端口叫队尾(rear)
- 队列的操作有：
    - 入队(enqueue)：只允许在队尾的位置放入元素， 新元素的下一个位置将成为新的队尾（以数组最为基础数据结构）
    - 出队(dequeue)：只允许在队头一侧移除元素， 出队元素的后一个元素将成为新的队头（以数组最为基础数据结构）
    - Python中的队列：collections.dequeue、queue.Queue等
    
#### 哈希表(hash table)
- 又叫散列表，提供键(key)和值(value)的映射关系，时间复杂度接近O(1)
- 哈希表本质上也是一个数组
- 通过哈希函数将key转换成数组的下标
- 哈希冲突：不同的key通过哈希函数得到相同的下标
- 解决哈希冲突的方式：
    - 开放寻址法：比如如果对于下标的位置已被占用，则继续往后选择空位置
    - 链表法：哈希表数组的每一个元素维护成一个链表
    
- Python中对应的数据类型是**字典(dict)**

### 树
- 没有节点的树称为空树
- 有且仅有一个节点作为**根节点**
- 子树
- 父节点(parent)
- 子节点(child)
- 兄弟节点(sibling)
- 叶子节点
- 树的高度或深度：即树的最大层级
#### 二叉树(binary tree)
- 最多有2个子节点的树
- 满二叉树：一棵二叉树，每一层的节点都是满的
- 二叉树的物理存储结构：链式存储结构、数组
- 二叉查找树(binary search tree)：左子树的值均小于根节点的值，右子树的值均大于根节点的值
- 二叉查找树又叫二叉排序树(binary sort tree)，它保证了元素的有序性，通过自平衡，避免元素的单边增加
- 二叉树的遍历：深度优先遍历(前序遍历、中序遍历、后续遍历，前中后指的是根元素输出的顺序)；广度优先遍历(层序遍历)
- 二叉堆：本质上是一种完全二叉树。有两种：最大堆和最小堆
- 最大堆：任何一个父节点的值，都大于或等于它左孩子或右孩子节点的值。堆顶的是最大值。
- 最小堆：任何一个父节点的值，都小于或等于它左孩子或右孩子节点的值。堆顶的是最小值。
- 二叉堆的操作：
    - 插入节点：插入到最后，然后”上浮“
    - 删除节点：删除堆顶元素，然后用最尾元素补到堆顶，然后对其进行”下沉“
    - 创建二叉堆：让所有非叶子节点依次”下沉“
- 优先队列
    - 最大优先队列：无论入队顺序如何，都是当前最大元素出队
    - 最小优先队列：无论入队顺序如何，都是当前最小元素出队
    - 使用最大堆或最小堆来实现最大优先队列或最小优先队列
 
   
    
### 图

### 排序
- O(n<sup>2</sup>)：冒泡排序、选择排序、插入排序、希尔排序(略优于O(n<sup>2</sup>))
- O(nlogn)：快速排序、归并排序、堆排序
- O(n)：计数排序、桶排序、基数排序
- 稳定排序与不稳定排序
#### 冒泡排序
- 把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。