带循环的一阶线性递归（求和）
First Order Linear Recurrences with loops (summation)
我有以下复发：
T(n) = Σk=0n-1 T(k) + n + 3
我的教授说这可以简化为
T(n) = 2T(n - 1) + 1
这怎么可能？
这种简化是不正确的。这些重复会返回不同的值。
您没有为重复指定基本情况，因此我们假设基本情况是 T(0)。那么我们有
- T(0) = T(0)
- T(1) = T(0) + 1 + 3 = T(0) + 4
- T(2) = T(0) + (T(0) + 4) + 2 + 3 = 2T(0) + 9
- T(3) = T(0) + (T(0) + 4) + (2T(0) + 9) + 3 + 3 = 4T(0) + 19
- ...
- T(k) = 2kT(0) + 3k + k(k + 1) / 2
这与您从 T(n) = 2T(n - 1) + 1 获得的模式不匹配：
- T(0) = T(0)
- T(1) = 2T(0) + 1
- T(2) = 2(2T(0) + 1) + 1 = 4T(0) + 3
- T(3) = 2(4T(0) + 3) + 1 = 8T(0) + 7
- ...
- T(k) = 2kT(0) + 2k+1 - 1.
这么看来，要么是某处沟通不畅，要么是提供给您的答案不正确。
我有以下复发：
T(n) = Σk=0n-1 T(k) + n + 3
我的教授说这可以简化为
T(n) = 2T(n - 1) + 1
这怎么可能？
这种简化是不正确的。这些重复会返回不同的值。
您没有为重复指定基本情况，因此我们假设基本情况是 T(0)。那么我们有
- T(0) = T(0)
- T(1) = T(0) + 1 + 3 = T(0) + 4
- T(2) = T(0) + (T(0) + 4) + 2 + 3 = 2T(0) + 9
- T(3) = T(0) + (T(0) + 4) + (2T(0) + 9) + 3 + 3 = 4T(0) + 19
- ...
- T(k) = 2kT(0) + 3k + k(k + 1) / 2
这与您从 T(n) = 2T(n - 1) + 1 获得的模式不匹配：
- T(0) = T(0)
- T(1) = 2T(0) + 1
- T(2) = 2(2T(0) + 1) + 1 = 4T(0) + 3
- T(3) = 2(4T(0) + 3) + 1 = 8T(0) + 7
- ...
- T(k) = 2kT(0) + 2k+1 - 1.
这么看来，要么是某处沟通不畅，要么是提供给您的答案不正确。