algorithm - 递归关系归纳证明

Question

我正在分析不同的方法来查找算法的时间复杂度，并且在尝试通过使用归纳证明来解决这种特定的递归关系时遇到了很多困难。

我的 RR 是：T(n) <= 2T(n/2) + √n

我假设你会假设 n 并证明 n-1？有人可以帮我吗。

Answer 1

让我们假设 T(0) = 0, T(1) = 1 （因为你没有给出任何微不足道的情况）。因此，我们有：T(2) = 3.41，T(4) = 8.82，T(6) = 14.57，T(8) = 20.48，T(10) = 26.51。这似乎是一个线性函数。

所以，我们可以假设T(n) <= C * n + o(n).

这可以通过归纳来证明。假设T(k) <= C*(k) + o(k) = C*(k) + o(n).每个k<n.

我们应该证明T(n) <= C*n + o(n). 使用递归，T(n) <= 2*T(n/2) + sqrt(n) <= 2*(C*(n/2) + o(n)) + sqrt(n) = C*n + (2*o(n) + sqrt(n)) = C*n + o(n)。

因此，我们证明T(n) <= C*n + o(n)了 ，这保证了T(n)至少O(n)。

此外，可以证明 的解T(x) = 2T(x/2) + sqrt(x), T(0)=0, T(1)=1是T(x) = (2x-sqrt(2x))/(2-sqrt(2))。

Answer 2

如果使用归纳法来证明，那么假设对 K 成立并证明 2*k 或 2^k。

首先，检查 T(1)：

T(1) <= 2T(1/2) + √n

（假设 T(1/2) = 1) T(1) = 2 + √n <= O(√n log n)

现在，假设 T(k) 为真。

=> T(k) <= O(√n log n) T(k) <= 2T(k/2) + √n <= c(√n log n)

证明，T(2k)：

T(2k) <= 2T(2k/2) + √(2k)
=> T(2k) <= 2(c(√k log k) + √(2k)
=> T(2k) <= √2 * [2(c(k log k) + √(2k)] //(不等式如下)
=> T(2k) <= [c'(2k log 2k)] => T(2k) <= O(√n登录 n)

增长率：

(c < log n < log2n < √n < n < n log nn < n log n < n(1.1) < n2 < n3 < n4 < 2n)