求解递归关系 T(n) = 3T(2n/3) + cn
Solving recurrence relation T(n) = 3T(2n/3) + cn
我正在尝试通过迭代方法解决这个关系。
我了解到解决方案的第一部分是 3^rT(2/3)^r * n。但是剩下的不就是 cn + 3n + 5n + 7n .... 吗？
感谢您提供的任何帮助。
如果我们反复重新代入T：
m 次迭代后。我们什么时候停止？假设停止条件为n = 1:
因此最后的结果是：
一些数值测试证实了这个结果：
N T(N)
---------------------
1000 262143000
2000 1048574000
3000 3145725000
4000 8388604000
5000 20971515000
6000 25165818000
7000 29360121000
8000 67108856000
9000 75497463000
10000 83886070000
对数对数图：
该图的梯度 m 是 T(N) = ϴ(N^m)。结果 m = 2.70562 与 2.70951.
的理论值相当接近
我正在尝试通过迭代方法解决这个关系。
我了解到解决方案的第一部分是 3^rT(2/3)^r * n。但是剩下的不就是 cn + 3n + 5n + 7n .... 吗？
感谢您提供的任何帮助。
如果我们反复重新代入T：
m 次迭代后。我们什么时候停止？假设停止条件为n = 1:
因此最后的结果是：
一些数值测试证实了这个结果：
N T(N)
---------------------
1000 262143000
2000 1048574000
3000 3145725000
4000 8388604000
5000 20971515000
6000 25165818000
7000 29360121000
8000 67108856000
9000 75497463000
10000 83886070000
对数对数图：
该图的梯度 m 是 T(N) = ϴ(N^m)。结果 m = 2.70562 与 2.70951.