這東西也是開了我眼界，你想兩個多項式乘法能有多困難，就是term by term的乘出來，然後加起來。
這樣當然需要N^2次的乘法(兩個多項式都是N degree的話，係數乘完以後再加起來。)
偏偏有人就是想要搞得 NlogN 的演算法 來計算這東西。
也算了嚇到我這種數學人。
以下是我看網路上影片作的筆記，主要就是Fast Fourier Transform+ Discrete Fourier Transform
這最古老 可以reference to Gauss.
但好滿玩的: 給大家看看唄
No comments:
Post a Comment