转换带10^6个数字的十进制数到它的二进制表示

Question

是否有可能非常大的十进制数（含d位）二进制表示转换在O（d）时间？

这里d = log（n），其中d是十进制数中的数字，即：例如10^6。所以这个数字明显小于10 ^（10^6）。

如果有一个算法，需要O（d）或O（d ^Ç）步骤。请分享。其中d是十进制数中的位数。

Answer 1

O（d）没有一个。

证明（不严格）：

甲十进制数可写成的总和超过x(k)*10^kk，其中x(k)是k个数位（起始于至少显著数字）。

10由两个因子2和5组成。2是一个简单的位移，但是5具有2位设置。这样做的结果是，在添加数字k时必须加以处理的位数不受任何常数的限制。对于任何konstant m，有一个k，使得1*10^k中的非零位数大于m。

因此，每位数字所需的（最大）工作量将不会保持不变，随着k的增加，它将增加。