这个递归关系是 O(infinity) 吗？
Is this recurrence relation O(infinity)?
这个递归关系是O(infinity)吗？
T(n) = 49*T(n/7) + n
没有给出基本条件。
我尝试使用大师定理求解，答案是 Theta(n^2)。但是当用递归树求解时，解变成一个无限级数，n*(7 + 7^2 + 7^3 +...)
有人可以帮忙吗？
通常，当没有为递归关系提供基本情况时，假设基本情况是 T(1) = 1 或类似的东西。这样，递归最终终止。
需要考虑的事情 - 如果递归树无限深，则只能从递归树中获得无限级数。尽管问题中没有指定基本情况，但您可以假设有一个基本情况，并且当输入对于 "sufficiently small." 的某些定义足够小时递归停止基于此，递归在什么时候开始停止？从那里，您应该能够将无限级数转换为有限长度的级数，然后会给您答案。
希望对您有所帮助！
如果你尝试递归方法：
T(n) = 7^2 T(n/7) + n = 7^2 [7^2 T(n/v^2) + n/7] + n = 7^4 T(n/7^2) + 7n + n
= ... = 7^(2i) * T(n/7^i) + n * [7^0 + 7^1 + 7^2 + ... + 7^(i -1)]
当 i 增长时 n/7^i 更接近 1 并且如另一个答案中所述，T(1) 是一个常数。所以如果我们假设 T(1) = 1，那么：
- T(n/7^i) = 1
- n/7^i = 1 => i = log_7 (n)
所以
T(n) = 7^(2*log_7 (n)) * T(1) + n * [7^0 + 7^1 + 7^2 + ... + 7 ^(log_7(n)-1)]
=> T(n) = n^2 + n * [1+7+7^2+...+(n-1)] = n^2 + c*n = theta(n^ 2)
让n = 7^m。循环变成
T(7^m) = 49 T(7^(m-1)) + 7^m,
或
S(m) = 49 S(m-1) + 7^m.
同质部分给出
S(m) = C 49^m
一般的解决方案是
S(m) = C 49^m - 7^m / 6
即
T(n) = C n² - n / 6 = (T(1) + 1 / 6) n² - n / 6.
这个递归关系是O(infinity)吗？
T(n) = 49*T(n/7) + n
没有给出基本条件。
我尝试使用大师定理求解，答案是 Theta(n^2)。但是当用递归树求解时，解变成一个无限级数，n*(7 + 7^2 + 7^3 +...) 有人可以帮忙吗？
通常，当没有为递归关系提供基本情况时，假设基本情况是 T(1) = 1 或类似的东西。这样，递归最终终止。
需要考虑的事情 - 如果递归树无限深，则只能从递归树中获得无限级数。尽管问题中没有指定基本情况，但您可以假设有一个基本情况，并且当输入对于 "sufficiently small." 的某些定义足够小时递归停止基于此，递归在什么时候开始停止？从那里，您应该能够将无限级数转换为有限长度的级数，然后会给您答案。
希望对您有所帮助！
如果你尝试递归方法：
T(n) = 7^2 T(n/7) + n = 7^2 [7^2 T(n/v^2) + n/7] + n = 7^4 T(n/7^2) + 7n + n
= ... = 7^(2i) * T(n/7^i) + n * [7^0 + 7^1 + 7^2 + ... + 7^(i -1)]
当 i 增长时 n/7^i 更接近 1 并且如另一个答案中所述，T(1) 是一个常数。所以如果我们假设 T(1) = 1，那么：
- T(n/7^i) = 1
- n/7^i = 1 => i = log_7 (n)
所以
T(n) = 7^(2*log_7 (n)) * T(1) + n * [7^0 + 7^1 + 7^2 + ... + 7 ^(log_7(n)-1)]
=> T(n) = n^2 + n * [1+7+7^2+...+(n-1)] = n^2 + c*n = theta(n^ 2)
让n = 7^m。循环变成
T(7^m) = 49 T(7^(m-1)) + 7^m,
或
S(m) = 49 S(m-1) + 7^m.
同质部分给出
S(m) = C 49^m
一般的解决方案是
S(m) = C 49^m - 7^m / 6
即
T(n) = C n² - n / 6 = (T(1) + 1 / 6) n² - n / 6.