我可以找到每一行的总和(n/log n-i)
,也可以画出它的递归树,但我无法计算每一行的总和。
T(n)=2T(n/2)+n/logn
T(1) = 1
我可以找到每一行的总和(n/log n-i)
,也可以画出它的递归树,但我无法计算每一行的总和。
T(n)=2T(n/2)+n/logn
T(1) = 1
t(n) = 2t(n/2) + n/log(n)
= 2(2t(n/4) + n/2/log(n/2)) + n/log(n)
= 4t(n/4) + n/log(n/2) + n/log(n)
= 4(2t(n/8) + n/4/log(n/4)) + n/log(n/2) + n/log(n)
= 8t(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
= 16t(n/16) + n/log(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
= n * t(1) + n/log(2) + n/log(4) + ... + n/log(n/2) + n/log(n)
= n(1 + Sum[i = 1 to log(n)](1/log(2^i)))
= n(1 + Sum[i = 1 to log(n)](1/i))
~= n(1 + log(log(n)))
= n + n*log(log(n)))
~= n*log(log(n)) [n -> infinity]
T(1) = 1
,这意味着 n = 2^k
。代入后得到:
第二个求和式的行为与调和级数相同,因此可以近似为log(k)
。现在k = log(n)
,得出的答案是:
按照下面的扩展主定理进行操作。
使用扩展主定理T(n)=2T(n/2)+n/logn
可以轻松解决,具体如下。
这里n/logn
部分可以重写为n * (logn)^-1
,有效地使得p=-1。
现在可以轻松应用扩展主定理,它将与扩展主定理的第2b种情况有关。
T(n)= O(nloglogn)
请跟随以下内容获取更详细的解释