作业1：(对应算法基础部分，25分) (1)证明O(f)O(g)=O(fg) (2)已知T(n)=2T(n/2)+nlog₂n,且T(1)=1,用拓展递归求T(n)的时间复杂度。

(1) 证明O(f)O(g)=O(fg)：

我们需要证明对于任意的函数f(n)，g(n)，总存在一个常数C和一个正整数N，使得当n>N时，有f(n)g(n)<=Cf(n)g(n)。

假设当n>N时，f(n)<=C1g(n)，g(n)<=C2f(n)，那么f(n)g(n)<=C1C2f(n)g(n)，即可得证。

因此，O(f)O(g)=O(fg)。

(2) 已知T(n)=2T(n/2)+nlog₂n，且T(1)=1，用拓展递归求T(n)的时间复杂度：

我们可以使用拓展递归展开的方法来求解递归式T(n) = 2T(n/2) + nlog₂n。

首先，我们将递归式展开成如下形式：

T(n) = 2T(n/2) + nlog₂n

= 2(2T(n/4) + (n/2)log₂(n/2)) + nlog₂n

= 2^2T(n/4) + nlog₂n

+ nlog₂(n/2)

= 2^2(2T(n/8) + (n/4)log₂(n/4)) + nlog₂n

+ nlog₂(n/2)

= 2^3T(n/8) + nlog₂n

+ nlog₂(n/2)

+ nlog₂(n/4)

= ...

= 2^kT(n/2^k) + nlog₂n

+ nlog₂(n/2)

+ nlog₂(n/4)

+ ...

+ nlog₂(n/2^k)

当n/2^k = 1时，即k = log₂n，所以：

T(n) = 2^log₂nT(1) + nlog₂nlog₂n

+ nlog₂(n/2)

+ nlog₂(n/4)

+ ...

+ nlog₂(n/2^(log₂n))

= n + nlog₂nlog₂n

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