CLRS算法书的问题31.1-12要求以下问题：给定一个β位（二进制）整数，提供一种有效的算法将其转换为十进制表示。如果长度不超过β的整数的乘法或除法需要时间M(β)，则可以证明二进制到十进制的转换可以在Θ(M(β)lg β)时间内完成。（提示：使用分治方法，通过单独递归获得结果的顶部和底部。它要求时间Θ(M(β)lg β)。如何通过分治算法实现这个目标，因为仅lg β就是递归树的高度？有人知道预期解决方案吗？
1个回答
0
为了使提示起作用，必须满足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ᵈ。
- James Waldby - jwpat7
1
我认为这本书实际上建议将M视为常数，因此我们需要通过lg B次乘法进行转换。这个答案仍然需要2^k ~ O(B)次乘法，所以可能不是该书寻找的答案。假设加法比乘法便宜得多，使得乘法的成本支配它们。 - xdavidliu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接