T(n) = c1T(n/a) + c2(T/b) + f(n) [英] T(n) = c1T(n/a) + c2(T/b) + f(n)

问题描述

示例 T(n)=T(n/3)+T(n/4)+3n 这个可以用迭代主定理或递归树解决.有人可以分析解决它以显示它是如何完成的吗?

Example T(n)=T(n/3)+T(n/4)+3n is this solvable with iterative master theorem or recursion tree.Can someone solve it analytically to show how it's done ?

推荐答案

我们可以用二项式求和展开T(n):

(经过一些步骤 - 可以通过归纳证明

(after some steps - can be proven by induction

对于一些扩展/递归深度 k.

我们在哪里终止?当f(n)的所有实例的参数达到某个阈值C时.因此最大扩展深度:

Where do we terminate? When the parameters to all instances of f(n) reach a certain threshold C. Thus the maximum depth of expansion:

我们选择a, b中最小的，因为参数只有min(a, b)的幂以最慢的速度减少:

We choose the smallest between a, b because the parameter with only powers of min(a, b) decreases at the slowest rate:

因此T(n)的一般表达式为:

闭式解析解的存在依赖于f(n)的形式.对于提供的示例:

The existence of a closed form analytical solution depends on the form of f(n). For the example provided:

内部求和是一个二项式括号的展开式j:

The inner summation is the expansion of a binomial bracket raised to power j:

这是一个几何级数，并且等于(使用标准公式):

This is a geometric series, and equals (using standard formula):

现在由于 7/12 小于 1，对于较大的 k 值，上述结果中的幂项变得消失很小(因此n).因此在大n的限制下:

Now since 7/12 is less than 1, the power term in the above result becomes vanishingly small for large values of k (and thus n). Therefore in the limit of large n:

说实话，上面的例子可以用递归树更直接地完成；但同样不适用于例如n 的其他权力，例如f(n) = Cn^2，可以简单地纳入通式.

Truth be told the above example could have been done more straightforwardly with a recursion tree; but the same does not go for e.g. other powers of n, e.g. f(n) = Cn^2, which can be trivially incorporated into the general formula.

这篇关于T(n) = c1T(n/a) + c2(T/b) + f(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！