作业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)。

相关问题

作业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)。

作业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)。