基本转换的计算复杂度 [英] Computational complexity of base conversion

问题描述

将非常大的n位数字转换为十进制表示法的复杂性是什么？

What is the complexity of converting a very large n-bit number to a decimal representation?

我的想法是重复整数除法的基本算法采用取每个数字的余数，将具有 O（M（n）log n）的复杂度，其中 M（n）是乘法算法的复杂度；但是，除法不是在2个n位数字之间，而是在1个n位数字和一个小的常数之间进行，因此在我看来，复杂度可能会较小。

My thought is that the elementary algorithm of repeated integer division, taking the remainder to get each digit, would have O(M(n)log n) complexity, where M(n) is the complexity of the multiplication algorithm; however, the division is not between 2 n-bit numbers but rather 1 n-bit number and a small constant number, so it seems to me the complexity could be smaller.

推荐答案

您所描述的朴素的基本转换需要二次时间；您需要处理 n bigint-by-smallint除法，大多数除法时间与n位bigint的大小成线性关系。

Naive base-conversion as you described takes quadratic time; you do about n bigint-by-smallint divisions, most of which take time linear in the size of the n-bit bigint.

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

You can do base conversion in O(M(n) log(n)) time, however, by picking a power of target-base that's roughly the square root of the to-be-converted number, doing divide-and-remainder by it (which can be done in O(M(n)) time via Newton's method), and recursing on the two halves.

这篇关于基本转换的计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！