理论与进阶专题
主定理
主定理是求解一类非常常见的递推式的「菜谱」：T(n) = aT(n/b) + f(n)。这里 a 是你产生的子问题个数，b 是每个子问题缩小的倍数，f(n) 是递归调用之外要做的额外工作——拆分和合并。许多分治算法恰好就是这个形状，于是你不必每次从头求解，只要比较两个量就能读出答案。
要比较的两个量是：f(n)——一层上所做的工作，与 n^(log_b a)——衡量叶子层子问题个数增长得有多快。定理分三种情形。情形一：若叶子工作 n^(log_b a) 比 f(n) 增长得更快，递归的底层占主导，T(n) = O(n^(log_b a))。情形二：若两者增速相同，每一层的代价都差不多，而你要在全部 log n 层上付这份代价，于是 T(n) = O(n^(log_b a) · log n)。情形三：若 f(n) 增长得更快，顶层占主导，T(n) = O(f(n))。
归并排序是教科书式的契合：T(n) = 2T(n/2) + O(n)，故 a = 2、b = 2，n^(log_b a) = n^(log_2 2) = n。合并工作 f(n) = O(n) 与 n 增速相同，正是情形二——每层代价 O(n)，共 log n 层，总计 O(n log n)。一句老实话：主定理只覆盖这种特定形状、且子问题大小大致相等的递推，情形三还需要一个温和的「正则性」条件。当递推不符合此形时，退回到递归树或归纳法。
// T(n) = a*T(n/b) + f(n) // Compare f(n) with n^(log_b a): // case 1: f(n) smaller -> T = O(n^(log_b a)) // case 2: same rate -> T = O(n^(log_b a) * log n) // case 3: f(n) larger -> T = O(f(n)) // // merge sort: a=2, b=2 -> n^(log2 2) = n; f(n)=n -> case 2 // => T(n) = O(n log n)
归并排序：a=2、b=2、f(n)=n、n^(log_b a)=n → 情形二 → O(n log n)。
它只适用于 T(n) = aT(n/b) + f(n) 这种、子问题大致等大的递推；其他形状要用递归树或归纳法。
又称
另见