基数转换的计算复杂度

Question

将一个非常大的n位数转换为十进制表示的复杂度是多少？

我的想法是，重复整数除法的初级算法，通过取余数来获得每个数字，其复杂度为O(M(n)log n)，其中M(n)是乘法算法的复杂度；然而，这里的除法不是在两个n位数之间进行，而是在一个n位数和一个小常数之间进行，因此我认为复杂度可能会更小。

- Tanner

---

@xdavidliu：计算一个大整数除以10的商和余数，没有必要花费O(M(n))的时间。线性时间就足够了。 - tmyklebu

@tmyklebu 不用在意，是的那是正确的。 - xdavidliu

Answer 1

你描述的简单进制转换需要二次时间；你需要进行约n次大整数除以小整数的操作，其中大多数操作的时间与n位大整数大小成线性关系。

然而，你可以通过选择一个目标基数的幂次作为大约要转换数字的平方根，在O(M(n) log(n))时间内完成基数转换。通过对其进行除法和余数运算（可以通过牛顿法在O(M(n))时间内完成），并在两个子集上递归。

- tmyklebu

---

除以2的时间复杂度为O(1)是怎么实现的？难道不需要移位操作吗？ - G. Bach

@G.Bach，我认为这里的想法是，如果你将数字表示为按小端位顺序排列的位列表，那么你可以使用“drop 1”来进行除以2的操作。 - dfeuer

@tmyklebu（我刚刚删除了我的评论，那是不正确的）我错误地假设所有的除法，即使在更深层次的递归中也是作用于顶层n的单个字，因此即使对于大小为n/2、n/4等输入，也需要M(n)时间。事实上，更深层次的除法是作用于更小的输入尺寸，这一点对我来说并不清楚。 - xdavidliu

有没有人能提供一个这个 O( M(n) log(n) ) 算法的论文或具体实现的链接？ - Meekohi

@Meekohi 请尝试使用此链接，第14页。 - Lev Knoblock