Master Theorem

分治策略的递推式通常形如 ,表示原问题被分为 个 规模的子问题,原问题自身需要 时间。

  • 若 ,则
  • 若 ,则
  • 若 ,则 直观理解: 构造了一颗 叉树,每层问题规模减少为 倍,则树共 层,遍历这棵树需 时间 更一般地,有 Akra-Bazzi Theorem

Akra-Bazzi Theorem

可以理解为泛化的主定理。

参数 可类比为

  • 增长慢于 ,
  • 增长等于 ,
  • 增长快于 ,

Example

运用自然数立方求和公式,

取 ,发现成立

因此 因此

例:大数乘法