作业1：(对应算法基础部分，25分) (1)证明O(f)O(g)=O(fg) (2)已知T(n)=2T(n/2)+n/og₂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)+n/og₂n，且T(1)=1，求T(n)的时间复杂度：

根据主定理，可以得到T(n)的时间复杂度为O(nlog₂n)。

具体步骤如下：

首先，我们将T(n)表示为递归式形式：T(n) = 2T(n/2) + n/og₂n

然后，我们可以得到a=2，b=2，f(n)=n/og₂n

根据主定理的第二种情况，当f(n) = Θ(n^log₂2)时，T(n)的时间复杂度为O(n^log₂2 * logn)。

因为当n/og₂n = 1时，T(n) = 1，因此，n/og₂n = 2^k时，T(n) = k。

所以，n/og₂n = 2^k，即k = log₂n，因此，T(n)的时间复杂度为O(nlog₂n)。