快速傅里叶变换(FFT)算法新手视频教程。
快速傅里叶变换(FFT)算法新手视频教程。
在本视频中,我们看一下有史以来最漂亮的算法之一:快速傅立叶变换(FFT)。 这是一个难以理解的算法,因此我们在大家都熟悉的环境中进行研究:多项式乘法。 你将看到如何通过提出正确的问题来“发现” FFT的核心思想。 该视频提供的关键见解是,可以通过在特殊值表示中乘以多项式来显着改善多项式乘法。 自身面临的挑战是将多项式从标准系数表示转换为值表示的问题。
我们看到FFT是执行此任务的效率极高的递归算法,并且我们还发现,稍作调整的FFT(逆FFT)也可以解决插值的逆问题