关于一个运算优化的问题

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块不同的数据则程序绝大部分运算变成加法了吧？？

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

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