这个问题是在考试中出现的,我不知道该怎么做,任何人都可以帮助我或给点提示。我觉得大师的方法在这里不适用?请帮忙。
T(n)=T(n/2)+ θ(logn)
这个问题是在考试中出现的,我不知道该怎么做,任何人都可以帮助我或给点提示。我觉得大师的方法在这里不适用?请帮忙。
T(n)=T(n/2)+ θ(logn)
假设n
是 的幂2
,n = 2^k
为简单起见,假设对数基数T(n) = T(n/2) + lg(n)
在哪里,而。lg
2
T(1) = lg(1) = 0
T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1)
= lg(2^k) + lg(2^{k-1}) + ... + lg(2^0)
= k.lg(2) + (k-1)lg(2) + ... + 0.lg(2)
= (k + (k-1) + ... + 0) lg(2)
= k(k+1)/2
= lg(n)(lg(n)+1)/2
= Theta(lg(n)^2).
对于n
不是 的幂2
,可以注意到它T
是一个递增函数,所以T(2^k) <= T(n) <= T(2^{k+1})
在哪里k = floor(lg(n))
。从上面的确切结果,我们得到
k(k+1)/2 <= T(n) <= (k+1)(k+2)/2
所以
T(n) = Theta(floor(lg(n))^2) = Theta(lg(n)^2)