《Python Algorithm》6.分治法

《Python Algorithm》6.分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。 分治法的精髓： 分--将问题分解为规模更小的子问题； 治--将这些规模更小的子问题逐个击破； 合--将已解决的子问题合并，最终得出“母”问题的解；

《Python Algorithm》6.分治法

• 树形问题：平衡
  • 应已阅读
    • 第三章的分治法递归
    • 第四章的完全归纳法（strong induction）
    • 第五章的递归遍历
  • 对比平衡与不平衡的分解
    • 不平衡：线型分解/结合，平方运行时间
    • 分治（平衡）：线型分解/结合，log运行时间
  • skyline问题
    • 描述
      • 给定一个有序的三元组序列(L,H,R)
        • L:一个建筑的左横坐标
        • H:高度
        • R:右横坐标
      • 即每个三元组表示一个矩形建筑轮廓
      • 目的是从这些独立建筑轮廓中构建整体轮廓（skyline）
    • 在已有轮廓上添加一个建筑
      • 如果轮廓以水平线段的三元组列表构成，则添加一个新建筑是线性的
      • 步骤
        • 在skyline的序列中寻找建筑的左坐标
        • 提升所有低于这个建筑的高度，直到
        • 找到建筑的右坐标
        • 新建筑左右坐标在几个水平坐标中间时，需要被分成两个
    • 画出所有建筑轮廓
      • 简单归纳法
        • 开始于一个建筑，添加新建筑直到结束
        • 平方运行时间
      • 分治法
        • 合并两个轮廓并不比合并轮廓和一个新建筑更难
        • 只遍历两个前后挨着的，如果有一个高于另一个，使用最大值
          • 如果需要的话分割水平线段
        • 算法
          • 首先递归的创建两个轮廓，每个基于一般建筑，然后合并他们
          • log运行时间
        • Ex6-1
• 典型的分治算法
  • 算法
    • 输入：set/列表
    • 元素被分成两个基本相等的集合（线性），算法递归的在每半运行，然后结合（线性）
  • 代码（通用）
  • 图解
• 二分法搜索
  • 应用
    • 版本控制系统
      • 如
        • Mercurial
        • git
      • 步骤
        • 编写测试
        • 让版本控制系统找到历史中bug出现在哪次中
  • 遍历搜索树与剪枝
    • 注意
      • 值有序
      • 如果是链表，插入是常数的，但python没有链表
        • 解决：树
    • 树的实现
      • 节点左子树都小于等于该节点，右子树都大于
      • set/mapping
    • 代码实现
  • 选择
    • 问题
      • 找到无序列表中第k大的元素
        • 最重要的情景是找中位数
    • 副作用
      • 找到k个更小的（n-k个更大的），即运行时间Θ(n),与k值无关
    • 堆
      • 堆中永远不会超过k个元素
      • Θ(n lg k)
      • heapq模块的nsmallest/nlargest
    • 删除k的依赖
      • 关注平均情况
      • T(n) = T(n/2) + n
      • 找到枢纽pivot
    • 代码实现
      • 分区和选择
  • sidebar/tip
    • bisect库
      • bisect(a, 5)
        • 返回插入位置（相同时靠右）
        • 等价于bisect_right
      • bisect_left(a, 5)
        • 靠左
      • insort/insort_right/insort_left
        • 查找后插入
        • 插入是线性的
      • 不支持key参数
    • 有序列表、树和字典的选择
    • 保证选择的线性时间
      • 随机选择算法
        • Ex6-13
        • 平均线性，但最差平方
      • BFPRT算法
        • 保证线性
        • 步骤
          • 首先把序列每五个分为一组
            • 或其他小常量
          • 找出每组的中位数
            • 使用简单的排序算法
          • 使用线性选择算法进行递归找出中位数的中位数
          • 结果值是一个能保证足够好的枢纽
        • T(n) <= T(n/5) + T(7n/10 + 6) + O(n)
• 二分法排序
  • 注意
    • 本节不会太深入，因为Python的list.sort足够高效
  • 快排
    • 非常接近上节的选择算法
      • 区别是遍历所有的k
    • 代码实现
    • 时间
      • 平均log
      • 最差平方
  • 归并排序
    • 代码实现
      • Ch3 Listing3-2
    • heapq.merge
  • 排序能有多快？
    • 最坏Ω(n lg n).
    • 除非知道值域或分布，否则log最好
  • sidebar
    • timsort
      • Python的list.sort
      • 近似归并排序
      • 原地算法
• 另外三个例子
  • 概述
    • 前两个是计算几何学
    • 最后一个是简单问题
  • 最近点对
    • 问题
      • 一组点，找到最近的两个
    • 解决
      • 检查每组点对距离
        • 平方复杂度
      • 分治法
        • log
        • 算法
          • 按X坐标把点按中线L两等分，分别找出最近点对，取最小值 d
          • 取出L两侧宽度各d的长带
            • 左
            • 右
            • 既不也不
          • 最小点可能位于长带内
          • 对于长带左侧某点只检查右侧最近6个点（网上资料）
            • 书中写的7个点（实际5个点）
  • 凸包
    • 问题
      • 在板上钉n个钉子，然后绑橡皮筋
      • 凸多边形是最外侧点的连线
    • 解决
      • 用x坐标二等分点集，递归解决
      • 找到上下切线进行结合
        • 线性
        • 从左半的最右和右半的最左开始
    • sidebar
      • 可以多快？
        • 多数O(n lg n)
        • 一些更快的O(n lg h)
          • h是外壳的点数
  • 最大切片
    • 问题
      • 包含实数的序列A，找到一组切片使sum(A[i:j])最大
      • 不要选整个序列，因为可能有负数
      • 股票交易找最大利润
    • 解决
      • 暴力法
        • result = max((A[i:j] for i in range(n) for j in range(i+1,n+1)), key=sum)
        • 立方
      • 解决sum的时间
        • 一次迭代考虑长度k的所有间隔
        • 然后k+1
        • 平方复杂度
          • 技巧：每次间隔移动时，减移出的，加移入的，而不是重新计算
        • 代码实现
      • 分治
        • 分为两组，找到每组最大切片
        • 寻找是否有在中间的（如最近点集问题）
        • log
    • sidebar
      • 多线程
        • muultiprocessing模块
• 树平衡
  • 注意
    • 难点，可忽略，不影响本书其他内容
  • 操作
    • 结点分裂/合并
    • 结点旋转
  • 2-3树
    • 一个节点含有1个关键字2个孩子或2个关键字3个孩子
    • B-树的特例
      • 几乎所有数据库系统的实现基础
    • 查找
      • 带有剪枝的递归遍历
    • 插入
      • 如果有空位，直接加
      • 如果没有，要考虑三个键
        • 分裂结点
          • 把中间值升至父亲
            • 如果是根则添加新根
            • 如果父亲满载继续执行
          • 叶子在同一层
    • 可以用二进制结点模拟
      • 结构更简单和一致
      • 旋转
      • AA-树
      • 代码实现
  • sidebar
    • 二进制堆、heapq和堆排序
      • 优先队列的实现
        • Prim（ch7）
        • Dijkstra（ch9）
      • 二进制堆
        • 完全二叉树
        • 性质
          • 每个父亲小于两个孩子（最小堆）
        • 不会旋转
          • 交换父子保持性质
      • heapq模块
        • heappush/heappop
        • heapify
          • 线性
        • heapreplace
        • merge/nlargest/nsmallest
      • 堆排序
• 扩展阅读
  • 二分
    • 插值查找
      • 平均O(lg lg n)
  • 实现集合（有效成员检查）
    • Bloom filters
  • 搜索树
    • 红黑树
    • AVL树
    • splay tree
  • 索引多维坐标和距离
  • 其他树结构
    • interval trees
    • quadtrees
    • octtrees