algorithm - 将整数转换为十进制的高效算法

Question

CLRS 算法书的问题 31.1-12 提出以下问题：

给出一个有效的算法将给定的β位（二进制）整数转换为十进制表示。论证如果最大长度为 的整数的乘法或除法β需要时间M(β)，则可以及时进行二进制到十进制的转换Θ( M(β) lg β)。（提示：使用分而治之的方法，通过单独的递归获得结果的上半部分和下半部分。

它要求时间Θ( M(β) lg β)。lg β考虑到递归树的高度，分而治之的算法怎么可能呢？有谁知道预期的解决方案是什么？

Answer 1

为了使提示起作用，M(β) 必须是线性函数；特别是，M(β) ≈ 2·M(β/2)。

如果给定了，那么有一个明显的解决方案：递归地将数据拆分为多个部分，分别处理这些部分，然后组合结果。在递归的第 k 层，将有 2ᵏ 个部分，每个部分的长度大约为 β/(2ᵏ) 位，或总共约为 β。第 k 层的处理花费 2ᵏ·M(β/(2ᵏ)) ≈ M(β)，因此总时间为 O(M(β)·lg β)。

用 β 位分割一个值 u 并处理它的两个部分 (v,w)，令 2·d 或 2·d+1 = ⌊β·ln(2)/ln(10)⌋；令 v = ⌊u/10ᵈ⌋ 和 w = uv·10ᵈ。