recurrence - 主定理：如何在这个递归关系中找到 b 的值

Question

主定理与T(n) = aT(n/b) + f(n)a >=1 和 b > 1 形式的递归一起使用，在这种情况下，b 的值可以很容易地从递归中看出，但是我有一个形式的递归

T(n) = T((n/4)+3) + f(n)

我如何得到b？

Answer 1

因此，如果您尝试简化递归，它将是这样的，T(n)= T((n+12)/3)) + f(n)

因为每次都会加上 n ，所以有两种可能性，主定理将不适用，因为方程不是 T(n)=aT(n/b)+ f(n) 的形式，或者你可以忽略+12 是常数，当 n 变化时不会变化，因此您可以将其重写为 T(n)= T(n/3)+f(n) 并使用主定理解决此问题，您将找到答案很可能与上面的相同。

或者您可以使用递归树简单地猜测解决方案