algorithm - 复发的解决方法

Question

我正在寻找这种复发的解决方案。基本上我想学习如何解决这种复发以及如何获得它的值(value)。

T(N) = 3T(N/3) + T(N/2) + N

Answer 1

使用 Akra-Bazzi 方法绝对是一个很好的解决方案。

下面关于递归树的解是错误的。在评论中找到原因。

只是想在这里留下错误的解决方案，以防有人好奇或犯同样的错误。

这是递归树的解决方案。

对于水平h，它看起来像

T(N) = 3^h*T(N/3^h) + T(N/2^h) +\sum\limits_{i=1}^{h-1} (3^{i -1} + 3^i)*T(N/(3^i 2^{h-i}))

这意味着水平 h 贡献

N < N + N/2^h + 4N/3 * (1-\frac{1}{2^{h-1}}) < 4N

注意，循环树的高度介于

(\log_2 N,\log_3 N)

因此，大 O 表示法是

O(N log N)

( 只是想说明递归树是一种可能的解决方案。