T(n)={1,n=1 8T(n/2+O(nlogn)),n=1},求T(n)的时间复杂度并附带过程

根据递推式，可以写出T(n)的递归式：

T(n) = 8T(n/2) + O(nlogn)

利用递归树法，可以得到：

T(n) = O(nlogn) + 8O(n/2log(n/2)) + 64O(n/4log(n/4)) + ... + O(1)

因为log(x/y) = log(x) - log(y)，我们可以将上式简化为：

T(n) = O(nlogn) + 8O(n/2logn) + 64O(n/4logn) + ... + O(1)

T(n) = O(nlogn) + 4nlogn + 16nlogn + ... + nlogn

T(n) = O(nlogn) + nlogn(4 + 16 + ... + 2^k)

其中k为满足2^k <= n的最大整数。因为一个长度为n的链表，最多有n个结点，所以k = logn。

将等比数列求和得：

4 + 16 + ... + 2^k = 2^(k+1) - 4

代入原式得：

T(n) = O(nlogn) + nlogn(2logn - 4)

T(n) = O(nlogn) + nlog^2(n) - 4nlogn

因此，T(n)的时间复杂度为O(nlog^2(n))。

相关问题

T(n) = 2T(n/2) + nlogn的tight bound

通过主定理（Master Theorem），可得T(n)=O(nlogn)。因为a=2, b=2, f(n) = n^log_ba = n^log_22 = n。根据主定理，当f(n) = O(n^log_ba-ε)时，复杂度为O(n^log_ba)；当f(n) = Θ(n^log_ba)时，复杂度为O(n^log_ba * logn)；当f(n) = Ω(n^log_ba+ε)且af(n/b) <= cf(n)时，复杂度为O(f(n))。 因为n = Ω(n^ε)，且2(n/2) <= cn，所以满足上述条件。故复杂度为O(nlogn)。

T(n) = 2T(n/2) + nlogn的asymptotically tight bound

我们可用主定理（Master Theorem）来证明T(n) = 2T(n/2) 的时间复杂度为nlogn的asymptotically tight bound。

根据主定理，对于递归式T(n) = aT(n/b) + f(n)（其中a和b为常数，且f(n)为渐进正的函数）：

如果f(n) = O(n^log[b]a-ε) 对某个常数ε > 0，则T(n) = Θ(n^log[b]a)。
如果f(n) = Θ(n^log[b]a * logk n)，则T(n) = Θ(n^log[b]a * logk+1 n) 。
如果f(n) = Ω(n^log[b]a+ε) 对某个常数ε > 0，并且如果对某个常数c < 1和足够大的n，有af(n/b) ≤ cf(n)，则T(n) = Θ(f(n)) 。

在这里，a = 2，b = 2，f(n) = 0，因此f(n) = Θ(n^0)，即 f(n) = Θ(1)。

因为 f(n) = Θ(1) = Θ(n^0)，所以我们可以应用主定理的第一种情况来计算时间复杂度，即：

T(n) = Θ(n^log[b]a) = Θ(n^log[2]2) = Θ(nlogn)

证毕。