我正在尝试解决以下重复问题: T(n) = T(n/3) + T(n/2) + sqrt(n) 我目前已完成以下操作，但不确定我是否在正确的轨道上:
T(n) <= 2T(n/2) + sqrt(n)
T(n) <= 4T(n/4) + sqrt(n/2) + sqrt(n)
T(n) <= 8T(n/8) + sqrt(n/4) + sqrt(n/2) + sqrt(n)
所以，n/(2^k) = 1，并且 sqrt 部分简化为:(a(1-r^n))/(1-r)
K = log2(n) 并且高度是 2^k，所以 2^(log2(n)) 但是:
我不确定如何将 2^(log2(n)) 的结果与 sqrt(n) 部分结合起来。
最佳答案
一个好的初始尝试是确定时间复杂度函数的上限 和下限。这些由:
这两个函数比 T(n) 本身更容易求解。考虑稍微更通用的函数:
我们什么时候停止递归？我们需要一个停止条件。由于未给出，我们可以假设它是 n = 1 而不失一般性(您会希望看到如何)。因此，术语的数量 m 由下式给出:
因此我们可以获得T(n)的上下界:
Can we do better than this? i.e. obtain the exact relationship between
nandT(n)?
来 self 之前的回答here ，我们可以推导出 T(n) 的二项式求和公式:
在哪里
C 使得 n = C 是 T(n) 的停止条件。如果没有给出，我们可以假设 C = 1 而不失一般性。
在您的示例中，f(n) = sqrt(n), c1 = c2 = 1, a = 3, b = 2。因此:
我们如何评估内和？考虑具有正指数 m 的二项式展开的标准公式:
这样我们将x,y替换为公式中对应的值，得到:
我们使用标准几何级数公式和对数规则到达最后两个步骤。请注意，指数与我们之前找到的边界是一致的。
一些数值测试来确认关系:
N T(N)
--------------------
500000 118537.6226
550000 121572.4712
600000 135160.4025
650000 141671.5369
700000 149696.4756
750000 165645.2079
800000 168368.1888
850000 181528.6266
900000 185899.2682
950000 191220.0292
1000000 204493.2952
log T(N) 对 log N 的绘图:
这样的图 m 的梯度是 T(N) ∝ N^m，我们看到 m = 0.863 , 非常接近 0.861 的理论值。
关于algorithm - 解决以下重现: T(n) = T(n/3) + T(n/2) + sqrt(n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46043058/