作业1：(对应算法基础部分，25分) 已知T(n)=2T(n/2)+nlog₂n,且T(1)=1,求T(n)的时间复杂度。

根据主定理（Master Theorem），可以解出该递归式的时间复杂度为 O(nlog₂n)。具体证明如下：

将递归式 T(n) = 2T(n/2) + nlog₂n 转化为通用形式 T(n) = aT(n/b) + f(n)，其中 a = 2，b = 2，f(n) = nlog₂n。那么有：

- 当 f(n) = O(n^(log_ba-ϵ))，其中 ϵ > 0 时，T(n) = Θ(n^(log_ba))。因为 log₂2 = 1，所以 log_ba = 1。又因为 nlog₂n = O(n^1)，所以 f(n) = O(n^(log_ba-ϵ))，即 f(n) = O(n^(1-ϵ))。因此，T(n) = Θ(nlog₂n)。
- 当 f(n) = Θ(n^(log_ba)) 时，T(n) = Θ(n^(log_ba) * logn)。因为 log₂2 = 1，所以 log_ba = 1。又因为 f(n) = Θ(nlog₂n) = Θ(n^(log_ba) * logn)，所以 T(n) = Θ(nlog₂n * logn)。
- 当 f(n) = Ω(n^(log_ba+ϵ))，其中 ϵ > 0 时，T(n) = Θ(f(n))。因为 nlog₂n = Ω(n^(1+ϵ))，所以 f(n) = Ω(n^(log_ba+ϵ))，即 f(n) = Ω(n^(1+ϵ))。根据主定理第三种情况，T(n) = Θ(nlog₂n)。

综上所述，T(n) 的时间复杂度为 O(nlog₂n)。