（编辑：我的问题被标记为重复的question已在我的原始帖子中链接，甚至在标记之前，我认为不足以回答我的具体问题，为什么如何在不制作的情况下获得某种复杂性关于未知功能的任何假设。）
我正在尝试解决CLRS中的练习（Cormen Intro to Algorithms，3ed）。练习内容如下：
给出一种有效的算法，将给定的β位（二进制）整数转换为十进制表示。认为如果长度最多为β的整数的乘法或除法需要时间M（β），那么我们可以在时间Θ[M（β）lgβ]中将二进制转换为十进制。 （提示：使用分而治之的方法，通过单独的递归获得结果的上半部分和下半部分）。
这个问题已被问及here和here。然而，那里的答案要么做出错误的假设，例如M（β）= O（β），要么给出答案完全忽略了问题的要求。另一个答案here甚至明确地陈述了Θ[M（β）lgβ]结果，但解释是非常手动的，好像结果是显而易见的：
你可以在O（M（n）log（n））时间进行基本转换，但是，通过选择目标基数的功率，该功率大致是待转换数的平方根，通过以下方式进行除法和余数：它（可以通过牛顿方法在O（M（n））时间内完成），并在两半上递归。
这个解释对我来说并不完全清楚：没有对M（n）做任何假设，这样的递归会导致O（M（n）n）时间，而不是O（M（n）log（n））。 （编辑：我的问题已被标记为该线程的副本，但我已经在我的原始帖子中包含了该线程的链接，之后它被标记为重复，因为我觉得该线程的答案没有充分解决问题我很困惑）。
据我所知，问题在于每个乘法，商和余数运算都需要一个恒定的时间M，它支配其他所有类型的操作，例如加法。因此，主导项M（β）lgβ仅来自仅执行lgβ乘法和除法。
但是，我无法想出任何只需要lgβ分区的东西。例如，如果我们从问题中得到提示，我们可以在伪代码中提出以下分而治之算法。
decimal(x, start, end, n):
digits = end - start + 1 // assume power of 2
if digits == 1:
x[start] = n // 1-based index
else:
t = 10^(digits/2) // assume negligible time
quotient, remainder = n / t // takes M time
decimal(x, start, start+digits/2-1, quotient)
decimal(x, start+digits/2, end, remainder)
为了简单起见，在d位数字n上调用decimal(x,1,d,n)，d为2的幂，将in的十进制表示放在size-d数组x中。假设行quotient, remainder = n / t，占用时间M并支配运行时中的其他所有内容，运行时递归为T（β）= 2T（β/ 2）+ M，其具有解T（β）=Θ（βM），而不是Θ（Mlgβ）。
我对这个问题的理解是否正确？如果是这样，如何仅使用Θ（lgβ）乘法和/或除法来获得十进制表示？
The following page by a very well-known StackOverflow user讨论了这个问题。特别是：
二进制 - >基数：二进制 - >基数转换相同但反过来。从基数16中的N位数字X开始。您希望将其转换为基数b中的M位数字R.计算：高=楼层（X / bM / 2）。计算：低= X - bM / 2 *高。递归转换低和高。附加结果。最终结果R将是转换为基数b的原始数字。
但是，我仍然没有看到这是如何O（lg B）乘法;如果你在两半上递归，你可以根据定义访问递归树中的每个节点，因此有O（B）乘法！
布伦特，which can be seen here的现代计算机算术的第55页，共239页，也讨论了“次级二次算法”，并提到了M（β）lgβ划分和征服算法。但是，我仍然对lgβ来自何处无能为力。同样，如果你分裂和征服，并在两个部分进行递归，那么运行时至少是线性的，而不是对数的！在该书的第23页，共239页，提供了以下算法（略有释义）：
Algorithm 1.26 FastIntegerOutput
Input: A = (sum 0 to n-1) a_i 2^i
Output: a string S of characters, representing A in based 10
if A < 10 then
return char(A)
else
find k such that 10^(2k-2) <= A < 10^(2k)
(Q, R) = DivRem(A, 10^k)
r = FastIntegerOutput(R)
return concatenate(FastIntegerOutput(Q), zeros(k-len(r)), r)
布伦特声称：
如果输入A有n个单词，则算法FastIntegerOutput具有复杂度O（M（n）log n）
但同样，我不知道这是怎么可能的，因为(Q, R) = DivRem(A, B^k)线被称为O（n）次，而不是O（lg n）？
首先，要把它排除在外：就我所知，我的问题的标题要求是什么，用对数的除法和乘法进行转换是不可能的;这只是我根据对阅读问题的误解而做出的假设。
我与教科书Modern Computer Arithmetic的作者通信，并且他们说算法确实称为分割Θ（β）次，而不是Θ（lgβ），并且在更深的递归级别，M确实作用于较小尺寸的参数，而不是在我的问题中我错误地假设的常数顶级β。特别地，树的顶级调用具有M（β/ 2），下一级具有2M（β/ 4），然后是4M（β/ 8）等，总共具有1gβ水平。只要M（β）=Ω（β），树总和就是O（M（β）lgβ），尽管通常不是Ω（M（β）lgβ），因此不是Θ（M（β）lgβ ）。例如，对于多项式M（β）=Θ（β^α），对于α= 1，树求和是Θ（βlgβ）=Θ（M（β）lgβ），并且Θ（β^α）= α> 1的Θ（M（β））。
因此，如果我们只假设M（β）=Ω（β），那么运行时将更准确地描述为O（M（β）lgβ），而不是如CLRS练习中的Θ（M（β）lgβ） 。 （在我与现代计算机算术的一位作者的对应中，他们认为CLRS意味着“提供一种有效的算法”意味着假设M（β）是线性的或拟线性的，但CLRS通常对我们假设的假设非常明确。制作，并且“给出一个有效的算法”只是一个通用的短语，他们经常在文本中使用练习和问题，所以我觉得这可能是CLRS的一个小错字。
更新：我向CLRS errata page提交了这个小修正，现在它已经启动：
第933页，练习31.1-13。添加M（β）=Ω（β）的限制，并将期望的时间界限从θ（M（β）lgβ）改变为O（M（β）lgβ）。刘大卫报道。发布于2017年12月25日。严重程度：3在第三版的第八次印刷中予以纠正。