algorithm - 求解递归T(n) = 3T(n/5) + T(n/2) + 2^n

Question

我在假设 T(n) 是接触 n <= 2 的情况下求解 T(n) 的递归。我开始用树方法求解这个 T(n)，因为我们不能使用主方法在这里，但是当我做这棵树时，我当然是在计算这个 T(n) 的时间 C，但是我的 C-s 非常重要而且很奇怪，所以我得到了

c = 2^n 然后对于下一个 c 我得到 ' 3 * 2^(n/5) + 2^(n/3)

而且我不知道如何用这些值来解决，我做错了什么或者我应该遵循什么程序来解决这个问题？

Answer 1

您可能希望尽可能减少术语的数量。

3 * 2^(n/5) + 2^(n/3) = 3 * (2^(1/5) * 2^n) + (2^(1/3) * 2 ^n)

然后将所有系数组合在一起。

(3 * 2^(1/5)) * 2^n + (2^(1/3)) * 2^n

注意公因数是 2^n。所以你会得到:

(3 * 2^(1/5) + 2^(1/3)) * 2^n

我将产品的第一部分命名为 constant 会给我们:

constant * 2^n 就是 T(2^n) 因为随着 n 的大小变得非常大，该常量变得微不足道。