转载自这里
有n个浮点数，现在要写C程序计算每n-1个数的乘积，不用除法，给出一个O(n)的算法
详情 :
n个数：X1, X2, …, Xn
求所有的Xi1 * Xi2 * … * Xin-1的值
其中i1, i2, …, in-1是{1, 2, …, n}中的任意不同的n-1个

这题目还是有点意思的，可以做一做，虽然不准用除法看上去有点无聊 ……

可以用乘法的话，O(n)忒简单了

貌似有一定难度啊。做不出啊做不出。

我只想到O(nlogn)的解法，还需要O(n)的空间……

看到一个巨简单的方法，我没想到，ft
一个数组a存{1, x1, x1*x2, x1*x2*x3, ..., x1*...*x(n-1) }
一个数组b存{x2*...*xn, x3*...*xn, ..., xn, 1}
构造这俩数组都只需要O(n)
输出result[i] = a[i] * b[i]

嘿，这算法漂亮，比我想到的好多了 ……

这个果然无敌，我一个EE的同学想了一个用指数和对数来模拟除法的算法，虽然也是O(n)，但看上去实在太无聊了。根本不能体现CS的精髓。还是tomato的那个好

嘿嘿，不过 tomato 那个算法虽然比我的简明漂亮，不过从实际执行乘法的次数来说，比我的多。为了得到所有的结果，这个算法大概要执行将近 3*n 次乘法，我的大概是 2*n 次。

＝＝＝＝＝＝＝＝＝＝＝＝

唔唔，我算错了，一样是 3*n 次这个等级 ……

我没想仔细，这个算法也是O(n)的

一
假设n = 2^k，k为整数
需要一个n-2的数组
1、
前n/2个数放{ x3*x4, x1*x2, x7*x8, x5*x6, ..., xn*x(n-1), x(n-2)*x(n-3) }
这一步需要n/2次乘法
之后的n/4个数放{ x5*x6*x7*x8, x1*x2*x3*x4, ..., x(n-3)*x(n-2)*x(n-1)*xn }
这一步需要n/4次乘法
...
...
最后放{ x(n/2+1)*x(n/2+2)*...*x(n), x1*x2*...*x(n/2) }
这一步需要2次乘法
完成这一切需要n-2次乘法
实际上这里构造了一个完全2叉树

2、
从树根开始遍历，将每一个父节点乘上子节点且放在子节点中，这里需要计算n-2次乘法
此时数组前n/2个数为
{x3*x4*x5~xn, x1*x2*x5~xn, x1~x4*x7~xn, x1~x6*x9~xn, ... }

3、
输出数组out[i] = temp[i/2] * in[i^1]（这里的计算实际上是使用0开头的数组，我懒得换算了）
这一步需要n次乘法

总计需要3n-4次乘法


二
算法：
一个数组a存{1, x1, x1*x2, x1*x2*x3, ..., x1*...*x(n-1) }
一个数组b存{x2*...*xn, x3*...*xn, ..., xn, 1}
构造这俩数组都只需要O(n)
输出result[i] = a[i] * b[i]
共需要3n-2次乘法
但这个算法的好处在于每次乘需要的值都有一个在寄存器中，可以省去把浮点数从内存往寄存器搬的一步
坏处在于每次做乘法都需要上一次乘法的结果，流水线只好每次都中断了


考虑多cpu的情况，第二种算法最多开2个线程，而前一种算法随着cpu增多效率也可以成倍提高