0

提前感谢您帮助解决这个问题。我正在上算法课，但我遇到了一些问题。根据教授的说法，当 C(1)=1 且 n 是 2 的幂时，以下情况成立：

C(n) = 2 * C(n/2) + n解决为C(n) = n * lg(n) + n

C(n) = 2 * C(n/2) + lg(n)解决为C(n) = 3 * n - lg(n) - 2

第一个我完全摸不着头脑。据我了解表格，所说的是 C(n) 解决了两个子问题，每个子问题都需要 n/2 工作来解决，以及额外的 n 工作量来拆分和合并所有内容。因此，对于问题的每个划分，常数 2 增加了 ^k 倍（其中 k 是分裂的数量），n/2 中的 2 也增加了 ^k 倍原因，最后一个 n 乘以 k 倍，因为每次拆分都会产生 k 倍的额外工作。

我的困惑源于第二个关系。鉴于第一个和第二个关系几乎相同，为什么第二个的结果不像 nlgn+(lgn^2)？

4

1 回答 1

2

一般结果是主定理

但在这种特定情况下，您可以计算出 2 的幂的数学：

C(2^k) 
= 2 * C(2^(k-1)) + lg(2^k) 
= 4 * C(2^(k-2)) + lg(2^k) + 2 * lg(2^(k-1))
= ... repeat ...
= 2^k * C(1) + sum (from i=1 to k) 2^(k-i) * lg 2^i
= 2^k + lg(2) * sum (from i=1 to k) 2^(i) * i
= 2^k - 2 + 2^k+1 - k
= 3 * 2^k - k - 2 
= 3 * n - lg(n) - 2
于 2013-10-06T04:05:11.413 回答