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

问题描述

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

它要求时间Θ（M（β）lgβ）。考虑到 lgβ到底是递归树的高度吗？有人知道目标解决方案是什么吗？

解决方案

要使提示起作用，必须是M（β）是线性函数的情况；尤其是M（β）≈2·M（β/ 2）。

如果给出的话，有一个明显的解决方案：将数据递归拆分为多个部分，分别处理各个部分，然后组合结果，在递归的k层将有2个部分，每个部分的长度大约β/（2ᵏ）位，或总共约β。在级别k处的处理总时间为2ᵏ·M（β/（2ᵏ））≈M（β），而总时间为O（M（β）·lgβ）。 / p>

要用β位拆分值u并处理其两个部分（v，w），则令2·d或2 ·d + 1 ＝⌊β·ln（2）/ ln（10）⌋；令v =⌊u/10ᵈ⌋和w = u-v·10ᵈ。

Problem 31.1-12 of the CLRS algorithms book asks the following question:

It asks for time Θ( M(β) lg β). How is that even possible for a divide and conquer algorithm given that lg β alone is the height of the recursion tree? Does anyone know what the intended solution is?

解决方案

For the hint to work, it must be the case that M(β) is a linear function; in particular, that M(β) ≈ 2·M(β/2).

If that is given, there is an obvious solution: Recursively split the data into parts, process the parts separately, and combine the results. At level k of the recursion there will be 2ᵏ parts, each of length approximately β/(2ᵏ) bits, or about β total. The processing at level k costs 2ᵏ·M(β/(2ᵏ)) ≈ M(β), whence O(M(β)·lg β) total time.

To split a value u with β bits and process its two parts (v,w), let 2·d or 2·d+1 = ⌊β·ln(2)/ln(10)⌋; let v = ⌊u/10ᵈ⌋ and w = u-v·10ᵈ.

这篇关于将整数转换为十进制的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！