相关疑难解决方法(0)

我知道一个类似的问题,但我想请求人们对我的算法的意见,以尽可能准确地将浮点数与实际成本相加.

这是我的第一个解决方案:

put all numbers into a min-absolute-heap. // EDIT as told by comments below
pop the 2 smallest ones.
add them.
put the result back into the heap.
continue until there is only 1 number in the heap.

这个将采用O(n*logn)而不是正常的O(n).这真的值得吗？

第二个解决方案来自我正在研究的数据的特征.这是一个巨大的正数列表,具有相似的数量级.

a[size]; // contains numbers, start at index 0
for(step = 1; step < size; step<<=1)
    for(i = step-1; i+step<size; i+=2*step)
        a[i+step] += a[i];
    if(i < size-1)
        a[size-1] += a[i];

基本思想是以"二叉树"方式进行求和.

注意:它是伪C代码.step<<=1表示乘以步数2.这一个将取O(n).我觉得可能有更好的方法.你能推荐/批评吗？