算法学习 Golang 版 - 探索算法始末

• 认识
• 算法
• 结构
• 数学原理
• 其他常见问题

认识

1.数学研究最抽象的数与结构的量、量变及其关系，算法用它与逻辑来发现从具象的问题空间到解空间的逻辑映射。算法的思想就来自于数学、逻辑及求解的工具、方法与规律中。

2.算法本身与程序无关（更与编程语言无关），程序代码是算法的一种表示方式。

3.算法通过数据结构来封装数据及对数据的操作，并基于数据结构来实现算法过程（最简单例子就是算法过程中操作数组-别拿数组不当数据结构！）。有时数据结构本身的性质也能用于设计算法，如最大堆用于堆排序。

4.算法是基于问题的，每种算法有它自己的问题背景。但是有时一种算法的思想能借鉴应用到另一个问题的解决方式中。算法的设计过程即是一个如何解题的过程。

算法

按问题目标的类型划分

• 排序

  • 插入排序

    • 直接插入排序(Insert Sort) O(n^2)
    • 折半插入排序(Binary Insert Sort)
    • 希尔排序(Shell Sort)

  • 交换排序

    • 冒泡排序(Bubble Sort) O(n^2)
    • 快速排序(Quick Sort)?? O(nlogn)

  • 选择排序

    • 直接选择排序(Select Sort) O(n^2)
    • 锦标赛排序(Tournament Sort) O(nlogn)
    • 堆排序(Heap Sort) O(nlogn)

  • 归并排序(Merge Sort) O(nlogn)

  • 基数排序(Radix Sort) O(d(n+radix))

  • 桶排序(Bucket Sort) O(nlogn)

• 查找/搜索

  • 二分查找(Binary Search)

  • 树型

    • 二叉搜索树(Binary Search Tree)
    • 平衡搜索树(AVL Tree)
    • 并查集(Union-Find Set)

  • 哈希(Hashing)

  • 最优化剪枝

  • 可行性剪枝

  • 记忆化搜索

  • 枚举搜索(Enumeration)

  • 深度优先(Depth First Search)

  • 广度优先(Breadth First Search)

  • 启发式搜索(Heuristic Search)

• 压缩

  • 哈夫曼编码

• 加密

  • 对称加密
    • AES
    • DES
    • RC4
  • 非对称加密
    • RSA
    • IDEA

• 最优解

  • 递推
  • 递归(Recursion)
  • 贪心算法(Greedy)
  • 动态规划(DynamicProgram)
  • 随机搜索
  • 爬山法
  • 模拟退火法
  • 遗传算法

• 并行

• 机器学习

  • 回归算法
    • 最小二乘法(Ordinary Least Square)
    • 逻辑回归(Logistic Regression)
    • 逐步式回归(Stepwise Regression)
    • 多元自适应回归样条(Multivariate Adaptive Regression Splines)
    • 本地散点平滑估计(Locally Estimated Scatterplot Smoothing)
  • 基于实例的算法
    • k-Nearest Neighbor(KNN)
    • 学习矢量量化（Learning Vector Quantization， LVQ）
    • 自组织映射算法（Self-Organizing Map ， SOM）
  • 正则化方法
    • Ridge Regression
    • Least Absolute Shrinkage and Selection Operator（LASSO）
    • 弹性网络（Elastic Net）
  • 决策树学习
    • 分类及回归树（Classification And Regression Tree， CART）
    • ID3 (Iterative Dichotomiser 3)
    • C4.5
    • Chi-squared Automatic Interaction Detection(CHAID)
    • Decision Stump
    • 随机森林（Random Forest）
    • 多元自适应回归样条（MARS）
    • 梯度推进机（Gradient Boosting Machine， GBM）
  • 贝叶斯方法
    • 朴素贝叶斯算法
    • 平均单依赖估计（Averaged One-Dependence Estimators， AODE）
    • Bayesian Belief Network（BBN）
  • 基于核的算法
    • 支持向量机（Support Vector Machine， SVM）
    • 径向基函数（Radial Basis Function ，RBF)
    • 线性判别分析（Linear Discriminate Analysis ，LDA)
  • 聚类算法
    • k-Means算法
    • 期望最大化算法（Expectation Maximization， EM）
  • 关联规则学习
    • Apriori算法
    • Eclat算法
  • 人工神经网络
    • 感知器神经网络（Perceptron Neural Network）
    • 反向传递（Back Propagation）
    • Hopfield网络
    • 学习矢量量化（Learning Vector Quantization， LVQ）
  • 深度学习
    • 受限波尔兹曼机（Restricted Boltzmann Machine， RBN）
    • Deep Belief Networks（DBN）
    • 卷积网络（Convolutional Network）
    • 堆栈式自动编码器（Stacked Auto-encoders）
  • 降低维度算法
    • 主成份分析（Principle Component Analysis， PCA）
    • 偏最小二乘回归（Partial Least Square Regression，PLS）
    • Sammon映射
    • 多维尺度（Multi-Dimensional Scaling, MDS）
    • 投影追踪（Projection Pursuit）
  • 集成算法
    • Boosting
    • Bootstrapped Aggregation（Bagging）
    • AdaBoost
    • 堆叠泛化（Stacked Generalization， Blending）

结构

• 组织结构
  • 集合结构
  • 线性结构
    • 线性表(Linear List)
    • 栈(Stack)
    • 队列(Queue)
    • 数组(Array)
    • 串(String)
    • 广义表(General List)
    • 跳跃表
  • 树型结构
    • 树(Tree)
      • 胜者树
      • 左偏树
      • 二项树
      • 线段树
      • 后缀树
      • 哈夫曼树
      • trie树(静态建树、动态建树)
      • 静态二叉检索树
      • RMQ
    • 堆(Heap) 二叉堆 斜堆
  • 图型结构
    • 图(Graph)
      • trie图
      • 有限状态自动机
• 统计结构
  • 树状数组
  • 虚二叉树
  • 线段树
  • 矩形面积并
  • 圆形面积并
• 关系结构
  • Hash表
  • 并查集
  • 路径压缩思想

数学原理

• 组合数学
  • 加法原理和乘法原理.
  • 排列组合
  • 容斥原理
  • 抽屉原理
  • 置换群与Polya定理
  • 递推关系和母函数
  • MoBius反演
  • 偏序关系理论
• 数论
  • 素数与整除问题
  • 进制位
  • 同余模运算
• 博奕论
  • 极大极小过程
  • Nim问题
• 概率论
• 数理统计
• 运筹学
• 计算几何学
  • 几何公式
  • 叉积和点积的运用(如线段相交的判定,点到线段的距离等)
  • 凸包
  • 坐标离散化.
  • 扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
  • 多边形的内核(半平面交)
  • 几何工具的综合应用
  • 半平面求交
  • 可视图的建立
  • 点集最小圆覆盖.
  • 对踵点

其他常见问题

按数学领域划分

• 图论

  • 图的深度优先遍历和广度优先遍历.
  • 最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
  • 最小生成树算法(prim,kruskal)
  • 拓扑排序
  • 二分图的最大匹配 (匈牙利算法)
  • 最大流的增广路算法(KM算法)
  • 度限制最小生成树和第K最短路.
  • 最优比率生成树.
  • 次小生成树.
  • 无向图、有向图的最小环
  • 差分约束系统的建立和求解
  • 最小费用最大流
  • 双连通分量
  • 强连通分支及其缩点
  • 图的割边和割点
  • 最小割模型、网络流规约

• 动态规划

  • 四边形不等式理论
  • 函数的凸凹性
  • 规划方向
  • 旅行商问题
  • 最优二分检索树
  • 树型动态规划
  • 状态动态规划
  • 记录状态的动态规划
  • LCA(Least Common Ancestors),即最近公共祖先
  • RMQ(Range Minimum/Maximum Query),即区间最值查询
  • 最长子序列系列问题
  • 最长不下降子序列
  • 最长公共子序列
  • 最长公共不下降子序列
  • 不完全状态记录
  • 青蛙过河问题
  • 利用区间dp
  • 背包类问题
    • 0-1背包，经典问题
    • 无限背包，经典问题
    • 判定性背包问题
    • 带附属关系的背包问题
    • +-1背包问题
    • 双背包求最优值
    • 构造三角形问题
    • 带上下界限制的背包问题(012背包)
  • 线性的动态规划问题
    • 积木游戏问题
    • 决斗（判定性问题）
    • 圆的最大多边形问题
    • 统计单词个数问题
    • 棋盘分割
    • 日程安排问题
    • 最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
    • 方块消除游戏(某区间可以连续消去求最大效益)
    • 资源分配问题
    • 数字三角形问题
    • 邮局问题与构造答案
    • 最高积木问题
    • 两段连续和最大
    • 2次幂和问题
    • N个数的最大M段子段和
    • 交叉最大数问题
  • 判定性问题的dp(如判定整除、判定可达性等)
    • 模K问题的dp
    • 特殊的模K问题，求最大(最小)模K的数
    • 变换数问题
  • 单调性优化的动态规划
    • 1-SUM问题
    • 2-SUM问题
    • 序列划分问题(单调队列优化)
  • 剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
    • 凸多边形的三角剖分问题
    • 乘积最大问题
    • 多边形游戏(多边形边上是操作符,顶点有权值)
    • 石子合并(N^3/N^2/NLogN各种优化)
  • 贪心的动态规划
    • 最优装载问题
    • 部分背包问题
    • 乘船问题
    • 贪心策略
    • 双机调度问题Johnson算法
  • 状态dp
    • 牛仔射击问题(博弈类)
    • 哈密顿路径的状态dp
    • 两支点天平平衡问题
    • 一个有向图的最接近二部图
  • 树型dp
    • 完美服务器问题(每个节点有3种状态)
    • 小胖守皇宫问题
    • 网络收费问题
    • 树中漫游问题
    • 树上的博弈
    • 树的最大独立集问题
    • 树的最大平衡值问题
    • 构造树的最小环