我想知道如何准确找到T（n）的上限吗？下面的一个例子：
T（n）= T（n / 2 + n （1/2））+ n。
我不确定如何在此处使用域或范围转换。
我在这里使用域转换。
让
n = 2 2 k ==> n / 2 = 2 2 k -1和n 1/2 = 2 2 k-1
在那之后，我不知道如何用T（n）加法来解决这种问题。希望有人可以告诉我如何解决此类重复性问题。
谢谢阿里·阿米里（Ali Amiri），正如您所说，我会考虑一下。
T（n）= T（n / 2）+ n。
然后让，
n = 2的ķ，
==> T（2 k）= T（2 k-1）+ 2 k
假设k = T（2 k）
使用域变换，我得到：
a k = 2 k c 1 + c 2
因此，
T（n）= O（n）。
我对吗？还是错了？
阿里·阿米里（Ali Amiri）的直觉是正确的，但这不是正式的论据。确实需要一个基本案例
T(n) = 1 for all 0 ≤ n < 9
然后我们可以写
1/2
n ≤ n/3 for all n ≥ 9
然后猜测并检查O（n）递减的解决方案
T'(n) = T'(n/2 + n/3) + n
并认为T = O（T'）= O（n）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句