前言

人生如逆旅，我亦是行人。

一、介紹

算法的世界多么廣大，我們可以將算法大致分為兩類：

• 第一類是較為有用的算法：比如一些經(jīng)典的圖算法，像 DFS 和 BFS（深度 / 廣度優(yōu)先算法），這些算法應(yīng)用在很多方面，他們非常高效，
  

• 第二類算法是那些極具美感的算法：例如當(dāng)我們第一次看到漢諾塔的遞歸實(shí)現(xiàn)算法時(shí)的狀態(tài)，你肯定會(huì)覺(jué)得這個(gè)算法賊牛逼，甚至?xí)凰拿栏兴鸷车剑@些算法或許并沒(méi)有那么有用或者高效，不過(guò)我們還是會(huì)研究它，就像沒(méi)事干了我們還是會(huì)看小說(shuō)；
  

這些偉大而精妙的算法會(huì)激發(fā)我們的靈感，促使我們發(fā)散性思考，下面介紹一種同時(shí)屬于以上兩類的算法：快速傅里葉變換（FFT）。

FFT 算法毫無(wú)疑問(wèn)是上個(gè)世紀(jì)發(fā)明的最偉大的算法之一。很多我們現(xiàn)代生活所依賴的科技，比如無(wú)線通訊和 GPS ，以至于任何和信號(hào)處理有關(guān)的算法，都依賴于 FFT 的深刻洞見(jiàn)。

人們常常不能感知 FFT 的美感，因?yàn)樗３Ｓ泻荛L(zhǎng)很長(zhǎng)的前置知識(shí)要求， 比如離散傅里葉變換、時(shí)域/頻域轉(zhuǎn)換、甚至更多。

yysy（有一說(shuō)一），想要真正搞清 FFT 的應(yīng)用，你也不得不把這些前置要求都學(xué)好。

快速傅里葉變換 ( fast Fourier transform ), 即利用計(jì)算機(jī)計(jì)算離散傅里葉變換（DFT)的高效、快速計(jì)算方法的統(tǒng)稱，簡(jiǎn)稱 FFT 。

二、學(xué)習(xí)

• 簡(jiǎn)單的問(wèn)題：給定兩個(gè)多項(xiàng)式，計(jì)算二者的乘積。
• 我們的任務(wù)就是設(shè)計(jì)高效的算法解決這個(gè)問(wèn)題。
  

1. 數(shù)學(xué)上，這個(gè)問(wèn)題可以直接通過(guò)重復(fù)使用乘法分配律解決。
   
   但是在計(jì)算機(jī)中，首先需要解決的問(wèn)題是，如何存儲(chǔ)一個(gè)多項(xiàng)式？

• 顯然，最自然的做法就是儲(chǔ)存多項(xiàng)式的系數(shù)。我們只需要把系數(shù)映射到一個(gè)數(shù)組中。

系數(shù)應(yīng)該按如下圖所示的順序儲(chǔ)存。

因?yàn)檫@樣一來(lái)數(shù)組的第 k 個(gè)數(shù)字正好對(duì)應(yīng)多項(xiàng)式的 k 階項(xiàng)系數(shù)。

這種表示方法為多項(xiàng)式的系數(shù)表示方法。

一般情況下，給定兩個(gè) d 階多項(xiàng)式，二者乘積應(yīng)為 2d 階多項(xiàng)式。

并且這一算法，如果用 naive 的乘法分配律來(lái)算，時(shí)間復(fù)雜度為 O(d ^ 2) 。因?yàn)槎囗?xiàng)式 A 的每一項(xiàng)都會(huì)跟多項(xiàng)式 B 的每一項(xiàng)相乘。

如何改進(jìn)這個(gè)算法？

例子

我們以最簡(jiǎn)單的多項(xiàng)式，即一階多項(xiàng)式/線性函數(shù)為例。

我們可以用兩個(gè)系數(shù)來(lái)表示線性函數(shù)，即截距（0階系數(shù)）和斜率（1階系數(shù)）（注：一對(duì)系數(shù)一對(duì)一決定了唯一的一條直線），還有沒(méi)有別的直線的表示也可以唯一確定一個(gè)直線呢？

表示其實(shí)很多，我們這里使用直線的兩點(diǎn)表示。

• 美麗的幾何學(xué)告訴我們：兩點(diǎn)確定一條直線。

• 事實(shí)上：高階多項(xiàng)式也有類似的性質(zhì)。 （即：任意 d 階多項(xiàng)式都由 d+1 個(gè)點(diǎn)唯一確定的）

例如下圖中的三個(gè)點(diǎn)確定了左邊這個(gè)二次函數(shù)：

如果圖中有四個(gè)點(diǎn)，那么我們就能確定左邊這個(gè)唯一的三次函數(shù)：

接下來(lái)證明一下這個(gè)結(jié)論：

• 假設(shè)我們有 p（x） 這個(gè) d 階多項(xiàng)式，通過(guò)了給定的 d+1 個(gè)點(diǎn)，我們需要證明：系數(shù)是唯一。
• 因此，我們將這 d+1 個(gè)點(diǎn)帶入多項(xiàng)式的方程，得到 d+1 個(gè)方程。線性方程組當(dāng)然可以寫(xiě)作 矩陣-向量 表示。
  
• 矩陣 M 可逆，只要這些 點(diǎn) x_0、… 、x_d 不重復(fù)（即兩兩都不同（下面為 范德蒙德矩陣）），只需證明 M 的行列式不為零（范德蒙德行列式）
  
  從而我們知道系數(shù)p_0、… 、p_d 是被 d+1 個(gè)點(diǎn)唯一確定的，從而多項(xiàng)式也是唯一的。

我們現(xiàn)在有兩種表示多項(xiàng)式的方法：

• 第一種是系數(shù)表示法；
• 第二種是 d+1 個(gè)點(diǎn)表示法，稱為值表示法；（利用值表示法，多項(xiàng)式乘法變得不能再簡(jiǎn)單了）

回到之前的問(wèn)題

乘出來(lái)的多項(xiàng)式 C（x）必然為 4 階，所以需要 5 個(gè)點(diǎn)表示。我們現(xiàn)在只需要挑出五個(gè)點(diǎn)并計(jì)算已有的兩個(gè)多項(xiàng)式的值，然后把對(duì)應(yīng)每個(gè)點(diǎn)的兩個(gè)值相乘，得到 C 在每個(gè)點(diǎn)的函數(shù)值。

根據(jù)我們前面的學(xué)習(xí)，五個(gè)點(diǎn)可以確定唯一的多項(xiàng)式，

這個(gè)多項(xiàng)式的系數(shù)表示我們也算出來(lái)了，利用值表示法，我們計(jì)算多項(xiàng)式乘法的時(shí)間一下子從 O（d^2）縮短到了 O（d）。

接下來(lái)開(kāi)始快速的多項(xiàng)式乘法算法了。

問(wèn)：

• 給定兩個(gè)系數(shù)表示的 d 階多項(xiàng)式，我們已經(jīng)知道了值表示法計(jì)算多項(xiàng)式乘法更快，所以我們可以先計(jì)算兩個(gè)多項(xiàng)式在 2d + 1 個(gè)點(diǎn)上的值，然后將函數(shù)值一對(duì)對(duì)地乘起來(lái)，從而得到乘出來(lái)的多項(xiàng)式的值表示，最后，將值表示轉(zhuǎn)換回系數(shù)表示。

• 主要的方法我們大致已經(jīng)清楚，現(xiàn)在的問(wèn)題在于還有些步驟我們沒(méi)搞清楚，
• 事實(shí)上我們?nèi)钡木褪牵喝绾螌⑾禂?shù)轉(zhuǎn)換成值表示，以及反過(guò)來(lái)，如何將值表示轉(zhuǎn)換成系數(shù)？
• 這一過(guò)程，實(shí)際上就是 FFT 重要之處。

四、求值（evaluation）

讓我們先關(guān)注一個(gè)方向：從系數(shù)表示到值表示。這個(gè)問(wèn)題稱為求值（evaluation）。

給定 d 階多項(xiàng)式和 n 個(gè)點(diǎn)，我們想計(jì)算多項(xiàng)式在這 n 個(gè)點(diǎn)上的值（n >= d+1）

• 我們可以采取粗暴的方式：直接在 x 軸上挑取 n 個(gè)點(diǎn)，一個(gè)一個(gè)計(jì)算函數(shù)值，但是如果這樣計(jì)算的話，將會(huì)變得十分麻煩。 即每個(gè)點(diǎn)的計(jì)算都是 O(d)，加起來(lái)還是 O(nd) >= O(d^2)。這樣問(wèn)題又變得像最初那樣復(fù)雜，現(xiàn)在的問(wèn)題是能不能整點(diǎn)更快的？

• 將問(wèn)題簡(jiǎn)化一下：考慮一個(gè)簡(jiǎn)單的多項(xiàng)式，比如：P(x) = x ^ 2，在 n=8 個(gè)點(diǎn)進(jìn)行求值。
• 那么問(wèn)題又來(lái)了，我們選那八個(gè)點(diǎn)更具有代表性呢？
• 有沒(méi)有這樣的一對(duì)點(diǎn)：當(dāng)你知道一個(gè)點(diǎn)的函數(shù)值時(shí)，另一個(gè)點(diǎn)的也可以立刻知道？
• 答案是：互為相反數(shù)的數(shù)對(duì)。（前提是：函數(shù) P 是一個(gè)偶函數(shù)）

• 如果是 P(x) = x^3 咋辦，？
• 事實(shí)上這個(gè)技巧依舊是對(duì)的，不過(guò)我們要在 -x 的函數(shù)值前面加個(gè)負(fù)號(hào)，

• 所以在這兩個(gè)偶/奇函數(shù)的情形中，我們只需要計(jì)算一半數(shù)量的點(diǎn)就好了，因?yàn)槭Ｏ乱话霃钠媾夹灾芯涂梢缘牡玫搅恕?/li>

再來(lái)看看奇偶這個(gè)點(diǎn)子對(duì)一般的多項(xiàng)式還適不適用，將多項(xiàng)式分成奇/偶函數(shù)兩個(gè)部分，把奇函數(shù)部分的 x 提出來(lái)一個(gè)，那么兩個(gè)括號(hào)里都是兩個(gè)偶多項(xiàng)式函數(shù)。

這樣的分解使得我們對(duì)于一對(duì)相反數(shù)計(jì)算函數(shù)值時(shí)，只需要計(jì)算其中一個(gè)，同時(shí)我們可以把兩部分都看作 x^2 的函數(shù)，你可以看到兩個(gè)子函數(shù)的階數(shù)都降到了 2，比原來(lái)的 5 階不知道高到哪去了。

• 推廣這一想法，如果我們有一個(gè) n-1 階多項(xiàng)式，我們想計(jì)算它在 n 個(gè)點(diǎn)的函數(shù)值，我們可以將多項(xiàng)式分為 奇 / 偶兩部分，每部分都只有 n/2 - 1 階
• 對(duì)于這兩個(gè)只有一半階的多項(xiàng)式，我們?cè)趺从?jì)算他們?cè)趯?duì)應(yīng)點(diǎn)的值呢？ 這又是一個(gè)求值問(wèn)題，不過(guò)這次我們需要計(jì)算我們所給的點(diǎn)的平方的函數(shù)值。因?yàn)槲覀円婚_(kāi)始取了一對(duì)對(duì)相反數(shù)，所以平方之后正好只剩 n/2 個(gè)點(diǎn)了，有沒(méi)有一點(diǎn)像遞歸算法。
• 總結(jié)：計(jì)算多項(xiàng)式 P 在 n 個(gè)點(diǎn)上的值，這 n 個(gè)點(diǎn)是一對(duì)對(duì)的相反數(shù)。我們把多項(xiàng)式分成（如上所述）的兩個(gè)部分，從而我們有兩個(gè)階為 n/2 - 1 的多項(xiàng)式，每個(gè)多項(xiàng)式也只需要求 n/2 個(gè)點(diǎn)的值。我們只需要遞歸地求這兩個(gè)小多項(xiàng)式的值，利用下方這兩個(gè)公式帶回去，就可以得到原多項(xiàng)式的 n 個(gè)的值。最后我們就得到了原多項(xiàng)式的值的表達(dá)。

如果上述的一切都行得通，那么我們的時(shí)間復(fù)雜度僅為 O(nlogn) ，因?yàn)閮蓚€(gè)子問(wèn)題都是原問(wèn)題規(guī)模的一半，而且我們只需要線性時(shí)間來(lái)計(jì)算原多項(xiàng)式的值。

• （一個(gè)問(wèn)題）在遞歸步驟：我們假設(shè)了每個(gè)多項(xiàng)式我們都使用相反數(shù)來(lái)對(duì)其進(jìn)行求值。注意對(duì)子問(wèn)題而言，每個(gè)求值點(diǎn)都是平方數(shù)，所以都是正的，遞歸不成立。
• 如何將新的求值點(diǎn)也搞成相反數(shù)對(duì)？

• 唯一的方法：就是將這些點(diǎn)都取成復(fù)數(shù)。這也正是 FFT 算法最奇思妙想的地方。

我們需要專門(mén)挑一些復(fù)數(shù)，使得它們平方之后，依舊是正負(fù)成對(duì)出現(xiàn)的。

現(xiàn)在又有一個(gè)問(wèn)題來(lái)了：該怎么取這些復(fù)數(shù)呢？

• 我們可以通過(guò)一個(gè)逆向工程來(lái)得到答案。

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-447191.html

到了這里，關(guān)于快速傅里葉變換（FFT）算法學(xué)習(xí)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！