主题：超大十进制数转为二进制数，有无较快的算法？
eastcowboy
[专家分：25370] 发布于 2005-07-02 11:21:00
如题，传统的除二取余，时间复杂度似乎高了点。
回复列表 （共19个回复）
11 楼
boxertony [专家分：23030] 发布于 2005-09-14 19:05:00
大家想得太简单了。举个例子，假设一个10000位的十进制整数，放在一个数组中，每个元素存放一位。要算得第一个余数需要对每个元素都除以一次2，即10000次。这时商为10000位或9999位（取小的吧，9999）（注意，商可不是5000位）。那么要算得第二个余数需要除以9999次，依次类推，算得所有的余数需要的除法次数为：
10000+9999+...+2+1 约等于50000000。所以该算法的时间复杂度可不是楼主说的log2(n)*log10(n)，而是O(n^2)
12 楼
boxertony [专家分：23030] 发布于 2005-09-14 19:07:00
大家想得太简单了。举个例子，假设一个10000位的十进制整数，放在一个数组中，每个元素存放一位。要算得第一个余数需要对每个元素都除以一次2，即10000次。这时商为10000位或9999位（取小的吧，9999）（注意，商可不是5000位）。那么要算得第二个余数需要除以9999次，依次类推，算得所有的余数需要的除法次数为：
10000+9999+...+2+1 约等于50000000。所以该算法的时间复杂度可不是楼主说的log2(n)*log10(n)，而是O(n^2)
更快的算法是有的，可以达到O(n*log2(n))，我不会，但我知道有人会。
13 楼
eastcowboy [专家分：25370] 发布于 2005-09-14 22:43:00
你说一个10000位的数，约用50000000次，那么复杂度就是log2(n)*log10(n)了。注意我说的n是这个10000位的数，而不是10000。
14 楼
boxertony [专家分：23030] 发布于 2005-09-15 09:45:00
原来楼主是这个意思啊，那倒是没有问题。不过，我们在评估这个算法复杂度的时候，我想主要是考虑位数的增加引起的复杂度的增加，直接用数据本身来评估是不大合适的。
另外，我的除法次数估计有误，少算了，呵呵。我只加了10000次，但实际上要求出10000位整数的2进制表示（他的位数应该有3万多位），应该需要加30000多次。也就是说，总的除法次数应该是50000000*log2(10)，约1.5亿次。所以你的log2(n)*log10(n)是对的，就是得搞明白我的n和你的n不一回事，呵呵。
15 楼
闪电123 [专家分：470] 发布于 2005-10-11 09:00:00
MAYBE素数表。。。。。
16 楼
eastcowboy [专家分：25370] 发布于 2005-10-11 12:51:00
似乎跟素数关系不大啊。
17 楼
ppoo24 [专家分：10] 发布于 2005-10-13 17:43:00
大家能否把这个汇编的公式（关于10进制——→2进制的转换）：
10进制整数=n*2^(n-1)+(n-1)*2^(n-2)+(n-2)*2^+.......
(这里我用n表示这个整数从左到右开始数的位数)
希望可以研究一下！！
18 楼
ppoo24 [专家分：10] 发布于 2005-10-13 17:45:00
大家能否把这个汇编的公式（关于10进制——→2进制的转换）：
10进制整数=n*2^(n-1)+(n-1)*2^(n-2)+(n-2)*2^+.......
(这里我用n表示这个整数从左到右开始数的位数)
希望可以研究一下！！[em2]
19 楼
ppoo24 [专家分：10] 发布于 2005-10-13 17:47:00
[color=0000FF]大家能否把这个汇编的公式（关于10进制——→2进制的转换）：
10进制整数=n*2^(n-1)+(n-1)*2^(n-2)+(n-2)*2^+.......
(这里我用n表示这个整数从左到右开始数的位数)
希望可以研究一下！！[/color][em2]
我来回复
您所在位置：