The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

推荐理由

It derives the FFT algorithm from polynomial multiplication and it’s fantastic . I rewatch it every 6 months or so.

强烈推荐tverbeure · 原文2024年7月

说明

这是2020年由Reducible发布的一部讲解，主题归在Algorithms & data structures。它讲的是fast fourier transform这一支里的具体问题，而不是把整个领域扫一遍。适合已经能看懂基本术语、想继续往下走的人。内容上可以概括成：Reducible's visual walkthrough of the Fast Fourier Transform, motivated by polynomial multiplication. It shows how the FFT's key ideas can be discovered by asking the right questions.这些读者给出的理由，核心是：HN repeatedly calls it a fantastic explanation that made FFT click, with some rewatching it periodically.讲法不绑某一条新闻，过几年仍然可以当材料看。从2021年到2026年，有7位不同的读者在8个不同月份把它推荐出来，其中明确叫别人去看的有5次。适合用一集把一个概念补上的人。抓住它用的那个图像或类比，比背公式重要。如果已经会了基本定义，就把注意力放在它怎么把fast fourier transform变成能跟着复述的例子。

视频信息

频道

Reducible

时长

28 分 23 秒

发布年份

2020

同主题更多

• CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
• Modern Dictionaries by Raymond Hettinger
• CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"
• CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures”
• Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019
• The Fastest Way to Board a Plane Feels Like the Slowest