algorithm - 碱基转换的计算复杂度

Question

将非常大的 n 位数字转换为十进制表示的复杂性如何？

我的想法是，重复整数除法的基本算法，取余数得到每个数字，将具有 O(M(n)log n) 复杂度，其中 M(n )是乘法算法的复杂度；但是，除法不是在 2 个 n 位数字之间，而是在 1 个 n 位数字和一个小常数之间，所以在我看来，复杂度可能会更小。

Answer 1

如您所述，朴素的基础转换需要二次方时间；您执行 n bigint-by-smallint 划分，其中大部分时间与 n 位 bigint 的大小成线性关系。

但是，您可以在 O(M(n) log(n)) 时间内进行基数转换，方法是选择目标基数的幂，它大致是待转换数的平方根，进行除法- 余数(可以通过牛顿法在 O(M(n)) 时间内完成)，并在两半上递归。