Skip to content

Latest commit

 

History

History
325 lines (289 loc) · 8.8 KB

README.md

File metadata and controls

325 lines (289 loc) · 8.8 KB
Raw

算法学习 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种状态)
      • 小胖守皇宫问题
      • 网络收费问题
      • 树中漫游问题
      • 树上的博弈
      • 树的最大独立集问题
      • 树的最大平衡值问题
      • 构造树的最小环