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

相关问题

证明o(f)o(g)=o(fg)算法

对于证明 o(f) o(g) = o(fg)，我们可以使用大O符号的定义来进行推导。

根据大O符号的定义，如果存在正常数 c 和 n0，使得对于所有 n > n0，有 f(n) ≤ c · g(n)，那么我们可以说 f(n) 是 o(g(n))。

假设 f(n) 是 o(g(n))，即存在正常数 c1 和 n1，使得对于所有 n > n1，有 f(n) ≤ c1 · g(n)。

现在我们来考虑 o(f) o(g)。根据函数复合（composition）的定义，o(f) o(g) 表示的是一个函数 h(n)，使得对于任意正常数 c2 和 n2，存在一个正常数 m，使得对于所有 n > m，有 h(n) ≤ c2 · f(g(n))。

我们将 h(n) 替换为 f(g(n))，即考虑 f(g(n)) ≤ c2 · f(g(n))。由于 f(n) 是 o(g(n))，我们可以取 c2 = c1，并且对于所有 n > max(n1, n2)，有 f(g(n)) ≤ c1 · g(g(n))。

因此，我们可以得出结论：o(f) o(g) = o(fg)。

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