一种算法将大小为 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,任何人都可以帮我弄清楚该怎么做?