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)$ c的形式$ C>。对于提供的示例:
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屋!