更快的傅里叶变换？一场大 O 记号的滥用

📋 概述

Ben Recht 拆解 OpenAI 数学仓库里号称更快的傅里叶变换。他先复习基础：傅里叶变换是一次点积，朴素做法需要 n² 次运算，而 Cooley–Tukey 的 FFT 用递归把代价降到约 5n log n，n 等于一百万时提速约一万倍；理论上限是 n 次运算，FFT 比这个合理下限慢 5 log₂n 倍，n 取一万亿时这个系数就是 200。OpenAI 的论文声称把 log(n) 项压小了一点，但作者连论文都没读——因为「OpenAI 里也没人读过」——而是直接把论文喂回机器，问 ChatGPT 怎么看它自己的输出。结论是那里并没有更快的傅里叶变换，问题出在大 O 记号被滥用到失去意义：当复杂度表达式里塞进足够小的项，任何东西都能被称作「突破」。他最后感慨 AI 很擅长自动化我们最糟的习惯，比如写没用的理论论文。