algorithm - 如何在递归中找到 T(n) 的渐近上界？

Question

我想知道如何准确找到 T(n) 的严格上限？对于下面的一个例子:

T(n)=T( n/2 + n^(1/2)) + n.

我不太确定如何在这里使用域或范围转换。

我在这里使用域转换。

让

n = 2^2k ==> n/2 = 2^2k-1and n^1/2 = 2^2k-1

在那之后，我不知道如何用T(n)中的加法来解决这种问题。希望有人能告诉我如何解决这些重复出现的问题。

谢谢 Ali Amiri，按照你说的，我大概考虑一下。

T(n)=T( n/2 ) + n.

让，

n = 2^k,

==> T(2^k)= T(2^k-1)+ 2^k

假设a_k = T(2^k)

使用域变换，我得到:

a_k = 2^kc₁ + c₂

因此，

T(n) = O(n).

我说的对吗？还是错了？

Answer 1

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)。