关于一个运算优化的问题

litaoye · 发表于 2009-3-12 15:09:04

我看有人不到0.1秒就算出来了，我的大概是0.6左右，而且我的方法比较繁琐，程序比较长（近300行），感觉肯定有更简单，更简洁的方法！

无心人 · 发表于 2009-3-12 15:11:51

我觉得不用排序啊

计算A[k]同比A[k]小的数logXor

也是个n^2 / 2的计算量

直接计算也是n^2 / 2工作量

因为xor运算是可以交换的啊

无心人 · 发表于 2009-3-12 15:13:55

因为 XOR 可交换

只要计算不同的两个数的 XOR就可以了
相同的XOR后是0，可不计算

结果乘以2就行了

litaoye · 发表于 2009-3-12 15:19:20

原帖由 无心人 于 2009-3-12 15:13 发表
因为 XOR 可交换

只要计算不同的两个数的 XOR就可以了
相同的XOR后是0，可不计算

结果乘以2就行了

恩！乘以2已经用上了，相同数的处理应该加入进去！我想一下！

litaoye · 发表于 2009-3-12 15:22:01

排序速度应该几乎不影响最后总的时间，反正就是挺快的，主要是为了后面分治时比较简单！

无心人 · 发表于 2009-3-12 16:16:28

什么叫分治？？

你打算进行10^n的比较？？

无心人 · 发表于 2009-3-12 16:16:56

允许用汇编么？

呵呵

无心人 · 发表于 2009-3-12 16:26:04

让我想想

你打算排序后简化求对数的运算

那能不能找个速度快的对数算法？？？

litaoye · 发表于 2009-3-12 16:31:56

恩，主要是最高bit不同的情况，可以批量运算，比如说1200000同200000以下的都可以不用算了，xor后肯定都 > 1000000,
取log10的整数部分是一个结果！这样可以减少一部分运算量！

另外如果对每个数求了最高位，那么转化成对数也应该是挺快的！

无心人 · 发表于 2009-3-12 16:32:17

加入10^n进入序列？？？？？？
再排序？？？？？
如何

排完后
根据10^n分割成39块不同的数据
则程序绝大部分运算变成加法了吧？？

账号		自动登录	找回密码
密码			欢迎注册

[求助] 关于一个运算优化的问题