1. 主定理（Master Theorem）三种情况的完整陈述与典型示例中 Case 1 T(n)=8T(n/2)+n² → O(n³)、Case 2 T(n)=2T(n/2)+n → O(n log n)、Case 3 T(n)=2T(n/2)+n² → O(n²)，以及正则条件的验证
请完整陈述主定理的三种情况，验证 Case 1 的 T(n)=8T(n/2)+n² → O(n³)、Case 2 的 T(n)=2T(n/2)+n → O(n log n)、Case 3 的 T(n)=2T(n/2)+n² → O(n²)，并说明正则条件（regularity condition）的作用？
- 主定理三个分支（case1/case2/case3）的适用条件与结论形式
- 对三个具体递推式正确识别 a、b、log_b a 并代入
- 正则条件 a·f(n/b) ≤ c·f(n) 的验证与意义
主定理针对形如 T(n)=a·T(n/b)+f(n) 的递推式（a≥1，b>1，f(n) 渐近非负）。令 c = log_b a（即 n^(log_b a) 为临界函数），分三种情况：Case 1，若 f(n)=O(n^(c−ε))（ε>0），则 T(n)=Θ(n^c)。对 T(n)=8T(n/2)+n²，a=8、b=2、c=log₂8=3，f(n)=n²=O(n^(3−1))，故 T(n)=Θ(n³)。Case 2，若 f(n)=Θ(n^c·log^k n)（k≥0），则 T(n)=Θ(n^c·log^(k+1) n)。对 T(n)=2T(n/2)+n，a=2、b=2、c=1，f(n)=n=Θ(n·log⁰n)，故 T(n)=Θ(n log n)。Case 3，若 f(n)=Ω(n^(c+ε))（ε>0）且满足正则条件 a·f(n/b) ≤ c·f(n)（c<1），则 T(n)=Θ(f(n))。对 T(n)=2T(n/2)+n²，a=2、b=2、c=log₂2=1，f(n)=n²=Ω(n^(1+ε))，且 2·(n/2)²=n²/2 ≤ c·n²（取 c=1/2 成立），故 T(n)=Θ(n²)。
主定理的本质是比较"递归分裂代价" n^(log_b a) 与"合并代价" f(n) 的渐近大小：Case 1 分裂主导、Case 3 合并主导、Case 2 两者同阶故多乘一个 log。正则条件仅出现在 Case 3，它保证 f(n) 不会随递归加深而"缩水"，从而递推式整体被 f(n) 主导，这是正确应用 Case 3 的必要前提。
// Case 3 的正则条件验证示例：a=2, b=2, f(n)=n^2
// a*f(n/b) = 2*(n/2)^2 = n^2/2，取 c=1/2 (<1) 满足 n^2/2 <= c*n^2
public class MasterVerify {
static boolean regularity(int a, int b, double fOfN, double fOfNOverB) {
double c = 0.5; // 任意满足 0<c<1 的常数
return a * fOfNOverB <= c * fOfN;
}
public static void main(String[] args) {
// a=2, b=2, f(n)=n^2, f(n/b)=(n/2)^2
System.out.println(regularity(2, 2, 100, 25)); // 2*25=50 <= 0.5*100=50，true
}
}