# Algorithm

**Repository Path**: neo5simple/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**: 2017-02-08
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法精解

作为软件工程师，只是对编程语言和开发工具熟悉是远远不够的

范畴 | 效率 | 抽象 | 重用性
---- | ---- | ---- | ------ 
数据结构|高效的组织数据方式|数据易于理解|模块化、上下文无关
算法|数据排序与查找|简化复杂问题|著名算法皆来自复杂问题的抽象

算法设计的一般方法

+ 随机法：依赖于随机数的统计特性，比如快速排序
+ 分治法：分解、求解和合并，比如归并排序
+ 动态规划：将较大问题分解成可能相关的子问题，最后在合并结果，比如递归
+ 贪心法：总在局部使用最佳选择，比如霍夫曼编码
+ 近似法：只计算足够好的解，放弃最优解，比如推销员问题

## 预备知识

### 指针操作

+ 指针基础：如何避免空指针
+ 存储空间分配
+ 数据集合与指针运算：结构和数组
+ 作为函数参数：传递引用
+ 指向指针的指针
+ 泛型指针与类型转换
+ 函数指针

### 递归

+ 基本递归：允许一个以自身越来越小的形式来定义自己的函数
+ 尾递归：递归调用在函数末尾的递归，编译器会产生优化代码

### 算法分析

+ 最坏情况分析：大多数算法的评估方式
+ O 表示法：性能上限指标
+ 计算复杂度

## 数据结构

### 链表

+ 单链表：元素由单独指针链接
+ 双向链表：元素之间通过两个指针链接
+ 循环链表：最后一个元素指针指向首元素
+ 应用：邮件、滚动列表、多项式计算、内存管理、LISP、文件链式分配、其他数据结构

### 栈和队列

+ 栈：后进先出 (LIFO) 的顺序存储和检索数据的结构，存储与检索的顺序相反
+ 队列：先进先出 (FIFO) 的顺序存储和检索数据的结构，存储于检索的顺序相同
+ 应用：信号量、事件处理、生产者 - 消费者问题、C 的函数调用

### 集合

+ 基本准则：相关联成员的无序组合，不能重复
+ 数据类型
+ 应用：数据关联、集合覆盖、集合计算、图、图算法、关系代数

### 哈希表

+ 链式哈希表：在多个桶 （可变链表，bucket) 中存储数据
+ 开地址哈希表：在表本身中存储数据，通过算法避免冲突
+ 选择哈希函数：核心问题
+ 解决冲突
+ 应用：数据库系统随机访问、符号表、数据字典、关联数组

### 树

+ 二叉树：最多只有两个子节点的树
+ 遍历算法：先序、中序、后序、层级
+ 平衡：确定结点数量尽可能降低树高的过程，便于书的搜索
+ 二叉搜索树：适合有增删改查操作的数据
+ 旋转：保持平衡的方法
+ 应用：霍夫曼编码、用户界面、数据库系统、处理表达式、人工智能、事件调度、优先级队列
+ 扩展：K 叉树、红黑树、Trie 树、B 系树

### 堆和优先队列

+ 堆：树形已排序组织，快速定位最值
+ 优先队列：堆的衍生物，便于获得最好优先级结点
+ 应用：排序、任务调度、包裹分拣、霍夫曼编码、负载均衡

### 图

+ 图：定义对象之间的关联或联系的结构
+ 搜索方法：广度优先、深度优先
+ 应用：图算法、统计网络跳数、拓扑排序、图着色、哈曼顿圈问题、分团问题、可序列化冲突

## 算法

### 排序和搜索

+ 插入排序：简单、不需额外空间，适合小数据集合
+ 快速排序：最好的排序算法，不需额外空间，适合大型数据集合
+ 归并排序：与快排性能相当，但是空间x2，而效率最好的也是超大数据集合
+ 计数排序：稳定的线性算法
+ 基数排序：逐次对元素排序的线性算法，适合固定大小的数据集合，对元素要求也多
+ 二分查找：不期望频繁插入和删除操作的有序数据集合的高效查找算法
+ 应用：次序统计、二分搜索、目录列表、数据库系统、拼写检查、电子表格
+ 相关：冒泡排序、选择排序、堆排序、内省排序、桶排序

### 数值计算

+ 多项式插值：求函数近似值
+ 最小二乘估计法
+ 方程求解：近似法
+ 应用：线性回归模型、曲线拟合、散点图、函数逼近、函数表、科学计算
+ 相关：误差估算、函数求导

### 数据压缩

+ 霍夫曼编码：基于最古老、最优雅的最小冗余编码，通过霍夫曼树实现
+ LZ77：基于字典法，通过滑动窗口和前向缓冲区对已出现的词组编码，优于霍夫曼编码
+ 应用：文件压缩、网络优化、数据库系统、在线手册
+ 相关：有损压缩、统计模型、香浓费诺编码、自适应霍夫曼编码、算数编码、LZ78

### 数据加密

+ DES: 一种对称加密算法，效率高，相对安全
+ RSA: 一种公钥加密算法，处理速度慢很多，但非常安全，适合小规模数据
+ 应用：电子货币、认证服务器、电子邮件、数字签名、电子投票、智能卡
+ 相关：找大素数、模运算、大数运算、欧几里得最大公约数算法、CFB-OFB、加密协议

### 图算法

+ 最小生成树：最小的代价将一个无方向带权图的所有顶点连接起来
+ 最短路径：连接一个方向带权图中两个顶点之间代价最小的路径
+ 旅行商问题：虚招一条遍历完整且仅一次无方向带权图中每个顶点，并返回起点的路径
+ 应用：优化管道、路由表、通信网络、闭合运输系统、有线电路板、交通监控

### 几何算法

+ 判断线段是否相交：先判断以线段为对角线的矩形是否相交，在判断线段是否跨越
+ 凸包：包含一个点集的最小凸多边形
+ 球面弧长
+ 应用：最远配对问题、地球两点距离、限制区域、密闭舱、机器人、地图制图信息系统、模拟系统