使用归纳发现复杂性
finding complexity using induction
我被要求证明：
对于每个n>=n0和T(n) = T(an) + T(bn) + n对于n>n0，a+b<1，其复杂度为T(n) = O(n)。
提示：通过归纳法证明：T(n) ≤ cn 对于合适的 c.
我想知道在这种情况下如何通过归纳法证明。
谢谢。
如果我们假设 an 和 bn 的不等式成立，那么
现在我们不知道这个常数和c之间的确切关系；但是如果我们看一下
的情况
但是 a + b 可以任意接近 1，这意味着 c 可以任意大。这有点违背 O-notation 的观点，因为常数必须是有限的。因此我们取下限：
因此我们找到了 c 的范围，在该范围内假设可以成立。 1 的下限是因为您的域 n >= n0 表示 T(n0) = n0。这里常数为 1，因此 c 必须至少为 1 才能满足假设的初始界限。这也将 a 和 b 的值限制为正数。
但要使假设为真，a, b 可以在 [0, 1) 中取 任何 值，这意味着如果 [=23] 的边界是正确的=] 那么它对于任何更大的参数也是正确的，例如 T(n + 1).
所以我们知道：
n = n0- 如果
n 为真那么 n + 1 也为真
因此，通过归纳，T(n) <= cn 对于任何 n >= n0，其中 c 满足之前的界限。
我被要求证明：
对于每个n>=n0和T(n) = T(an) + T(bn) + n对于n>n0，a+b<1，其复杂度为T(n) = O(n)。
提示：通过归纳法证明：T(n) ≤ cn 对于合适的 c.
我想知道在这种情况下如何通过归纳法证明。
谢谢。
如果我们假设 an 和 bn 的不等式成立，那么
现在我们不知道这个常数和c之间的确切关系；但是如果我们看一下
但是 a + b 可以任意接近 1，这意味着 c 可以任意大。这有点违背 O-notation 的观点，因为常数必须是有限的。因此我们取下限：
因此我们找到了 c 的范围，在该范围内假设可以成立。 1 的下限是因为您的域 n >= n0 表示 T(n0) = n0。这里常数为 1，因此 c 必须至少为 1 才能满足假设的初始界限。这也将 a 和 b 的值限制为正数。
但要使假设为真，a, b 可以在 [0, 1) 中取 任何 值，这意味着如果 [=23] 的边界是正确的=] 那么它对于任何更大的参数也是正确的，例如 T(n + 1).
所以我们知道：
n = n0 的假设成立
- 如果
n为真那么n + 1 也为真
因此，通过归纳，T(n) <= cn 对于任何 n >= n0，其中 c 满足之前的界限。