色好x久久,美日韩aaa在线

本章涉及知識點：

1、多項式乘法的時間復雜度

2、多項式的表示：系數

3、多項式的表示：點值

4、復數的表示

5、單位復數根

6、單位復數根的性質—消去引理

7、單位復數根的性質—折半引理

8、離散傅里葉變換：DFT和IDFT

9、快速傅里葉變換：FFT

10、FFT求解多項式乘法的步驟

11、python編程實戰(zhàn)FFT大數乘法

12、結果分析

一、多項式乘法的時間復雜度

數學中，我們可以將任意一個n位的數字寫為一個n-1次多項式，如456可以寫為

數字轉為多項式

即可抽象定義出以x為變量的多項式函數A(x)

多項式函數

其中aj表示：長度為N-1位數字的第j為數字

例如要計算456 * 123 = ？，則我們用多項式A(x)和B(x)來分別表示其各自的數字，C(x)表示兩個多項式的乘積

兩個數字的多項式

由乘法的運算規(guī)則，兩個數的每一位數字都要與另一個數的每一位相乘，最后相加同一位上所有的數字，得到乘積中該位的數字，即

多項式乘法

將x=10為基帶入結果，即可以得到456 * 123 =?4 * 10**4 + 13 * 10**3 + 28 * 10**2 + 27 * 10 + 18 =?56088

我們可以歸納出乘積C(x)的每一位數字的計算關系為

乘積數位的計算

其中cj表示：乘積數中的第j位的數字

則乘積多項式C(x)可以寫為

乘積多項式

至此我們可以看到，由于受限于乘法運算自身的規(guī)則，計算兩個多項式乘積（將數字轉換為多項式）的時間復雜度為： $O(n^{2})$ ，當n很大的時候復雜度將非常高

那么需要研究的問題就是：有沒有方法可以高效的提高多項式乘法復雜度呢？

二、多項式的表示：系數

為了降低多項式乘法的復雜度，我們首先需要了解幾個數學知識

從多項式函數的定義，我們將所有系數視為系數向量，而由全部系數組成的向量a叫做該多項式的系數表達

系數表達

PS：乘積多項式C(x)的系數向量cj，也稱輸入向量a和b的卷積，記為

卷積運算

從之前的分析可知，要計算出乘積C(x)的每一個系數向量cj，需要的時間復雜度為 $O(n^{2})$

三、多項式的表示：點值

我們任意選取n個不同的自變量x帶入多項式函數A(x)進行求值運算，將得到n個不同數值的y，即

求值運算

則多項式的點值表達就是由這n個數值點組成的集合

點值表達

因為可以選取任意n個不同點所構成的集合，所有一個多項式可以有很多不同的點值表達

我們把任意n個點構成的集合叫做點值表達的基

從點值表達的基入手，選取適當的xk來優(yōu)化多項式乘法效率，為此，我們選取單位復數根作為多項式的基

四、復數的表示

復數的定義：設a，b為實數，則形如 $z = a + bi$ 的數稱為復數，其中a稱為實部，b稱為虛部

PS：當a=0時，復數為純虛數；當b=0時，復數可視為實數

將復數的實部與虛部的平方和的正平方根值稱為該復數的模，即

復數的模

五、單位復數根

任意一個復數w，其n次冪的結果為1，就稱復數w是n次單位復數根，即

n次單位復數根

可以看到，n次單位復數根有n個，其幾何意義為：n個單位復數根均勻的分布在以復平面原點為圓心的單位圓上

n次單位復數根的幾何意義

在幾何意義的單位圓中，我們將圓周角 $2\pi$ 均分成n份，則 $\frac{2\pi}{n}$ 叫做單位根的幅角

由歐拉公式得

歐拉公式

我們定義 $w_{n}$ 表示一個n次單位根，則

主n次單位根

$w_{n}$ 又被稱為主n次單位根，而其余 $w_{n}^{1}$ 、 $w_{n}^{2}$ 等叫做n次單位根的冪次，記為： $w_{n}^{k}$ ，則

n次單位根的冪次

可以很容易知道

n次單位根的性質

下面我們證明n次單位根的兩個性質

六、單位復數根的性質—消去引理

設d>0為任何一個整數，則

消去引理

七、單位復數根的性質—折半引理

由

折半引理

則可以得到

折半引理

至此，可以看到通過消去和折半引理，我們將n的規(guī)模降低到了原來的一半

八、離散傅里葉變換：DFT和IDFT

回顧之前我們的多項式函數

多項式函數

我們將n次單位根的冪次項： $w_{n}^{0}，w_{n}^{1}，w_{n}^{2}，...，w_{n}^{n-1}$ 依次帶入A(x)，則得到

離散傅里葉正變換

記向量 $y = (y_{0}, y_{1},..., y_{n-1})$ 是系數向量 $a = (a_{0}, a_{1},..., a_{n-1})$ 的離散傅里葉變換，也稱離散傅里葉正變換（DFT）

則對應的離散傅里葉逆變換（IDFT）為

離散傅里葉逆變換

可以看到：

（1）DFT對應著多項式求值

（2）IDFT對應著插值，即求多項式的系數

九、快速傅里葉變換：FFT

由DFT定義可知，將 $w_{n}^{0}，w_{n}^{1}，w_{n}^{2}，...，w_{n}^{n-1}$ 全部依次帶入A(x)計算出多項式的時間復雜度仍然是 $O(n^{2})$

此時我們就需要利用之前所講的n次單位復數根的知識，將A(x)中的偶數下標和奇數下標的系數，分別用兩個新的多項式A1(x)和A2(x)來表示，即

偶數下標的多項式

奇數下標的多項式

注意：A(x)的次數界為n，A1(x)的次數界為n/2，A2(x)的次數界也為n/2

則可以得到A(x)和A1(x)、A2(x)的關系為

多項式函數關系

我們將 $x=w_{n}^{k}$ 帶入得，其中 $k=0,1,2,...,\frac{n}{2} - 1$

快速傅里葉變換1

至此，我們就得到了在 $[0, \frac{n}{2} - 1]$ 之間 $w_{n}^{k}$ 的所有求值

下面還需要計算 $[\frac{n}{2} , n-1]$ 之間的 $w_{n}^{k}$ 的值，根據折半引理，我們將 $x = w_{n}^{k + \frac{n}{2}}$ 帶入得

快速傅里葉變換2

至此，我們就得到了 $[\frac{n}{2} , n-1]$ 之間 $w_{n}^{k}$ 的所有求值

觀察上面兩個式子，不難發(fā)現(xiàn)：

（1） $A(w_{n}^{k})$ 和 $A(w_{n}^{k + \frac{n}{2}})$ 的計算式子里只有一個常數項互為相反數

（2）在 $[0, \frac{n}{2} - 1]$ 之間枚舉出 $A(w_{n}^{k})$ 后，就可以在 $O(1)$ 的時間里得到 $[\frac{n}{2} , n-1]$ 的 $A(w_{n}^{k + \frac{n}{2}})$

（3）原問題的規(guī)?？s小了一半（分治法的思想）

至此，我們利用數學中n次單位復數根的性質，將DFT優(yōu)化為FFT（快速傅里葉正變換），即

快速傅里葉正變換

十、FFT求解多項式乘法的步驟

通過以上的研究，我們可以總結出使用FFT計算多項式乘法的時間復雜度

FFT計算多項式乘法的時間復雜度

FFT利用n次單位復數根和分治法的思想，將多項式乘法的時間復雜度由 $O(n^{2})$ 降低到了 $O(n\lg n)$

最后我們可以總結出求解多項式乘法的高效算法步驟為：

（1）加倍次數界：由分治法的思想，將兩個多項式的次數界補全為2的冪次

（2）求值：通過FFT計算出兩個多項式的點值表達，即2n次單位復數根的多項式函數取值

（3）逐點相乘：將兩個多項式的點值依次相乘，得到相乘結果的點值

（4）插值：通過IDFT計算相乘結果的點值，得到相乘結果的每一個系數

十一、python編程實戰(zhàn)FFT大數乘法