有人可以用替代方法帮助我解决此重复吗？

Question

有人可以帮我解决这种复发吗？使用替换方法，T（n）= 8T（n / 2）+ n ^ 2为T（n）= O（n ^ 3）。考虑到T（1）= 1

Answer 1

处理这种递归关系的一种方法是来自Python符号数学库rsolve的rsolve：

sympy

这将输出解

from sympy import Function, rsolve, log
from sympy.abc import k, n

f = Function('f')
g = Function('g')

# T(n) = 8T(n/2) + n^2   T(1) = 1
T = f(n) - 8 * f(n / 2) - n ** 2 - 3
Tk = T.subs({n: 2 ** k, f(n): g(k), f(n / 2): g(k - 1)})

s = rsolve(Tk, g(k), {g(0): 1})
print("solution for k:", s.cancel())
print("solution for n:", s.subs({k: log(n, 2)}).simplify().cancel())

for k in range(0, 11):
    print(f"k={k}, n={2 ** k}, T(n)={(17 * n ** 3 - 3) // 7 - n ** 2}")

。请注意，该功能仅针对(17*n^3 - 3)/7 - n^2的2的幂定义。n的第一个值是n=1,2,4,8,...

Answer 2

只需尝试扩大关系并继续进行归纳：

1, 15, 139, 1179, 9691, 78555, 632539, 5076699, 40679131, 325695195, 2606610139

[每次将

T(n) = 8 T(n/2) + n^2 =
       8(8T(n/4) + (n/2)^2) + n^2 = 8^2 T(n/2^2) + 8 (n/2)^2 + n^2

除以​​n时，如果为2，则表示序列n = 2^k的长度：

k = log(n)

用

T(n) = n^2 + 8 (n/2)^2 + 8^2 (n/2^2)^2 + ... + 8^log(n) T(1)
     = sum_{i=0}^{log(n)} 8^i (n/2^i)^2

重写关系：

2^2i = 4^i

注意

T(n) = sum_{i=0}^{log(n)} 8^i/4^i n^2 = n^2 * sum_{i=0}^{log(n)} 2^i
     = n^2 (2^(log(n)+1) - 1) = \Theta(n^3)

。