嘿，这俩问题问到点子上了，咱一个个掰扯清楚：

问题1：为何n点FFT等价于截断数据？这是否会使FFT的时间复杂度变为O(1)？ #

先把核心概念钉死：n点FFT的输入必须是长度为n的序列。如果你的原始信号x长度比n大，那用x的前n个点跑n点FFT，本质上就是对原始信号做了截断——因为FFT没办法直接处理长度不匹配的输入，你给它n个点，它就只盯着这n个点做变换，相当于把更长的信号“砍”到n点来分析。

但别被“截断”这俩字误导，时间复杂度绝对不可能是O(1)！FFT的核心是分治算法，它的时间复杂度是O(n log n)，这是由算法本身的运算逻辑决定的：你要处理n个数据点，就得做log₂n级别的分治拆分，每一级都要处理n次操作。哪怕你是截断后的数据，只要输入是n个点，运算量就和n直接挂钩——你想想，1024点FFT和102400点FFT的运算时间能一样吗？绝对不可能，O(1)意味着不管n多大，耗时都固定，这完全不符合FFT的实际运行情况。

问题2：为何n点FFT实现为fft(x[1:N])而非fft(x)[1:N]？后者的时间复杂度会变成O(1)吗？ #

这个设计纯粹是为了效率！咱直接对比两种操作的差异：

• fft(x[1:N])：先把x截断成前N个点，再对这N个点跑FFT。这时候FFT的输入长度是N，时间复杂度是O(N log N)，运算量只和N有关。
• fft(x)[1:N]：先对整个x做FFT（假设x的长度是M，M>N），这时候FFT的时间复杂度是O(M log M)，之后再取前N个结果。显然，当M远大于N时，前者的运算量要小得多——比如对10000点的信号做FFT再取前100点，和直接对前100点做FFT，前者的运算量是后者的几十倍，速度自然慢很多。

另外，哪怕用fft(x[1:N])，时间复杂度也不会变成O(1)，原因和第一个问题一样：你还是要处理N个点的FFT运算，运算量和N的大小直接相关，不可能是常数时间。

内容的提问来源于stack exchange，提问作者HXD