递推式Tn=Tn-1+logn的阶和Tn=4Tn/2的渐近界

对于递推式Tn = Tn-1 + logn，我们可以将其展开：

Tn = Tn-1 + logn
= Tn-2 + log(n-1) + logn
= Tn-3 + log(n-2) + log(n-1) + logn
= ...
= T1 + log2 + log3 + ... + log(n-1) + logn

我们可以看到，每一项都是log(i)，其中i从2到n递增。因此，我们可以将这个递推式的阶和表示为：

Tn = O(log2 + log3 + ... + log(n-1) + logn)

根据对数的性质，我们知道：

log2 + log3 + ... + log(n-1) + logn ≤ nlogn

因此，递推式的阶和可以渐进地表示为：

Tn = O(nlogn)

对于递推式Tn = 4Tn/2，我们可以将其展开：

Tn = 4Tn/2
= 4(4Tn/4)
= 4^2Tn/4^2
= 4^3Tn/4^3
= ...
= 4^(log2(n))T1

由于每次递归都将问题的规模减少一半，总共需要进行log2(n)次递归。因此，递推式的渐近界可以表示为：

Tn = O(4^(log2(n)))
= O(2^(2log2(n)))
= O(2^(log2(n^2)))
= O(n^2)

因此，递推式的渐近界为O(n^2)。