# beauty-algorithm

**Repository Path**: varcha/beauty

## Basic Information

- **Project Name**: beauty-algorithm
- **Description**: 王铮 数据结构与算法之美 学习笔记。
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: https://time.geekbang.org/column/intro/126
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-08-31
- **Last Updated**: 2021-09-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构与算法之美

[数据结构与算法之美_算法实战_算法面试-极客时间 (geekbang.org)](https://time.geekbang.org/column/intro/126)

由来、特性、适用场景和能解决的问题。

## Q_sqrt

$$
$f(x)=\frac{1}{x^{2}}-x$
$f^{\prime}(x)=\left.f^{\prime}(y)\right|_{y=x}=-\frac{2}{y^{3}}=-\frac{2}{x^{3}}$
$x_{\text {new }}=x-\frac{f(x)}{f^{\prime}(x)}=x-\frac{\frac{1}{x^{2}}-x}{-\frac{2}{x^{3}}}=\frac{3}{2} x-\frac{1}{2} x^{4}$
$$



## 复杂度分析

1. 性能基准测试：事后统计法； 运行在具体硬件、数据集 现实中的算法执行效率。

2. O分析法： 提供理论分析模型，与硬件平台无关，与数据随机性无关，避免数据规模导致异常情况

#### 时间复杂度

1. 渐进时间复杂度 asymptotic time complexity： 算法执行效率与数据增大规模之间的趋势。
   
   1. 只关注循环次数最多的一段； 加法法则取最大；乘法法则取乘积

2. 复杂度量级
   
   1. 执行时间不随n变化即为 O(1)。
   
   2. O(logn) 不同对数底数之间可以互相转换。
   
   3. O(m+n)：复杂度由两个数据的规则所决定

#### 空间复杂度

1. 渐进空间复杂度：相比原数据额外的内存消耗（除了原本数据存储空间，算法引入的新空间）。

2. 常见： O(1), O(n), O(n^2)

#### 特殊情况时间复杂度

1. 最好，最坏情况

2. 平均情况 / 期望 / 加权平均 时间复杂度： 同一代码在特殊情况下，时间复杂度有量级差距，才会使用以区分。

3. 均摊时间复杂度： 复杂度呈现周期变化，计算一个周期内的平均操作复杂度（**摊还分析法**），一般**均摊==最好**

## 常见数据结构

#### 数组

1. 连续内存，数组支持根据下标的随机访问。
   
   - a[k]_address = base_address + k * type_size; 

2. “插入&删除”： 低效？O(n)
   
   1. 无序插入，替换插入O(1)
   
   2. 标记数据，统一删除。

3. 数组越界，C未决行为，访问非法地址。

4. java arraylist容器：封装细节，动态扩容(✖️1.5) （内存申请，数据搬运）
   
   - 无法存储基本数据类型，需要封装为Integer，Long类

#### 链表

1. LRU缓存淘汰算法： 
   
   - 缓存即空间换时间思想；对于消耗内存程序，通过用时间换空间优化。
   1. 获得新数据，遍历链表，若有该数据，则从原位置移到头节点
   
   2. 没有找到，则1⃣️若缓存未满，插入头节点；2⃣️若已经满了，删除尾节点，插入头节点。

2. 单向链表；双向链表（LinkedHashMap）：用空间换时间；双向循环链表。
   
   1. 天然支持动态扩容；
   
   2. 频繁插入/删除：产生内存碎片，java会触发频繁Garbage Collection
   
   3. 单向链表，快慢指针，获取中位数。q.next != null && q.next.next != null;

3. 链表代码技巧：

   1. 理解指针/引用含义：。

   2. 警惕内存丢失 和 内存泄漏：c语言手动释放内存空间。

   3. 使用哨兵 sentinel：数组查找，最后一位作为哨兵，省略i<n的n次比较；
      
      ```java
      sentinel = a[n-1];  
      if( key==snetinel ) 
        	return n-1;
      while( key!=a[i] ) i++;
      a[n-1] = semtinel;
      if( i==n-1 ) return -1;
      return i;
      ```
      
   4. 留意边界条件处理：链表为null，1，2，头尾节点 时候，是否可以正常工作？； 注意边界，健壮代码。
   
   5. 举例画图：正常例子，边界例子

4. 常用5个链表操作：

   + 单链表反转，链表中环检测，两个有序链表合并，删除链表中倒数第n个，求链表中间节点。
   + leetcode对应：206，141，21，19，876

#### 栈

1. 实现栈：数组-顺序栈，链表栈
2. 函数调用栈
3. 表达式求值
4. JVM内存空间：代码区，静态数据区，动态数据区（堆、栈）
   1. 代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
   2. 静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
   3. 栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
   4. 堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
5. 栈，函数调用，作用域？
6. leetcode：20， 155， 232， 844， 224， 682， 496

#### 队列

1. 循环队列：

   ```java
   tail = (tail+1)%n;
   head = (head+1)%n;
   (tail + 1)%n == head;  // full queue
   tail == head;  // empty
   ```

2. 阻塞队列：生产者-消费者队列； 有限资源池（线程池）排队请求;

3. 并发队列（线程安全队列）：入列/出列方法加🔒，锁粒度大并发度低；数组循环队列，CAS原子操作 - disrupter；Linux环形缓存； java concurrent 并发包 ArrayBlockQueue 公平锁

## 递归

1. 堆栈溢出：限制递归调用最大深度，

2. 重复计算：散列表存储

   ```java
   hasSolvedList.put(n, value);
   hasSolvedList.contain(n);
   value = hasSolvedList.get(n);
   ```

3. 空间复杂度：额外的空间开销

## 排序

1. 排序算法执行效率：最好情况，最坏情况，平均情况 时间复杂度； 考虑时间复杂度的系数、常数、低阶； 比较次数，交换（移动）次数。
2. 内存消耗：原地排序（空间复杂度O(1) ）。
3. 稳定性：序列中值相等元素，排序之后顺序不变。
4. 有序度：具有有序关系的元素对的对数；完全有序时候为满有序度 $C_n^2=\dfrac{n(n-1)}{2}$​ ，逆序度为满有序度减去有序度，即为为达到有序序列而需要比较和交换的次数。

#### 冒泡排序

#### 插入排序

1. 动态的像有序序列中插入数据，

#### 归并排序

1. 分枝算法思想 ——> 递归实现
2. 归并函数递推公式， merge() 公式
3. 时间复杂度计算：O(nlogn)
4. 空间复杂度：非原地排序算法，合并数组需要额外存储空间。O(n)

#### 快速排序

1. Partition() 分区函数 
2. pivot 三分查找法
3. C++ qsort函数：小数据量归并排序，大数据快速排序，递归到长度为4时候 插入排序。

排序时间：

![image-20210831220015098](README.assets/image-20210831220015098.png)

> 插入排序 查找算法调用二分查找。

![image-20210902142224885](README.assets/image-20210902142224885.png)

![image-20210831225424499](README.assets/image-20210831225424499.png)

#### 二分查找

1. 有序数据集合的查找算法：
2. 时间复杂度：O(logn) ——> 堆，二叉树 的操作时间复杂度也是 O(logn)
3. 应用局限性：
   - 依赖顺序表结构（数组）
   - 针对有序数组
   - 数据量太小不适合二分查找；如果数据比对非常耗时，则优先二分查找。
   - 数据量太不也不适合，数组存储需要连续的内存空间
4. IP 定位对应省份地址。
5. 二分查找变形问题：
   - 有序集合，重复数据，查找第一个等于给定值的元素；
   - 查找最后一个等于给定值的元素。
   - 查找第一个 大于等于给定值 的元素
   - 查找最后一个 小于等于给定值 的元素
6. 散列表、二分查找树 ——> 二分查找 相比这些内存上更有优势。
7. 一般用于查找 “近似” 问题。
8. leetcode：33 循环有序数组如何实现二分查找？

## 跳表

1. 支持二分查找的链表结构 ——> redis有序集合实现方式，对比 **红黑树**
2. 索引层 down指针。

![IMG_0730(1)](README.assets/IMG_0730(1).JPG)

3. 跳表索引动态更新：随机函数。
4. Redis有序集合支持核心操作：插入、删除、查找、区间查找、迭代输出
   - 对比红黑树：区间查找效率更高；代码实现更容易、灵活。
5. [Redis源码学习之跳表](https://cloud.tencent.com/developer/article/1353762)

## 散列表 Hash Table

1. 散列函数 Hasp function：得到非负整数，不同key对应hash值不同，相同key对应hash值相同。
2. 散列冲突无法避免：
   - 开放寻址法 open addressing：删除标记为deleted
     - 线性探测 Linear Probing（每次探测步长为1），二次探测 Quadratic probing（探测步长为探测次数平方），双重散列 Double hashing（多个hash函数）
     - 装载因子 load factor
   - 链表法 chaining
3. 散列函数设计：散列表碰撞攻击。
   1. 数据分析法，如英语单词每个字母ASCII进位相加，在对跟散列表大小求余、取模。
   2. 直接寻址法，平方取中法，折叠法，随机数法。
4. 装载因子变化：动态扩容、缩容。
   - 避免一次性扩容导致某次操作耗时过多，将老数据搬入新散列表过程 “均摊” 到每一次新的数据插入操作中，在查询时候，先查找新散列表，无法找到再查找旧散列表。
5.  LinkedHashMap链表法，ThreadLocalMap 开放寻址法。
   - 开放寻址法：有效利用CPU缓存加快查询速度；**序列化**容易；需要装载因子低，大对象大数据量时候浪费空间多。
   - 链表法：大装载因子容忍度高；不适合小对象小数量，零星分布在内存中，查询费时。
   - 链表法改造：使用跳表、红黑树等数据结构代替链表，即便 散列表碰撞攻击，查询/插入速度也只会从从 O(1) 退化为 O(logn)。
6. java HashMap：
   - 初始大小16，最大装在因子 0.75，超过扩容2倍。
   - 链表法，当链表长度 大于8，转换为 **红黑树**。
7. 工业级的散列表、散列函数：
   - 快速的插入、查询、删除操作
   - 内存占用合理 —————> 定义装载因子，设计动态扩容策略
   - 性能稳定，极端情况下性能退化不会过分 —————> 合适的散列冲突解决办法
8. 使用散列表维护一个本身有序的双向链表，如按照 score 排序的链表，按照key值放入散列表。 next，front，hnext。
9. 按照访问时间排序的 LinkedHaspMap 即 支持LRU缓存淘汰策略的缓存系统。
   - Linked 表示 双向链表。

### 哈希算法

1. MD5，SHA算法
2. 原理：将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规则即为hash算法。
   - 不能反推原始数据
   - 敏感，即使更改1bit也会引起改变。
   - 散列冲突小，不同原始数据hash值相同概率很小。
   - 执行效率高，长文本也可以迅速计算出哈希值。
3. MD5：128bit长度
4. 应用场景：安全加密，唯一标识，散列函数，负载均衡，数据切片，分布式存储。

##### 安全加密

1. MD5 Message-Digest Algorithm，SHA Secure Hash Algorithm，DES Data Encryption Standard，AES Advanced Encryption Standard。
2. 组合数学：鸽巢原理。128位的 MD5 当又 2^128+1个对象进行计算时，必然会产生相同哈希值。
3. 针对**字典攻击**，可以引入 **盐salt** 将用户密码绑定，然后使用hash算法进行加密。

##### 数据校验

1. P2P协议，

##### 散列函数

相比hash算法，对散列重推、反向解密关心不大，追求执行效率，安全可靠。

##### 负载均衡

1. 负载均衡算法：会话粘滞session sticky，轮询，随机，加权轮询。
2. 客户端IP地址或者会话ID计算hash，与服务器列表大小取模运算，得到服务器编号。

##### 数据分片

1. “关键词” 次数：搜索日志体积巨大：将数据文件分片用N台机器同步处理，MapReduce

##### 图片重复查询

1. 图片hash取模分配到对应及其存储，hash 128bit 16字节，文件路径 256字节，指针8字节，共152字节存储一个映射索引。

##### 分布式存储

1. 改变服务器数量，所有数据的hash重新取模搬移到新服务器，缓存失效 --> 穿透缓存，甚至 雪崩效应，压跨数据库。
2. 一致性hash 算法：虚拟环，虚拟节点。CRC校验，git commit
   - [一致性哈希算法 consistent hashing-朱双印博客 (zsythink.net)](https://www.zsythink.net/archives/1182)



### 二叉树

1. 二叉树存储方式，什么二叉树适合数组？
2. 无父节点：根节点；无子节点：叶子节点。
   - 高度height：节点到叶子最长路径（边长）
   - 深度 depth：根节点到此节点经过边的个数
   - 层 level：节点深度 + 1
   - 树的高度 = 根节点高度
3. 满二叉树； 最后一层节点靠左，上面的层是满二叉树：完全二叉树。
4. 二叉链式存储法；
5. 数组顺序存储法：跟节点 i，左子节点 2 * i 位置，右子节点 2 * i + 1 位置。
   - 完全二叉树可以存满数组，非完全二叉树会浪费较多数组空间
6. 堆：完全二叉树，存储方式为数组。
##### 遍历
1. 前序、中序、后序遍历：指遍历时 此节点与其左、右子节点之间的相对顺序（左永远在右前）。
2. 时间复杂度：O(n)
3. 给定 n 个数，简历二叉树数目为 **卡特兰数**，建立完全二叉树数目为 n！（完全二叉树转化为数组，排列组合） 。
4. 二叉树的层次遍历，借助queue，O(n)空间复杂度，

##### 二叉查找数

1. 又称 ”二叉搜索树" ：动态数据集合的快速插入、删除操作：对比散列表
2. 左子树大于，右子树小于。
3. 删除：无子节点；只有一边子节点；有两个节点（寻找右子树中的最小节点，剪切到当前节点）；或者将要删除的节点打标记
4. 快速查找最大/最小节点，前驱/后继结点。
5. 中序遍历，得到有序数据序列。
6. 支持重复数据（键值key）的二叉查找树：
   - 链表，动态扩容数组存储在同一个位置
   - 相同key节点放在右子树
7. 时间复杂度分析：
   - 节点配置不平衡：退化为链表；理想配置：完全二叉树； 时间复杂度与树height成正比，height <= log2n
   - 平衡二叉查找树：高度接近logN，时间复杂度 O(logn)
8. 对比散列表：
   - 有序存储 vs 无需存储；散列表扩容耗时，散列冲突时性能不稳定；
   - 散列表查找时间是常量级别，但是因为散列冲突，不一定小于 logN；
   - 散列表设计复杂；散列表装载因子，浪费存储空间

##### 平衡二叉查找树-红黑树

1. balanced tree （B-tree）任何节点左右子树高度相差<=1，AVL数 --> 严格定义的平衡二叉查找数（为了维持高度平衡需要频繁操作）。其他平衡二叉：伸展树 Treap，树堆（无法避免极端情况下性能退化）；红黑树维持平衡代价较低，也不会在极端情况下退化。
2. 解决普通普通二叉树在频繁的插入删除操作中，出现的时间复杂度退化为 O(n) 问题。----> 只要树的高度不必 logn 大很多（仍是对数量级），即便不符合严格定义平衡二叉树，仍是一个 合格的平衡二叉树 ---->  红黑树。
3. 红黑树：①根节点黑色；②叶子黑色；③相邻节点不能全红；④从该节点到达叶子节点的所有路径，包含相同数目黑色节点。
   - 插入、删除操作过程中，会破坏3、4两点，需要通过
4. 红黑树高度分析：去掉红色节点，黑色节点组成完成二叉树（高度近似 logn），红黑树高度近似 2*logn
5. 动态数据结构。
6. 2-3-tree:
   - 从底向上长。
7. 实现：红黑树插入节点必须红色，新插入节点是叶子节点：左右旋转和改变颜色。
   - 关注节点
8. case1：

##### 逆序树计算时间复杂度

1. 归并排序，快速排序
2. 斐波那契数列
3. 全排列问题

##### 前缀树 Trie

1. 每个节点属性：children 数组或集合，罗列当前分支包含的所有字符
2. isEnd：boolean，判断该节点是否为某字符串结尾
3. 根节点为空。除了根节点，其余所有节点都可能是结尾，叶子节点一定是结尾。
4. 212： 单词搜索。

##### 线段树

1. 频繁对数组进行如下操作：更新数组元素数值；求数组内任意一段区间内元素的总和（或平均值）

2. 元素都存储子节点，父节点保存子节点之和。

##### 树状数组 Binary Indexed Tree

1. 频繁更新节点值；求前K个元素综合（或平均值）：O(logN)
2. 多叉树
3.