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）二项式求和：

We can expand T(n) with a binomial summation:

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

(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屋！