主定理的扩展很多算法的递归是这样的T(n)T(n/3)T(2n/3)O(n)T(n)T(n/3)T(2n/3)O(n)或者T(n)T(n/5)T(7n/10)O(n)T(n)T(n/5)T(7n/10)O(n)这些递归的特点是子问题规模不同、递归分支不均匀。主定理无法直接套。这时候就需要 Akra–Bazzi 定理。Akra–Bazzi 定理处理什么Akra–Bazzi 定理处理的是T(n)f(n)∑i1kaiT(n/bi)T(n)f(n)i1∑k​ai​T(n/bi​)其中aiai​ 表示第 ii 类子问题有多少个n/bin/bi​ 表示第 ii 类子问题的规模f(n)f(n) 表示递归之外的额外工作它是主定理的扩展。主定理是它的特殊情况。计算核心先求一个 ppAkra–Bazzi 的第一步是找到 pp使得∑i1kaibi−p1i1∑k​ai​bi−p​1这个 pp 可以理解为递归结构本身的增长指数。为什么假设 T(n)T(n) 大概像 npnp代入递归np≈∑i1kai(n/bi)pnp≈i1∑k​ai​(n/bi​)p整理得np≈np∑i1kaibi−pnp≈npi1∑k​ai​bi−p​所以必须有∑i1kaibi−p1i1∑k​ai​bi−p​1这就是 Akra–Bazzi 定理的灵魂。结论求出 pp 之后有T(n)Θ(np(1∫1nf(u)up1du))T(n)Θ(np(1∫1n​up1f(u)​du))这个公式可以拆成两部分看npnp递归结构本身的复杂度积分每一层额外工作 f(n)f(n) 的累计影响因此使用 Akra–Bazzi 定理计算复杂度分为三步第一步解方程求出 p∑i1kaibi−p1i1∑k​ai​bi−p​1第二步计算积分∫1nf(u)up1du∫1n​up1f(u)​du第三步乘回 npnpT(n)Θ(np(1∫1nf(u)up1du))T(n)Θ(np(1∫1n​up1f(u)​du))例子主定理无法处理的递归考虑T(n)T(n/2)T(n/3)nT(n)T(n/2)T(n/3)n这里有两个子问题规模分别是 n/2n/2 和 n/3n/3。所以(1/2)p(1/3)p1(1/2)p(1/3)p1这个方程的解大约是p≈0.79p≈0.79又因为 f(n)nf(n)n所以T(n)Θ(np(1∫1nuup1du))T(n)Θ(np(1∫1n​up1u​du))积分部分为∫1nu−pduΘ(n1−p)∫1n​u−pduΘ(n1−p)因此T(n)Θ(np⋅n1−p)Θ(n)T(n)Θ(np⋅n1−p)Θ(n)不均匀分治快速排序不可能每次都选到最中间的枢纽。假设快速排序每次都把数组分成 1/41/4 和 3/43/4 两部分。递归为T(n)T(n/4)T(3n/4)O(n)T(n)T(n/4)T(3n/4)O(n)求 pp(1/4)p(3/4)p1(1/4)p(3/4)p1。显然 p1p1。于是T(n)Θ(n(1∫1nuu2du))T(n)Θ(n(1∫1n​u2u​du))最终 T(n)Θ(nlog⁡n)T(n)Θ(nlogn)这和快速排序的直觉一致只要划分不是极端不平衡快速排序仍然是 O(nlog⁡n)O(nlogn)。事实上只要每层总工作量是线性的并且问题按固定比例缩小总复杂度通常还是 nlog⁡nnlogn 级别。BFPRT 选择算法BFPRT也就是线性时间选择算法会出现类似递归T(n)T(n/5)T(7n/10)O(n)T(n)T(n/5)T(7n/10)O(n)其中T(n/5)T(n/5) 来自递归寻找中位数的中位数T(7n/10)T(7n/10) 来自递归处理剩下的一侧O(n)O(n) 来自分组、找中位数和 partition求 (1/5)p(7/10)p1(1/5)p(7/10)p1由于当 p1p1 时1/57/109/1011/57/109/101。所以真正的 p1p1。代入 Akra–Bazzi 公式后这就和例子一完全一样了。最终 T(n)Θ(n)T(n)Θ(n)递归结构本身占主导考虑T(n)2T(n/2)T(n/4)O(n)T(n)2T(n/2)T(n/4)O(n)求 pp2(1/2)p(1/4)p12(1/2)p(1/4)p1当 p1p1 时2⋅12145412⋅21​41​45​1当 p2p2 时2⋅1411691612⋅41​161​169​1所以1p21p2这里递归结构本身增长得比 nn 更快。因此T(n)Θ(np)T(n)Θ(np)。其中 pp 是方程 2(1/2)p(1/4)p12(1/2)p(1/4)p1 的解。和主定理的关系