用主定理求解递归式t(n)=t(n/5)+t(n/17)+n，推导是否正确？

我将递归式t(n)通过上下界约束为$t_1(n)=2t(rac{n}{17})+n\leq t(n)\leq t_2(n)=2t(rac{n}{5})+5$。接着我用主定理分别求解$t_1(n)$和$t_2(n)$：对于$t_1(n)$，令$a=2,b=17,f(n)=n$，可得$f(n)^{log_b{a}}=n{log_{17}{2}}=\Omega(n^{log_{17}{2}+\epsilon})$（其中$\epsilon=1-log_{17}{2}>0$），且$a\cdot f(n/b)=2\cdot\frac{n}{17}\leq c\cdot n$（常数$c=0.5<1$），根据主定理情况3得出$t_1(n)=\Omega(n)$；同理，对于$t_2(n)$，令$a=2,b=5,f(n)=n$，可得$n^{{log_{5}{2}}=\Omega(n}{log_{5}{2}+\epsilon})$（$\epsilon=1-log_{5}{2}$），且$2\cdot \frac{n}{5}\leq c\cdot n$（$c=0.5$），根据主定理情况3得出$t_2(n)=\Theta(n)$。因此我得出$t(n)=\Theta(n)$，请问该推导是否正确？若错误，请指出问题所在。

你的推导存在两处关键错误，导致结论不可靠，具体问题如下：

1. 对$t_2(n)$的主定理应用完全错误 #

你定义的$t_2(n)=2t(\frac{n}{5})+5$，但在分析时错误地将$f(n)$当成了$n$，实际$f(n)=5$（常数函数）。针对这个递归式：

• $a=2$，$b=5$，计算$log_b a = log_5 2 ≈ 0.43$
• 常数函数$f(n)=5$满足$f(n)=O(n^{log_5 2 - \epsilon})$（取$\epsilon=0.1$即可），符合主定理情况1的条件
• 因此正确结论是$t_2(n)=\Theta(n^{log_5 2})$，而不是你得出的$\Theta(n)$

2. 上下界的约束逻辑可能不成立 #

你假设$t_1(n) \leq t(n) \leq t_2(n)$，但这个约束是否合理取决于原递归式的形式：

• 如果原递归式是$t(n)=2t(\frac{n}{k})+n$（其中$5 \leq k \leq 17$），那么正确的上下界应该是$2t(\frac{n}{17})+n \leq t(n) \leq 2t(\frac{n}{5})+n$（因为$k$越小，子问题规模$\frac{n}{k}$越大，递归开销越高），此时$t_2(n)$的$f(n)=n$，主定理情况3应用正确，$t_2(n)=\Theta(n)$，结合$t_1(n)=\Theta(n)$，才能推出$t(n)=\Theta(n)$
• 但你写的$t_2(n)$是$+5$而非$+n$，这会导致上界$t_2(n)$的复杂度远低于$n$，和$t(n)$的实际增长趋势矛盾，约束关系不成立

补充：$t_1(n)$的结论表述不准确 #

你对$t_1(n)$应用主定理情况3时，正确结论应该是$t_1(n)=\Theta(n)$（情况3的结论是$T(n)=\Theta(f(n))$），而不是你写的$\Omega(n)$——虽然$\Omega(n)$本身没错，但没有给出紧界，不够精确。

如果修正$t_2(n)$的表达式为$2t(\frac{n}{5})+n$，同时修正$t_1(n)$的结论为$\Theta(n)$，那么你的推导逻辑是正确的，最终$t(n)=\Theta(n)$的结论成立。

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