用主定理求解递推式T(n)=9T(n/2)+n³：我的解法是否正确？

你的解法是正确的，原因如下：

主定理针对形如 T(n) = aT(n/b) + f(n)（其中a≥1，b>1）的递推式，分为三种核心情况判断：

• 对应递推式 T(n)=9T(n/2)+n³，参数为：a=9，b=2，f(n)=n³
• 计算得 log_b a = log₂9 ≈ 3.17
• 对比f(n)的量级：n³属于O(n^(log₂9 - ε))（取ε≈0.17>0），满足主定理的情况1
• 根据情况1的结论，递推式的解为Θ(n^log₂9)，与你的推导结果完全一致

内容的提问来源于stack exchange，提问作者Lan