algorithm - 复发的解决办法

Question

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

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

标签： algorithmcomplexity-theoryrecurrence

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^{hi}))

这意味着 h 级有贡献

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

请注意，递归树的高度介于

(\log_2 N, \log_3 N)

因此，大哦符号是

O(N log N)

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