基本转换的计算复杂性

Question

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

我的想法是,重复整数除法的基本算法,取余数来得到每个数字,将具有O(M(n)log n)复杂性,其中M(n)是乘法算法的复杂性; 然而,除法不是在2个n位数之间,而是1个n位数和一个小常数,因此在我看来复杂性可能更小.

Answer 1

正如您所描述的，朴素的碱基转换需要二次时间；你要做的是nbigint-by-smallint 除法，其中大部分所花费的时间与 n 位 bigint 的大小成线性关系。

但是，您可以在 O(M(n) log(n)) 时间内完成基数转换，方法是选择目标基数的幂，该幂大约是要转换的数字的平方根，然后通过以下方式进行除法和余数它（可以通过牛顿法在 O(M(n)) 时间内完成），并在两半上递归。