使用迭代替换查找多次重复的运行时间
Find runtime of Multiple Recurrences using Iterative Substitution
我正在尝试使用迭代替换查找以下重复的运行时间:
T(n) = T(n/2) + T(n/3) + n
问题是有两个 T(n/x)
项,事实证明,为这种情况找到一般形式非常具有挑战性。
对于这样的情况,是否应该遵循使用迭代替换的一般准则?
此重复来自 class 个 Akra–Bazzi 个重复。根据公式,解决方案是:
或者,假设 T(1) = c0
那么你可以通过归纳法证明 T(n) <= max(6,c0)*n
。
您也可以使用替换规则。方法如下:
T(n) = T(n/2)+T(n/3) + n =
= n+(n/2+n/3)+T(n/(2*2))+T(n/(2*3))+T(n/(3*2))+T(n/(3*3))
= n+(n/2+n/3)+(n/(2*2)+n/(2*3)+n/(3*2)+n/(3*3))
+T(n/(2*2*2))+T(n/(2*2*3))
+T(n/(2*3*2))+T(n/(2*3*3))
+T(n/(3*2*2))+T(n/(3*2*3))
+T(n/(3*3*2))+T(n/(3*3*3))=
...
= n * (1 + 5/6 + (5/6)^2 + (5/6)^3 + (5/6)^4 + ...)
= 6 * n (assuming n = 2^k3^k. you get < 6*n otherwise)
这里没有什么正式的,但是
T(n) = 2T(n/2) + n // O(nlog(n))
所以你的循环可能仍然是 O(nlog(n))?
基本情况是什么?
我正在尝试使用迭代替换查找以下重复的运行时间:
T(n) = T(n/2) + T(n/3) + n
问题是有两个 T(n/x)
项,事实证明,为这种情况找到一般形式非常具有挑战性。
对于这样的情况,是否应该遵循使用迭代替换的一般准则?
此重复来自 class 个 Akra–Bazzi 个重复。根据公式,解决方案是:
或者,假设 T(1) = c0
那么你可以通过归纳法证明 T(n) <= max(6,c0)*n
。
您也可以使用替换规则。方法如下:
T(n) = T(n/2)+T(n/3) + n =
= n+(n/2+n/3)+T(n/(2*2))+T(n/(2*3))+T(n/(3*2))+T(n/(3*3))
= n+(n/2+n/3)+(n/(2*2)+n/(2*3)+n/(3*2)+n/(3*3))
+T(n/(2*2*2))+T(n/(2*2*3))
+T(n/(2*3*2))+T(n/(2*3*3))
+T(n/(3*2*2))+T(n/(3*2*3))
+T(n/(3*3*2))+T(n/(3*3*3))=
...
= n * (1 + 5/6 + (5/6)^2 + (5/6)^3 + (5/6)^4 + ...)
= 6 * n (assuming n = 2^k3^k. you get < 6*n otherwise)
这里没有什么正式的,但是
T(n) = 2T(n/2) + n // O(nlog(n))
所以你的循环可能仍然是 O(nlog(n))?
基本情况是什么?