算法课的 project 中有一道挺有意思的题,原文如下:
English Version
Formula Computing
Description
Given two arrays $a$ and $b$ of length $n$ which contains positive integers less than or equal to 100 (we assume that the array index starts at zero and $n < 10^5$), calculate $C[k]=\sum_{i=k}^{n-1}(a[i]\times b[i - k])$ for $k = 0,1,…,n-1$.
Input
The first line contains a positive integer $n$. There are two positive integers in each of the next $n$ lines representing the elements in the two arrays, i.e., the $(i+2)\text{-th}$ line contains $a[i]$,$b[i]$.
Output
$n$ lines. The $k\text{-th}$ line contains one positive number which represents $C[k-1]$.
Sample
Input
1
2
3
4
5
65
3 1
2 4
1 1
2 4
1 4Output
1
2
3
4
524
12
10
6
1
Solution
Naive Method
很简单,二重循环直接算即可,复杂度 $\Theta (n^2)$:
1 |
|
FFT Method
其实上述算法已经可以通过所有数据点了(可能是数据比较弱),不过显然不是课程期待的算法。
注意到$C[k]$的计算方式有点像卷积操作,令$a’[k]=a[n - 1 - k]$,则有$C[k]=\sum_{i=k}^{n-1}a[i]\times b[i-k]=\sum_{j=0}^{n-1-k}a’[(n-1-k)-j]\times b[j]$。至此已经有卷积的雏形了,再做一步代换$C’[k]=C[n-1-k]=\sum_{j=0}^{k}a’[k-j]\times b[j]$,终于出现了卷积形式。
有了卷积形式之后就可以使用 FFT 来加速了,复杂度 $\Theta (n \log n)$:
1 |
|