《Python Algorithm》3.Counting 101

“数学[英语：mathematics，源自古希腊语μάθημα（máthēma）；经常被缩写为math或maths]，是研究数量、结构、变化、空间以及信息等概念的一门学科。数学是人类对事物的抽象结构与模式进行严格描述、推导的一种通用手段，可以应用于现实世界的任何问题，所有的数学对象本质上都是人为定义的。从这个意义上，数学属于形式科学，而不是自然科学。

《Python Algorithm》3.Counting 101

• 求和的基础知识
  • • sum(f(i) for i in range(m, n+1))
  • 分配律
    • c * sum(f(i) for i in seq)
    • sum(c * f (i) for i in seq)
  • 结合律
    • sum(f(i) for i in seq) + sum(g(i) for i in seq)
    • sum(f(i) + g(i) for i in seq)
• 两种锦标赛
  • 本节研究内容
    • 循环赛
      • round-robin
    • 锦标赛
      • knockout
  • 握手
    • n(n-1)/2
    • Θ(n2)
  • 龟兔赛跑
    • 二叉树
    • 代表
      • 兔：宽（n = 2 ** h）
      • 龟：高（h = log(n, 2)）
    • 二分法
      • Ch 6
• 子集、排列、组合
  • 排列
    • 特点
      • 顺序确定
    • bogo排序
      • 反复生成随机数，直到排序正确
      • Θ(n · n!)
    • A(n, m) = n! / (n - m)!
  • 组合
    • 二项式系数
    • C(n, m) = n! / (k!(n-k)!)
  • sidebar/tip
    • pseudo-polynomiality
      • 素数
    • Python数学符号工具
      • Sage
      • Wolfram Alpha
• 递归
  • 手工推导
    • 递推关系
      • T(n) = T(n-i) + i
      • T(n) = Θ(n)
  • 重要示例
    • 通用格式
      • T(n) = a·T(g(n)) + f(n)
        • a:递归次数
        • g(n):需要递归解决的子问题规模
        • f(n):函数中的额外工作
    • 一些重要递归
      • T(n) = T(n-1) + 1
        • Θ(n)
        • 处理一个序列，如reduce
      • T(n) = T(n-1) + n
        • Θ(n ** 2)
        • 握手问题
      • T(n) = 2T(n-1) + 1
        • Θ(2 ** n)
        • 汉诺塔
      • T(n) = 2T(n-1) + n
        • Θ(2 ** n)
      • T(n) = T(n/2) + 1
        • Θ(lgn)
        • 二分查找
          • Ch6
      • T(n) = T(n/2) + n
        • Θ(n)
        • 随机选择
          • Ch6
      • T(n) = 2T(n/2) + 1
        • Θ(n)
        • 树的遍历
          • Ch5
      • T(n) = 2T(n/2) + n
        • Θ(nlgn)
        • 分治法排序
          • Ch6
    • 通用方法
      • 逐步推倒直到看到一个模式
      • 使用行号变量i表达公式
        • 公式5
        • 公式6
          • • 假设T(1)=1
        • 公式8
          • T(n) = n + lgn
            • 假设i = lgn
      • 选择i以便递归达到目标
  • 猜想与验证
    • 问题
      • 前述n都假设为2的幂，而实际很少这样
    • 归纳法证明
      • 公式1
      • 公式8
  • 主定理：一个普遍适用的解决方案
    • T(n) = aT(n/b) + f(n)
      • a: 递归次数
      • 1/b: 百分比
    • 对于树而言
      • a:每个内部节点的孩子数
      • log(n, b): 高度
      • a ** log(n, b):宽度
      • n ** log(a, b):叶子数
    • 3种场景
      • 根节点运算占主体
        • 时间
          • Θ(f (n))
        • 如何判断
          • 不断缩小常数因子，如果根节点渐进地比叶子做更多工作
        • 形式
          • 条件
            • c < 1
            • large n
            • • ε:某个特定常数（任意小的数？）
        • 举例
          • T(n) = 2T(n/3) + n
      • 叶子节点运算占主体
        • 时间
        • 举例
          • T(n) = 2T(n/2) + lgn
      • 根叶增长趋势相同
        • 形式
        • 时间
        • 举例
          • T(n) = 2T(n/4) + sqrt(n)
  • sidebar/tip
    • 掉进兔子洞（改变变量）
• 代码实现
  • gnome sort
    • 特点
      • 1层循环
      • i交换-1，不交换+1
    • 时间
      • Ω(n)
      • O(n2)
  • merge sort
    • 讲解
      • Ch6
    • 时间
      • Θ(n lg n)
• 扩展阅读
  • 离散数学
  • 计算和证明
    • Proofs That Really Count, by Benjamin and Quinn
  • 具体数学
    • Concrete Mathematics, by Graham, Knuth, and Patashnik