我有一个问题。
在我的书中，他们有以下递归：
T(n) = 3*T(floor(n/4))+theta(n^2)
他们尝试猜测 T(n) = O(n^2)，然后使用替换方法来验证猜测。但他们没有显示基本情况？没有必要吗？
我想也许是因为他们不知道当 n=1 时 T(n) 会发生什么。 ??
在我的书中，他们也有重复 T(n)=2*T(floor(n/2))+n 和 T(1)=1
然后他们猜测 T(n )=O(nlgn)
他们用替换法来验证它。
他们假设对于所有正 mT(n)=O(n lg n)
T(n) <= 2(c*floor(n/2)*lg(floor(n/2))+n
<= c*n*lg(n/2)+n
= c*n*lg(n)-c*n*lg(2)+n
= c*n*lg(n)-c*n+n
<= c*n*lg(n)-c*n+n
Where c>=1
是好的。然后他们说：“数学归纳法要求我们证明我们的解决方案适用于边界条件”，
T(1)<=c*1*lg(1)=0
这与 T(1)=1 不一致
，但随后他们利用渐近符号，只要求他们证明 T(n)<= c*n*lg(n) for n>=n0 他们选择 n0
然后他们用 T(2)=4 和 T( 3)=5为基数归纳证明中的情况让 n0=2
我的问题是：
为什么我必须用 T(2) AND T(3) 替换基本情况 T(1) ？为什么不直接将其替换为 T(2)=4
我可以从递归中导出 T(2)=4 然后说
T(2)<= c*2*lg(2) = c*2
Where c>=1 and I choose c>=2
为什么我必须考虑 T(3) ？
I have a question.
In my book they have the following recurrence:
T(n) = 3*T(floor(n/4))+theta(n^2)
They try to guess that T(n) = O(n^2) and they then use the substitution method to verify the guess. But they don't show the base case? Isn't that necessary?
I think maybe it is because they don't know what happen with T(n) when n=1. ??
In my book they also have the reccurence T(n)=2*T(floor(n/2))+n and T(1)=1
They then guess that T(n)=O(n lg n)
And they use the substitution method to verify it.
They assume that T(n)=O(n lg n) for all positive m<n
T(n) <= 2(c*floor(n/2)*lg(floor(n/2))+n
<= c*n*lg(n/2)+n
= c*n*lg(n)-c*n*lg(2)+n
= c*n*lg(n)-c*n+n
<= c*n*lg(n)-c*n+n
Where c>=1
Ok. They then say: "Mathematical induction requires us to show that our solution holds for the boundary conditions"
T(1)<=c*1*lg(1)=0
which is at odds with T(1)=1
but then they take advantage of asymptotic notation requiring them only to prove T(n)<= c*n*lg(n) for n>=n0 where they to choose n0
Then they replace T(1) by T(2)=4 and T(3)=5 as base cases in the inductive proof letting n0=2
And my question is:
Why do I have to replace the base case T(1) with T(2) AND T(3)? Why not just replace it with T(2)=4
I can derive T(2)=4 from the recurrence and then say
T(2)<= c*2*lg(2) = c*2
Where c>=1 and I choose c>=2
Why do I have to consider T(3) ?
发布评论
评论（1）
首先，如何评估T(6)？ T(6) = 2*T(下限(6/2)) + 6 => T(6) = 2*T(3) + 6 = 16。
其次，他们写道 - 在 n > 之后3，它变得独立于T(1) ...所以在1之后和4之前都应该作为基本情况给出。
这就是为什么我们也有 2 输入 T(3)。
请评论...
First, How to evaluate T(6)? T(6) = 2*T(floor(6/2)) + 6 => T(6) = 2*T(3) + 6 = 16.
Second, they have written that - after n > 3,it becomes independent of T(1) ... so after 1 and before 4 all should given as base cases.
That's why we have 2 enter T(3) also.
Please Comments...