我没想仔细，这个算法也是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增多效率也可以成倍提高