【学习笔记】多项式相关算法

手动博客搬家: 本文发表于20181125 13:19:28, 原地址https://blog.csdn.net/suncongbo/article/details/84485568

最近学了一下多项式相关算法，简单记录一下
记号说明: \(O(Af(n))\)表示时间复杂度\(O(f(n))\), FFT的常数为\(A\).
例如，进行了\(6\)次大小为\(2n\)的DFT/IDFT, 则复杂度为\(O(12n\log n)\)
以下的常数都是以我的实现方法为准，很可能有比我好的做法，如果有的话欢迎沟通（我太菜了）。

1. 多项式乘法
   两个\(n\)次多项式相乘，\(O(6n\log n)\)时间，\(2n\)空间
2. 多项式求逆
   \(n\)次多项式求逆，\(O(12n\log n)\)时间, \(4n\)空间
   https://blog.csdn.net/suncongbo/article/details/84485718
3. 多项式对数函数
   \(n\)次多项式对数函数，\(O(18n\log n)\), \(4n\)空间
   https://blog.csdn.net/suncongbo/article/details/84487306
4. 多项式指数函数
   \(n\)次多项式指数函数，\(O(48n\log n)\), \(4n\)空间
   https://blog.csdn.net/suncongbo/article/details/84559818
5. 多项式带余除法
   \(n\)次多项式除以小于\(n\)次的多项式，\(O(24n\log n)\), \(8n\)空间
   https://blog.csdn.net/suncongbo/article/details/84853342

【学习笔记】多项式相关算法

原文：https://www.cnblogs.com/suncongbo/p/10311207.html