基数转换的计算复杂度

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

我的想法是，重复整数除法的基本算法，其余部分得到每个数字，将有复杂性，其中M(n)是乘法算法的复杂性;然而，这种划分不是在2个n位数之间，而是在1个n位数和一个小常数之间，所以在我看来复杂度可能更小。

2015-02-09 Tanner

@xdavidliu：不需要花O（M（n））时间计算一个大整数的商和余数10，线性时间就足够了。 – tmyklebu 2017-12-23 14:59:55

@tmyklebu没关系，是的，这是正确的 – xdavidliu 2017-12-23 15:15:43

您所描述的朴素碱基转换需要二次时间;你可以做一些bigint-by-smallint分区，其中大部分需要时间与n位bigint的大小成线性关系。

您可以在O（M（n）log（n））时间内进行基础转换，但是，通过选择大致为要转换的数字的平方根的目标基础的力量，（它可以通过牛顿方法在O（M（n））时间完成），并在两半上递归。

2015-02-09 20:13:11 tmyklebu

我想我的问题是否由小数分割可以在线性时间O（n）或更少。例如，除以2或4是平凡的O（1）;有没有一个O（n）算法除以10？ – Tanner 2015-02-09 20:37:06

如何除以2 O（1）？你必须移动所有的位，不是吗？ – 2015-02-09 20:53:24

@坦纳，是的，任何固定除数除以O（n），其中n是股息的长度。只需使用通常的长分法算法即可。允许任意的除数改变一切。 – dfeuer 2015-02-09 20:53:25

回答