CLRS算法书的问题31.1-12要求以下问题:给定一个β位(二进制)整数,提供一种有效的算法将其转换为十进制表示。如果长度不超过β的整数的乘法或除法需要时间M(β),则可以证明二进制到十进制的转换可以在Θ(M(β)lg β)时间内完成。(提示:使用分治方法,通过单独递归获得结果的顶部和底部。它要求时间Θ(M(β)lg β)。如何通过分治算法实现这个目标,因为仅lg β就是递归树的高度?有人知道预期解决方案吗?
为了使提示起作用,必须满足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 = u-v·10ᵈ。