算法的大体结构

通过阅读《算法导论》篇前内容，从宏观上了解算法，对算法有一个整体上的印象和认识。

而《算法》一书分为排序、查找、图、字符串这四大块。

知识树

基本知识
- 算法是一项技术
- 设计和分析
  - 表达方法
    - 渐进表示
      - 渐进符号
      - 上界和下界
  - 设计策略
  - 基本思想
    - 贪心法
    - 分治法
    - 动态规划
      - 分治法与动态规划法实际上都是递归思想的运用
      - 二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解
      - 适用于分治法的问题分解成子问题后，各子问题间无公共子子问题，而动态规划法相反
    - 随机化
    - 回溯法
- 排序
- 概率分析和随机化算法
排序和顺序统计量
- 数据的结构
  - 关键字
  - 卫星数据
- why
  - 本身需要排序
  - 作为子程序
  - 排序算法数量非常庞大
  - 确定问题的下界
  - 实现排序算法会出现工程问题
- 排序算法
  - 插入排序
  - 归并排序
  - 堆排序
  - 快速排序
  - 计数排序
  - 基数排序
  - 桶排序
- 评估值
  - 最坏运行时间
  - 期望运行时间
- 顺序统计量：第i小的数？
数据结构
- 集合：现代数学的基础
- 计算机里的集合可变：动态集合
  - 元素
    - 用对象来表示
    - 组成
      - 关键字
        
        全序集，如实数集合
      - 卫星数据
    - 操作
      - 查询
      - 修改
        
        增加
        
        删除
        
        更新
- 一些数据结构
  - 栈
  - 队列
  - 链表
  - 根树
  - 散列表
  - 二叉搜索树
    - 红黑树
    - B树
      - B+树
- 从存储上分类
  - 线性（顺序）表
    - 顺序表
      - 计算机中以数组存储
    - 链表
    - 索引
    - 散列
    - 说明
      - C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。
  - 链表
    - 单链表
      - 动态
      - 静态
    - 双链表
    - 循环链表
      - 单循环
      - 双循环
    - 说明
      - 链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。
      - 数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问；链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效率比数组要低。
高级设计和分析技术
- 广泛使用的技术
  - 分治策略
  - 随机化方法
  - 递归技术
- 设计分析高效算法的三种重要技术
  - 动态规划：解决最优化问题
    - 分解成子问题，避免重复求解子问题
  - 贪心算法：通常用于最优化问题
    - 追求局部最优解
    - 拟阵理论？
  - 摊还算法：分析序列整体的实际代价的界？
    - 核算法
    - 势能法
    - 动态表
高级数据结构
- B树：为磁盘存储而专门设计的一类平衡搜索树
  - 考量执行时间和磁盘存取次数
- 可合并堆的一种实现：斐波那契堆？
- van Emde Boas树
  - 递归数据结构
- 用于不相交集合的一些数据结构
- 动态树：不相交的有根树的森林
  - 边代价
  - 结点到根的最小边代价路径
- 伸展树
- 持久数据结构？
- 聚合树
- 指数搜索树
- 动态图数据结构
  - 顶点连通性
  - 边连通性
  - 最小生成树
  - 双连通性
  - 传递闭包
图算法
- 图论
- 计算机表示
  - G = (V, E)
- 最小生成树：最小权重之和来连接所有结点
- 权重图：计算两个结点的最短路径
- 在流网络里计算出最大流
算法问题选编？？？
- 新的计算模型
  - 电路
  - 并行计算机
- 多线程算法：一种并行计算模型
- 矩阵操作
  - LU分解
  - LUP分解
  - 高斯消元法求解线性方程组
  - 矩阵求逆
  - 矩阵乘法
  - 计算最小二乘的近似解
- 线性规划：有限资源和竞争约束
  - 单纯形算法
- 多项式
  - 快速傅里叶变换（FFT）
    - 实现方法：并行电路
- 整数数论算法
  - 计算最大公约数的欧几里得算法
  - 应用：RSA公钥加密系统
  - 随机性素数测试来高效地找到最大素数
- 字符串匹配
  - 朴素字符串匹配
  - RK算法
  - 有限自动机
  - KMP算法
- 计算几何学
  - 基本性质
  - “扫除”方法来判断线段是否有交点
- NP完全问题
  - 很多计算问题都是NP完全的
  - 至今没有解决这一问题的多项式时间算法
  - 运用近似算法有效地找到NP完全问题的近似解
- 设计高效算法的一些已知局限
用到的数学知识
- 级数求和
- 集合等离散数学的内容
  - 集合
  - 关系
  - 函数
  - 图
  - 树
- 计数和概率
  - 计数
  - 概率
  - 离散随机变量
  - 几何分布与二项分布
- 矩阵与线性代数

算法的大体结构

发布于 2017-10-27 22:04:03

知识树

推荐书籍