algorithm - 特定分治算法的复杂性

Question

一种算法将大小为 n 的问题分解（划分）为 b 个大小为 n/b 的子问题，其中 b 是整数。分解成本为n，C(1)=1。使用重复替换证明，对于所有 2≥b 的值，算法的复杂度为 O(n lg n)。

这就是我用于初始方程 C(n) = C(n/b) + n 的内容，经过 k 步替换后，我得到 C(n) = C(n/b^k) + n [summation(from i=0 到 k-1) 的 (1/b)^i]

k = log(base b) n

我不确定我是否做对了所有这一切，因为当我完成此操作时，我没有得到 n lgn，任何人都可以帮我弄清楚该怎么做？

Answer 1

我认为你的重复是错误的。由于有 b 个大小为 n/b 的单独子问题，因此在 C(n / b) 项之前应该有一个 b 的系数。复发应该是

C(1) = 1

C(n) = b C(n/b) +O(n)。

使用主定理，这解决了 O(n log n)。另一种看待这一点的方式是，在将递归 k 次扩大后，我们得到

C(n) = b ^k C(n / b ^k ) + kn

_{这在 k = log b} n时终止。代入 k 的值并进行化简，得到 O(n log n) 的值。

希望这可以帮助！